Maths Olympiad Prep

Library / /1 of 2

Number theory Difficulty 3.4 AMC 10/12 Prove it North Macedonia

Let S(n)S(n) denote the sum of the digits of the natural number nn. For example: n=2456n = 2456, S(n)=S(2456)=2+4+5+6=16S(n) = S(2456) = 2+4+5+6=16, S(S(n))=S(S(2456))=S(16)=1+6=7S(S(n)) = S(S(2456)) = S(16)=1+6=7. Is there a natural number nn for which n+S(n)+S(S(n))=2011n + S(n) + S(S(n)) = 2011.

Solution

The numbers nn and S(n)S(n) have the same remainder when divided by 33 and 99. Namely, if n=amam1a1a0n = \overline{a_m a_{m-1} \dots a_1 a_0} then
n=amam1a1a0=10mam+10m1am1++10a1+a0=[(10m1)am+(10m11)am1++(101)a1]+[am+am1++a1+a0] \begin{aligned} n &= \overline{a_m a_{m-1} \dots a_1 a_0} = 10^m a_m + 10^{m-1} a_{m-1} + \dots + 10 a_1 + a_0 \\ &= [(10^m - 1)a_m + (10^{m-1} - 1)a_{m-1} + \dots + (10 - 1)a_1] + [a_m + a_{m-1} + \dots + a_1 + a_0] \end{aligned}
Each expression in the brackets is divisible by 99, therefore nn and S(n)S(n) have the same remainder when divided by 33 and 99. The numbers nn, S(n)S(n), S(S(n))S(S(n)) have the same remainder when divided by 33. Therefore the sum n+S(n)+S(S(n))n + S(n) + S(S(n)) is always divisible by 33 while 20112011 is not. Therefore the equation has no 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 and solution reproduced as published; topic and difficulty added by this site.