2007 AMC 10A Problem 25

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$.

1. $n$ is less than $2007$. Among such numbers, the largest digit sum is $S(1999) = 1 + 9 + 9 + 9 = 28$.
2. 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$.
3. Therefore $n = 2007 - S(n) - S(S(n)) \ge 2007 - 28 - 10 = 1969$.

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

1. 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$.
2. 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$.

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

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

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.

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.

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:

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

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