Track / Stage 3 / 63 of 260 #543 of 2444

Problem 543

AMC 10/12, early questions

Number theory Difficulty 3.4 Prove it Junior Macedonian Mathematical Olympiad · North Macedonia

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

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

The numbers $n$ and $S(n)$ have the same remainder when divided by $3$ and $9$ . Namely, if $n = \overline{a_m a_{m-1} \dots a_1 a_0}$ then
$\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 $9$ , therefore $n$ and $S(n)$ have the same remainder when divided by $3$ and $9$ . The numbers $n$ , $S(n)$ , $S(S(n))$ have the same remainder when divided by $3$ . Therefore the sum $n + S(n) + S(S(n))$ is always divisible by $3$ while $2011$ is not. Therefore the equation has no solution.

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