Number theoryDifficulty 3.4AMC 10/12Prove itNorth 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.
Solution
The numbers n and S(n) have the same remainder when divided by 3 and 9. Namely, if n=amam−1…a1a0 then n=amam−1…a1a0=10mam+10m−1am−1+⋯+10a1+a0=[(10m−1)am+(10m−1−1)am−1+⋯+(10−1)a1]+[am+am−1+⋯+a1+a0] 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.
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.