Maths Olympiad Prep

Library / /50 of 82

Number theory Difficulty 5.2 AIME, harder Prove it United States

Problem:
What is the smallest integer greater than 1010 such that the sum of the digits in its base 1717 representation is equal to the sum of the digits in its base 1010 representation?

Solution

Solution:
We assume that the answer is at most three digits (in base 1010). Then our desired number can be expressed in the form abc10=def17\overline{a b c}_{10} = \overline{d e f}_{17}, where a,b,ca, b, c are digits in base 1010, and d,e,fd, e, f are digits in base 1717. These variables then satisfy the equations
100a+10b+c=289d+17e+fa+b+c=d+e+f \begin{aligned} 100 a + 10 b + c &= 289 d + 17 e + f \\ a + b + c &= d + e + f \end{aligned}
Subtracting the second equation from the first, we obtain 99a+9b=288d+16e99 a + 9 b = 288 d + 16 e, or 9(11a+b)=16(18d+e)9(11 a + b) = 16(18 d + e). From this equation, we find that 11a+b11 a + b must be divisible by 1616, and 18d+e18 d + e must be divisible by 99.

To minimize abc\overline{a b c}, we find the minimal possible value of aa:

If a=0a = 0, then the only way for 11a+b=b11 a + b = b to be divisible by 1616 is to set b=0b = 0; however, this is disallowed by the problem condition, which stipulates that the number must be greater than 1010.

If we try a=1a = 1, then we find that the only possible value of bb which lets 11a+b=b+1111 a + b = b + 11 be divisible by 1616 is b=5b = 5. Plugging these in and simplifying, we find that we must have 18d+e=918 d + e = 9. The only possible solution to this is d=0,e=9d = 0, e = 9.

Now to satisfy a+b+c=d+e+fa + b + c = d + e + f, we must have 1+5+c=0+9+f1 + 5 + c = 0 + 9 + f, or c=f+3c = f + 3. The minimal possible solution to this is c=3,f=0c = 3, f = 0.

So our answer is abc=153\overline{a b c} = 153, which is also equal to 09017090_{17}.

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.