Maths Olympiad Prep

Library / Romanian Mathematical Olympiad /164 of 275

Romanian Mathematical Olympiad

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=305⋅2a2^x + 2^y + 2^z + 2^t = 305 \cdot 2^a, whence
2x⋅(1+2y−x+2z−x+2t−x)=305⋅2a(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 y−xy-x, z−xz-x and t−xt-x are positive integers, hence 2y−x2^{y-x}, 2z−x2^{z-x}, 2t−x2^{t-x} are even, and 1+2y−x+2z−x+2t−x1+2^{y-x}+2^{z-x}+2^{t-x} is odd.
For parity reasons, (1) yields 2x=2a2^x = 2^a and 1+2y−x+2z−x+2t−x=3051+2^{y-x}+2^{z-x}+2^{t-x} = 305, hence x=ax=a and 2y−x+2z−x+2t−x=3042^{y-x}+2^{z-x}+2^{t-x} = 304.
This gives
2y−x⋅(1+2z−y+2t−y)=24⋅19, 2^{y-x} \cdot (1 + 2^{z-y} + 2^{t-y}) = 2^4 \cdot 19,
whence y−x=4y-x = 4, so y=a+4y = a+4.
Moreover, 1+2z−y+2t−y=191+2^{z-y}+2^{t-y} = 19, so 2z−y(1+2t−z)=2⋅92^{z-y}(1+2^{t-z}) = 2 \cdot 9, therefore z−y=1z-y = 1 and t−z=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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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