Maths Olympiad Prep

Library / /459 of 520

Number theory Difficulty 4.1 AIME Find the answer

Let S(n)S(n) equal the sum of the digits of positive integer nn. For example, S(1507)=13S(1507) = 13. For a particular positive integer nn, S(n)=1274S(n) = 1274. Which of the following could be the value of S(n+1)S(n+1)?

Pick one

Solutions — 2

Solution 1

Note that nS(n)(mod9)n \equiv S(n) \pmod{9}. This can be seen from the fact that k=0n10kakk=0nak(mod9)\sum_{k=0}^{n}10^{k}a_k \equiv \sum_{k=0}^{n}a_k \pmod{9}. Thus, if S(n)=1274S(n) = 1274, then n5(mod9)n \equiv 5 \pmod{9}, and thus n+1S(n+1)6(mod9)n+1 \equiv S(n+1) \equiv 6 \pmod{9}. The only answer choice that satisfies n+16(mod9)n+1 \equiv 6 \pmod{9} is (D)1239\boxed{\textbf{(D)} 1239}.

Solution 2

1. Let S(n)=1274 S(n) = 1274 . This means the sum of the digits of n n is 1274.
2. When we add 1 to n n , we need to consider how this affects the sum of the digits. If adding 1 to n n does not cause any carries, then S(n+1)=S(n)+1=1274+1=1275 S(n+1) = S(n) + 1 = 1274 + 1 = 1275 .
3. However, if adding 1 to n n causes carries, the sum of the digits can change more significantly. For example, if n n ends in a sequence of 9's, adding 1 will turn these 9's into 0's and increase the next digit by 1.
4. Consider the case where n n ends in k k nines. For example, if n=999999 n = 999 \ldots 999 (with k k nines), then n+1=1000000 n+1 = 1000 \ldots 000 (with k k zeros and a leading 1). The sum of the digits changes from 9k 9k to 1.
5. In general, if n n has a sequence of k k trailing nines, adding 1 will decrease the sum of the digits by 9k 9k and increase it by 1 (from the carry). Therefore, S(n+1)=S(n)9k+1 S(n+1) = S(n) - 9k + 1 .
6. We need to find a value of k k such that S(n+1) S(n+1) is one of the given options: 1, 3, 12, 1239, or 1265.

Let's check each option:
- For S(n+1)=1 S(n+1) = 1 :
1=12749k+1    0=12749k    9k=1274    k=12749141.56 1 = 1274 - 9k + 1 \implies 0 = 1274 - 9k \implies 9k = 1274 \implies k = \frac{1274}{9} \approx 141.56
Since k k must be an integer, this is not possible.

- For S(n+1)=3 S(n+1) = 3 :
3=12749k+1    2=12749k    9k=1272    k=12729141.33 3 = 1274 - 9k + 1 \implies 2 = 1274 - 9k \implies 9k = 1272 \implies k = \frac{1272}{9} \approx 141.33
Since k k must be an integer, this is not possible.

- For S(n+1)=12 S(n+1) = 12 :
12=12749k+1    11=12749k    9k=1263    k=12639140.33 12 = 1274 - 9k + 1 \implies 11 = 1274 - 9k \implies 9k = 1263 \implies k = \frac{1263}{9} \approx 140.33
Since k k must be an integer, this is not possible.

- For S(n+1)=1239 S(n+1) = 1239 :
1239=12749k+1    1238=12749k    9k=36    k=369=4 1239 = 1274 - 9k + 1 \implies 1238 = 1274 - 9k \implies 9k = 36 \implies k = \frac{36}{9} = 4
This is possible since k=4 k = 4 is an integer.

- For S(n+1)=1265 S(n+1) = 1265 :
1265=12749k+1    1264=12749k    9k=10    k=1091.11 1265 = 1274 - 9k + 1 \implies 1264 = 1274 - 9k \implies 9k = 10 \implies k = \frac{10}{9} \approx 1.11
Since k k must be an integer, this is not possible.

Therefore, the only possible value for S(n+1) S(n+1) is 1239.

The final answer is 1239 \boxed{1239} .

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.