Olympiad Maths Prep

Track / Stage 5 / 235 of 400 #835 of 2000

Problem 835

AIME late
Number theory Difficulty 5.6 Prove it

Let S(n)S(n) denote the sum of the digits of the integer nn. Then for any integer m(m>1)m (m>1), there does not exist a positive integer nn such that
nS(n)=10m10 n-S(n)=10^{m}-10 \text {. }

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Prove that for some integer m(m>1)m(m>1), assuming there exists a positive integer nn such that equation (1) holds. Let
n=10kak+10k1ak1++10a1+a0 n=10^{k} a_{k}+10^{k-1} a_{k-1}+\cdots+10 a_{1}+a_{0} \text {, }

where ak,ak1,,a0a_{k}, a_{k-1}, \cdots, a_{0} are non-negative integers no greater than 9, and ak1a_{k} \geqslant 1.
Thus, S(n)=ak+ak1++a0S(n)=a_{k}+a_{k-1}+\cdots+a_{0}.
(1) k<10m10k<10^{m}-10, contradiction.
(3) k>mk>m.

It is easy to see that nn has at least one more digit than 10m10^{m}.
 By ak+ak1++am+am1++a0=10kak+10k1ak1++10m(am1)+10m1am1++a0+10 \begin{array}{l} \text { By } a_{k}+a_{k-1}+\cdots+a_{m}+a_{m-1}+\cdots+a_{0} \\ =10^{k} a_{k}+10^{k-1} a_{k-1}+\cdots+10^{m}\left(a_{m}-1\right)+ \\ 10^{m-1} a_{m-1}+\cdots+a_{0}+10 \text {, } \end{array}

then ak=1,ak1==am=am1==a1=0a_{k}=1, a_{k-1}=\cdots=a_{m}=a_{m-1}=\cdots=a_{1}=0.
Thus, nS(n)=10k1>10m10n-S(n)=10^{k}-1>10^{m}-10, contradiction.
In summary, the generalization holds.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.