Maths Olympiad Prep

Library / /31 of 33

, 2011

Number theory Difficulty 8.6 Shortlist Prove it Baltic Way

For any natural number nn, denote by N(n)N(n) the number of digits of nn and by S(n)S(n) the sum of digits of nn. (Assume that numbers do not start with zero.)
Which digits can occur in a natural number nn if nS(n)<mS(m)\frac{n}{S(n)} < \frac{m}{S(m)} for all other mm such that N(m)=N(n)N(m) = N(n)?

Solution

Let nn be fixed. Consider the number that is obtained by increasing or decreasing one of its digits by ii, i.e., the number n±bin \pm bi where b=10kb = 10^k for some kk. Then
n±biS(n±bi)>nS(n)    n±biS(n)±i>nS(n)    n±bin>S(n)±iS(n)    1±bin>1±iS(n)    ±bin>±iS(n)    ±b>±nS(n). \begin{align*} \frac{n \pm bi}{S(n \pm bi)} > \frac{n}{S(n)} &\iff \frac{n \pm bi}{S(n) \pm i} > \frac{n}{S(n)} \\ &\iff \frac{n \pm bi}{n} > \frac{S(n) \pm i}{S(n)} \\ &\iff 1 \pm \frac{bi}{n} > 1 \pm \frac{i}{S(n)} \\ &\iff \pm \frac{bi}{n} > \pm \frac{i}{S(n)} \\ &\iff \pm b > \pm \frac{n}{S(n)}. \end{align*}
The last inequality is equivalent to nS(n)<b\frac{n}{S(n)} < b in the case of plus and to nS(n)>b\frac{n}{S(n)} > b in the case of minus.
This shows that no number nn with the property described in the problem can contain digits 2 through 8. Otherwise, this digit could be both increased and decreased leading to contradictory conclusions since the ratio of the number and its sum of digits increases in both cases.
It remains to show that the numbers with the desired property can contain digits 0, 1, 9. For that, we prove that 1099 has the desired property. Let n=d3d2d1d0n = \overline{d_3d_2d_1d_0} be an arbitrary 4-digit number. For arbitrary positive integer xx, denote R(x)=xS(x)R(x) = \frac{x}{S(x)}.
If d0<9d_0 < 9 then the last digit can be increased. As d3>0d_3 > 0 implies
R(d3d2d19)=1000d3+100d2+10d1+9d3+d2+d1+9>1, R(\overline{d_3d_2d_19}) = \frac{1000d_3 + 100d_2 + 10d_1 + 9}{d_3 + d_2 + d_1 + 9} > 1,
we obtain R(d3d2d19)<R(n)R(\overline{d_3d_2d_19}) < R(n).
If d1<9d_1 < 9 then the tens digit can be increased. As
R(d3d299)=1000d3+100d2+99d3+d2+9+9>10009+9+9+9>1000100=10, R(\overline{d_3d_299}) = \frac{1000d_3 + 100d_2 + 99}{d_3 + d_2 + 9 + 9} > \frac{1000}{9 + 9 + 9 + 9} > \frac{1000}{100} = 10,
If d3>1d_3 > 1 then the thousands digit can be decreased. As
R(1d299)=1000+100d2+991+d2+9+9<90009=1000, R(\overline{1d_299}) = \frac{1000 + 100d_2 + 99}{1 + d_2 + 9 + 9} < \frac{9000}{9} = 1000,
we obtain R(1d299)<R(d3d299)R(\overline{1d_299}) < R(\overline{d_3d_299}).
Finally if d2>0d_2 > 0 then the hundreds digit can be decreased. As
R(1099)=109919<100, R(1099) = \frac{1099}{19} < 100,
we obtain R(1099)<R(1d299)R(1099) < R(\overline{1d_299}). Consequently,
R(1099)R(1d299)R(d3d299)R(d3d2d19)R(n), R(1099) \le R(\overline{1d_299}) \le R(\overline{d_3d_299}) \le R(\overline{d_3d_2d_19}) \le R(n),
whereby all equalities hold simultaneously only if n=1099n = 1099. This completes the proof.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.