2017 AMC 10A Problem 20

P16-20~4 minPrint

Bases & Digits Modular Arithmetic Use the answer choices (mod checks, size, form) to eliminate or select Use an invariant, parity, or coloring argument

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

Show solution without answering

Key insight

Adding 1 raises the digit sum by 1, but each 9 that turns into 0 takes away 9. So the new digit sum is 1275 minus a multiple of 9.

Solution

1. Try small examples. $S(23) = 5$ and $S(24) = 6$ : adding $1$ usually raises the digit sum by $1$ . But $S(199) = 19$ and $S(200) = 2$ : the two $9$ s turned into $0$ s, each losing $9$ , and the $1$ went up to $2$ .
2. The general rule. If $n$ ends in $k$ nines, adding $1$ turns those nines into zeros (losing $9$ each) and raises the next digit by $1$ . So
$S(n+1) = S(n) + 1 - 9k = 1275 - 9k.$
(With $k = 0$ this is just $1275$ .)
3. Test the choices. $S(n+1)$ must equal $1275$ minus a multiple of $9$ . Subtract each choice from $1275$ and see whether $9$ divides the result:

Choice	$1275 - \text{choice}$	Divisible by $9$ ?
$1$	$1274$	no ( $1274 = 9 \cdot 141 + 5$ )
$3$	$1272$	no ( $1272 = 9 \cdot 141 + 3$ )
$12$	$1263$	no ( $1263 = 9 \cdot 140 + 3$ )
$1239$	$36$	yes ( $36 = 9 \cdot 4$ )
$1265$	$10$	no

Check that $1239$ really happens. We need $n$ ending in exactly four nines with digit sum $1274$ . Those four nines give $36$ , so the other digits must add to $1274 - 36 = 1238$ . For example, take a $6$ , then $154$ eights ( $6 + 154 \cdot 8 = 1238$ ), then $9999$ . Adding $1$ turns the last eight into a nine and the four nines into zeros, giving digit sum $1238 + 1 = 1239$ .

The answer is $\boxed{\textbf{(D)}\ 1239}$ .

Why this works

A number and its digit sum always leave the same remainder when divided by $9$ . Carrying can change a digit sum a lot, but only by multiples of $9$ . So checking remainders on division by $9$ quickly rules out impossible digit sums, a handy tool for any digit-sum question.

Alternative approach

Use remainders on division by $9$ directly. The digits of $1275$ add to $15$ , and $15$ leaves remainder $6$ , so $S(n+1)$ must leave remainder $6$ when divided by $9$ . Find each choice's remainder from its digit sum: $1 \to 1$ , $3 \to 3$ , $12 \to 3$ , $1239 \to 15 \to 6$ , $1265 \to 14 \to 5$ . Only $1239$ has remainder $6$ .

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Suppose $n$ ends in exactly $k$ nines ( $k \ge 0$ ). Adding $1$ turns those $k$ nines into zeros and increases the next digit by $1$ , so
$S(n+1) = S(n) + 1 - 9k = 1275 - 9k.$
Hence $S(n+1) \equiv 1275 \pmod 9$ . The digit sum of $1275$ is $15$ , so $1275 \equiv 6 \pmod 9$ , and $S(n+1)$ must leave remainder $6$ when divided by $9$ .

Check the choices by their own digit sums: $1 \to 1$ ; $3 \to 3$ ; $12 \to 3$ ; $1239 \to 15 \to 6$ ; $1265 \to 14 \to 5$ . Only $1239$ is $6 \pmod 9$ .

It is attainable: $1275 - 1239 = 36 = 9 \cdot 4$ , so take $n$ ending in exactly four nines with the remaining digits summing to $1274 - 36 = 1238$ (for example $6$ followed by $154$ eights, then $9999$ ). Then $S(n+1) = 1239$ .

The answer is $\boxed{\textbf{(D)}\ 1239}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 8: Base Numbers
Introduction to Number Theory, Chapter 12: Introduction to Modular Arithmetic
Introduction to Number Theory, Chapter 9: Base Number Arithmetic
Introduction to Number Theory, Chapter 10: Units Digits