2007 AMC 10A Problem 25

P21-25~8 minPrint

Bases & Digits Modular Arithmetic Bound the quantity above/below or estimate to pin it down Organized listing / direct enumeration

For each positive integer $n$ , let $S(n)$ denote the sum of the digits of $n.$ For how many values of $n$ is $n + S(n) + S(S(n)) = 2007?$

Show solution without answering

Key insight

Digit sums are small, so n must be between 1969 and 2007. A remainder argument with 9 shows n is a multiple of 3, leaving 13 numbers to test.

Solution

The digit sums are tiny compared with $n$ , so $n$ must be close to $2007$ . First find how close, then shrink the list, then test.

Step 1: $n$ is at least $1969$ .

$n$ is less than $2007$ . Among such numbers, the largest digit sum is $S(1999) = 1 + 9 + 9 + 9 = 28$ .
So $S(n)$ is at most $28$ . Among numbers up to $28$ , the largest digit sum is $S(19) = 10$ . So $S(S(n))$ is at most $10$ .
Therefore $n = 2007 - S(n) - S(S(n)) \ge 2007 - 28 - 10 = 1969$ .

Step 2: $n$ must be a multiple of $3$ .

A number and its digit sum leave the same remainder when divided by $9$ . (For example, $1977$ and $1 + 9 + 7 + 7 = 24$ both leave remainder $6$ .) So $n$ , $S(n)$ and $S(S(n))$ all leave the same remainder; call it $r$ .
Then $n + S(n) + S(S(n))$ leaves the same remainder as $3r$ . This sum is $2007$ , and $2007 = 9 \times 223$ is a multiple of $9$ . So $3r$ must be a multiple of $9$ , which means $r$ is $0$ , $3$ or $6$ . In every case $n$ is a multiple of $3$ .

Step 3: test the multiples of $3$ from $1971$ to $2007$ .

$n$	1971	1974	1977	1980	1983	1986	1989	1992	1995	1998	2001	2004	2007
$S(n)$	18	21	24	18	21	24	27	21	24	27	3	6	9
$S(S(n))$	9	3	6	9	3	6	9	3	6	9	3	6	9
total	1998	1998	2007	2007	2007	2016	2025	2016	2025	2034	2007	2016	2025

The total is $2007$ for $n = 1977, 1980, 1983$ and $2001$ : four values.

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

Why this works

Digit-sum problems use two tools. First, a digit sum is small (at most $9$ for each digit), which squeezes $n$ into a short range. Second, a number and its digit sum leave the same remainder when divided by $9$ , which removes most of that range. What is left is short enough to check by hand.

Alternative approach

Skip Step 2 and test every $n$ from $1969$ to $2007$ . That is $39$ numbers, but they go quickly in groups of ten, because the digit sum goes up by $1$ each time until the last digit rolls over. You find the same four values; the multiple-of- $3$ filter just saves time.

Concise solution

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

Bound the search. Since $n < 2007$ , $n$ has at most four digits with the leading one at most $2$ ; the largest digit sum available is $S(1999) = 28$ , and then $S(S(n)) \le S(28) = 10$ (in fact at most $10$ for any $S(n) \le 28$ ). So
$n = 2007 - S(n) - S(S(n)) \ge 2007 - 28 - 10 = 1969.$

Filter by $9$ . A number is congruent to its digit sum modulo $9$ , so $n \equiv S(n) \equiv S(S(n)) \pmod 9$ . The equation gives $3n \equiv 2007 \equiv 0 \pmod 9$ , hence $n \equiv 0 \pmod 3$ .

That leaves the multiples of $3$ from $1971$ to $2007$ , thirteen candidates. Compute $n + S(n) + S(S(n))$ for each:

$n$	1971	1974	1977	1980	1983	1986	1989	1992	1995	1998	2001	2004	2007
$S(n)$	18	21	24	18	21	24	27	21	24	27	3	6	9
$S(S(n))$	9	3	6	9	3	6	9	3	6	9	3	6	9
total	1998	1998	2007	2007	2007	2016	2025	2016	2025	2034	2007	2016	2025

Exactly four values work: $n = 1977, 1980, 1983, 2001$ .

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

Review in the AoPS books

Introduction to Number Theory, Chapter 8: Base Numbers
Introduction to Number Theory, Chapter 12: Introduction to Modular Arithmetic
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.2)
Introduction to Number Theory, Chapter 9: Base Number Arithmetic