Maths Olympiad Prep

Library / /44 of 61

Algebra Difficulty 7.0 National Olympiad Prove it Canada

Problem:
For any real number tt, denote by [t][t] the greatest integer which is less than or equal to tt. For example: [8]=8[8]=8, [π]=3[\pi]=3 and [5/2]=3[-5 / 2]=-3. Show that the equation
[x]+[2x]+[4x]+[8x]+[16x]+[32x]=12345 [x]+[2x]+[4x]+[8x]+[16x]+[32x]=12345
has no real solution.

Solution

Solution:
Let xx be a real number. For any integer n0n \geq 0, [2nx][2^n x] is the greatest integer less than or equal to 2nx2^n x.

Let S(x)=[x]+[2x]+[4x]+[8x]+[16x]+[32x]S(x) = [x] + [2x] + [4x] + [8x] + [16x] + [32x].

Let x=a+yx = a + y, where aa is an integer and 0y<10 \leq y < 1.
Then [2kx]=[2ka+2ky]=2ka+[2ky][2^k x] = [2^k a + 2^k y] = 2^k a + [2^k y] for k=0,1,2,3,4,5k = 0,1,2,3,4,5.

So,
S(x)=k=05[2kx]=k=05(2ka+[2ky])=(k=052k)a+k=05[2ky] S(x) = \sum_{k=0}^5 [2^k x] = \sum_{k=0}^5 (2^k a + [2^k y]) = (\sum_{k=0}^5 2^k)a + \sum_{k=0}^5 [2^k y]
But k=052k=1+2+4+8+16+32=63\sum_{k=0}^5 2^k = 1 + 2 + 4 + 8 + 16 + 32 = 63.
So,
S(x)=63a+k=05[2ky] S(x) = 63a + \sum_{k=0}^5 [2^k y]

Now, 0y<10 \leq y < 1, so 02ky<2k0 \leq 2^k y < 2^k.
Therefore, [2ky][2^k y] is an integer between 00 and 2k12^k - 1.

Thus, k=05[2ky]\sum_{k=0}^5 [2^k y] is an integer between 00 and 1+3+7+15+31=571 + 3 + 7 + 15 + 31 = 57 (since [2ky]2k1[2^k y] \leq 2^k - 1), but actually, for k=0k=0 to 55, [2ky][2^k y] runs from 00 to 2k12^k - 1, so the sum runs from 00 to 1+3+7+15+31=571 + 3 + 7 + 15 + 31 = 57 for k=1k=1 to 55, plus [y][y] which is 00 (since 0y<10 \leq y < 1), so the sum is from 00 to 6262.

But let's check:
For k=0k=0, [20y]=[y]=0[2^0 y] = [y] = 0 (since 0y<10 \leq y < 1).
For k=1k=1, [2y][2y] runs from 00 to 11.
For k=2k=2, [4y][4y] runs from 00 to 33.
For k=3k=3, [8y][8y] runs from 00 to 77.
For k=4k=4, [16y][16y] runs from 00 to 1515.
For k=5k=5, [32y][32y] runs from 00 to 3131.
So the sum k=05[2ky]\sum_{k=0}^5 [2^k y] runs from 00 to 0+1+3+7+15+31=570 + 1 + 3 + 7 + 15 + 31 = 57.

Therefore, S(x)=63a+mS(x) = 63a + m, where mm is an integer between 00 and 5757.

Thus, S(x)S(x) can only take values congruent to mm modulo 6363, i.e., S(x)m(mod63)S(x) \equiv m \pmod{63}, where 0m570 \leq m \leq 57.

But for a fixed aa, S(x)S(x) runs through 63a,63a+1,,63a+5763a, 63a+1, \ldots, 63a+57 as yy varies from 00 to 11.

Therefore, S(x)S(x) can only take values congruent to 0,1,2,,570,1,2,\ldots,57 modulo 6363.

Now, 12345=63×196+5712345 = 63 \times 196 + 57.
So 1234557(mod63)12345 \equiv 57 \pmod{63}.

Therefore, for a=196a = 196, S(x)S(x) could be 63×196+m63 \times 196 + m for 0m570 \leq m \leq 57.
But 12345=63×196+5712345 = 63 \times 196 + 57, so m=57m = 57.

But let's check if m=57m = 57 is possible.

But m=k=05[2ky]=0+1+3+7+15+31=57m = \sum_{k=0}^5 [2^k y] = 0 + 1 + 3 + 7 + 15 + 31 = 57.
Is it possible for [2y]=1[2y]=1, [4y]=3[4y]=3, [8y]=7[8y]=7, [16y]=15[16y]=15, [32y]=31[32y]=31 and [y]=0[y]=0?

Let's see:
[2y]=1[2y]=1 implies 12y<21 \leq 2y < 2, so 0.5y<10.5 \leq y < 1.
[4y]=3[4y]=3 implies 34y<43 \leq 4y < 4, so 0.75y<10.75 \leq y < 1.
[8y]=7[8y]=7 implies 78y<87 \leq 8y < 8, so 0.875y<10.875 \leq y < 1.
[16y]=15[16y]=15 implies 1516y<1615 \leq 16y < 16, so 0.9375y<10.9375 \leq y < 1.
[32y]=31[32y]=31 implies 3132y<3231 \leq 32y < 32, so 0.96875y<10.96875 \leq y < 1.

So, yy must satisfy all these inequalities:
0.96875y<10.96875 \leq y < 1.

But [y]=0[y]=0 requires 0y<10 \leq y < 1 (which is always true for yy in [0,1)[0,1)).

Therefore, such yy exists, for example, y=0.97y = 0.97.

But let's check if S(x)S(x) can actually be 1234512345 for x=a+y=196+yx = a + y = 196 + y with yy in [0.96875,1)[0.96875, 1).

But recall that [x]=a[x] = a (since 0y<10 \leq y < 1), [2x]=2a+[2y][2x] = 2a + [2y], [4x]=4a+[4y][4x] = 4a + [4y], etc.
So,
S(x)=63a+[y]+[2y]+[4y]+[8y]+[16y]+[32y] S(x) = 63a + [y] + [2y] + [4y] + [8y] + [16y] + [32y]
For a=196a = 196, S(x)=12348+mS(x) = 12348 + m.
But 12345=12348+m12345 = 12348 + m implies m=3m = -3.
But mm cannot be negative, as m=[y]+[2y]+[4y]+[8y]+[16y]+[32y]0m = [y] + [2y] + [4y] + [8y] + [16y] + [32y] \geq 0.

Wait, but above we had 12345=63×196+57=12348+57=1240512345 = 63 \times 196 + 57 = 12348 + 57 = 12405.
But 63×196=1234863 \times 196 = 12348, 12348+57=1240512348 + 57 = 12405.
But 12345=63×195+60=12285+60=1234512345 = 63 \times 195 + 60 = 12285 + 60 = 12345.
So 12345=63×195+6012345 = 63 \times 195 + 60.
So m=60m = 60.
But mm can only be 00 to 5757.
Therefore, S(x)S(x) can only take values 63a+m63a + m for 0m570 \leq m \leq 57.

Therefore, 1234512345 cannot be written as 63a+m63a + m with 0m570 \leq m \leq 57.

Therefore, the equation has no real solution.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.