Maths Olympiad Prep

Library / Harvard-MIT November Tournament /43 of 74

Harvard-MIT November Tournament

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 abc‾10=def‾17\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,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.