Maths Olympiad Prep

Library / /3 of 9

Algebra Difficulty 4.0 AMC 10/12 Prove it Japan

For each positive integer kk, denote by S(k)S(k) the sum of the digits of kk. How many positive integers nn less than or equal to 999999 are there for which S(n)S(n+1)\frac{S(n)}{S(n+1)} is an integer?

Solution

A positive integer nn less than or equal to 999999 can be represented as 102a+10b+c10^2a + 10b + c where a,b,ca, b, c are integers satisfying 0a,b,c90 \le a, b, c \le 9 and a+b+c0a + b + c \ne 0. Then we have S(n)=a+b+cS(n) = a + b + c and
S(n+1)={a+b+c+1,if c<9(i),a+b+1,if c=9,b<9(ii),a+1,if c=b=9,a<9(iii),1,if c=b=a=9(iv). S(n+1) = \begin{cases} a + b + c + 1, & \text{if } c < 9 \cdots (\text{i}), \\ a + b + 1, & \text{if } c = 9, b < 9 \cdots (\text{ii}), \\ a + 1, & \text{if } c = b = 9, a < 9 \cdots (\text{iii}), \\ 1, & \text{if } c = b = a = 9 \cdots (\text{iv}). \end{cases}

Now, it is clear that S(n)S(n+1)\frac{S(n)}{S(n+1)} is not an integer in case (i), and is the integer 999999 in case (iv) above. In case (iii), we have S(n)S(n+1)=a+18a+1\frac{S(n)}{S(n+1)} = \frac{a + 18}{a + 1}, which is an integer only when a=0a = 0, corresponding to the case n=99n = 99. Finally, in case (ii), S(n)S(n+1)=a+b+9a+b+1\frac{S(n)}{S(n+1)} = \frac{a + b + 9}{a + b + 1}, with 0a90 \le a \le 9, 0b<90 \le b < 9. If we let k=a+bk = a + b, then we see that k+9k+1\frac{k + 9}{k + 1} is an integer only when k=0,1,3,7k = 0, 1, 3, 7, from which we conclude that only possibilities for (a,b)(a, b) under the case (ii) are
(a,b)=(0,0),(0,1),(0,3),(0,7),(1,0),(1,2),(1,6),(2,1),(2,5),(3,0),(3,4),(4,3),(5,2),(6,1),(7,0), (a, b) = (0, 0), (0, 1), (0, 3), (0, 7), (1, 0), (1, 2), (1, 6), (2, 1), (2, 5), (3, 0), (3, 4), (4, 3), (5, 2), (6, 1), (7, 0),
and these choices of (a,b)(a, b) correspond to
n=9,19,39,79,109,129,169,219,259,309,349,439,529,619,709, n = 9, 19, 39, 79, 109, 129, 169, 219, 259, 309, 349, 439, 529, 619, 709,
respectively. These, together with the numbers 9999 and 999999 found above, give 1717 integers satisfying the condition of the problem.

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.