Maths Olympiad Prep

Library / /17 of 39

Number theory Difficulty 6.0 AIME, harder Prove it Romania

Let x,y,z,tx, y, z, t be pairwise distinct positive integers and n=2x+2y+2z+2tn = 2^x + 2^y + 2^z + 2^t. The division of nn by 305305 gives the quotient 2a2^a and leaves the remainder 00, where aa is a non-negative integer.
Find the remainder of the division of a+x+y+z+ta + x + y + z + t by 55.

Solution

Assume, without loss of generality, that x<y<z<tx < y < z < t. Then 2x+2y+2z+2t=3052a2^x + 2^y + 2^z + 2^t = 305 \cdot 2^a, whence
2x(1+2yx+2zx+2tx)=3052a(1) 2^x \cdot (1 + 2^{y-x} + 2^{z-x} + 2^{t-x}) = 305 \cdot 2^a \tag{1}
Since x<y<z<tx < y < z < t, the numbers yxy-x, zxz-x and txt-x are positive integers, hence 2yx2^{y-x}, 2zx2^{z-x}, 2tx2^{t-x} are even, and 1+2yx+2zx+2tx1+2^{y-x}+2^{z-x}+2^{t-x} is odd.
For parity reasons, (1) yields 2x=2a2^x = 2^a and 1+2yx+2zx+2tx=3051+2^{y-x}+2^{z-x}+2^{t-x} = 305, hence x=ax=a and 2yx+2zx+2tx=3042^{y-x}+2^{z-x}+2^{t-x} = 304.
This gives
2yx(1+2zy+2ty)=2419, 2^{y-x} \cdot (1 + 2^{z-y} + 2^{t-y}) = 2^4 \cdot 19,
whence yx=4y-x = 4, so y=a+4y = a+4.
Moreover, 1+2zy+2ty=191+2^{z-y}+2^{t-y} = 19, so 2zy(1+2tz)=292^{z-y}(1+2^{t-z}) = 2 \cdot 9, therefore zy=1z-y = 1 and tz=3t-z = 3, that is z=y+1=a+5z = y+1 = a+5 and t=z+3=a+8t = z+3 = a+8.
The above yield
a+x+y+z+t=a+a+(a+4)+(a+5)+(a+8)=5a+17=5(a+3)+2, a+x+y+z+t = a+a+(a+4)+(a+5)+(a+8) = 5a+17 = 5 \cdot (a+3)+2,
so the remainder of the division of the sum a+x+y+z+ta+x+y+z+t by 55 is 22.

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 and solution reproduced as published; topic and difficulty added by this site.