AMC 10 · 2007 · #25

Grade 4 arithmetic

Archetype Small-Domain Constrained Search └ Sub-archetype Sum-Target Search

digit-sumcaseworkmodular-arithmeticbound-inequality-then-enumerate caseworkbound-inequality-then-enumerate ↑ Prerequisites: digit-sum

📏 Long solution 💡 4 insights

📘 View easy version →

Problem

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

Pick an answer.

(A)

$\ 1$

(B)

$\ 2$

(C)

$\ 3$

(D)

$\ 4$

(E)

$\ 5$

AMC 10 2007 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

Try it yourself first — the explanation is most useful after you’ve attempted it.

View mode:

Toolkit + CCSS Solution

Understand

Restated: For a positive integer $n$, let $S(n)$ be the sum of its digits, and apply $S$ again to get $S(S(n))$. Count how many $n$ make $n + S(n) + S(S(n))$ exactly equal to $2007$.

Givens: $S(n)$ is the sum of the digits of $n$; $S(S(n))$ is the digit sum of that digit sum; The equation to satisfy is $n + S(n) + S(S(n)) = 2007$; $n$ ranges over positive integers; Answer choices: (A) $1$, (B) $2$, (C) $3$, (D) $4$, (E) $5$

Unknowns: The number of positive integers $n$ that satisfy the equation

Understand

Restated: For a positive integer $n$, let $S(n)$ be the sum of its digits, and apply $S$ again to get $S(S(n))$. Count how many $n$ make $n + S(n) + S(S(n))$ exactly equal to $2007$.

Plan

Primary tool: #14 Extreme Principle

Secondary: #16 Change Focus / Count the Complement, #2 Make a Systematic List

There are infinitely many positive integers, so Tool #14 (Extreme Principle) first traps $n$ in a tiny window: the two extra terms $S(n)+S(S(n))$ can never be large, so $n$ must sit just below $2007$. That leaves only a few dozen candidates. Tool #16 (Change Focus) then looks at the problem through remainders when dividing by $9$; the digit-sum rule forces $n$ to be a multiple of $3$, cutting the candidates by two thirds. Finally Tool #2 (Make a Systematic List) walks the surviving multiples of $3$ in order, computing $n + S(n) + S(S(n))$ for each and counting the hits.

Execute — Answer: D

#14 Extreme Principle 4.NBT.B.4 Step 1

Trap $n$ in a small window

Since $S(n)$ and $S(S(n))$ are both positive, $n < 2007$.
Now bound how big those two terms can be.
For any $n$ below $2007$, the digits are at most $1,9,9,9$, so $S(n) \le 28$.
Then $S(n)$ is at most $28$, whose digit sum is at most $10$, so $S(S(n)) \le 10$.
Hence $S(n) + S(S(n)) \le 38$.
Rearranging the equation, $n = 2007 - S(n) - S(S(n)) \ge 2007 - 38 = 1969$.
So every solution satisfies $1969 \le n \le 2006$.

$$S(n)+S(S(n)) \le 28+10 = 38 \;\Rightarrow\; n = 2007 - S(n) - S(S(n)) \ge 1969, \quad\text{so } 1969 \le n \le 2006$$

💡 Digit sums stay tiny, so $n$ can only be a short step below $2007$.

#16 Change Focus / Count the Complement 4.NBT.B.6 Step 2

Keep only multiples of $3$

A number leaves the same remainder as its digit sum when divided by $9$, because $10, 100, 1000$ are each one more than a multiple of $9$.
So $n$, $S(n)$, and $S(S(n))$ all leave the same remainder $r$ when divided by $9$.
Their total then leaves remainder $r + r + r = 3r$.
We need the total to be $2007$, and $2007 = 9 \times 223$ leaves remainder $0$.
So $3r$ must be a multiple of $9$, which means $r$ is a multiple of $3$.
A number whose remainder mod $9$ is a multiple of $3$ is exactly a multiple of $3$.
So $n$ must be a multiple of $3$.

$$n \equiv S(n) \equiv S(S(n)) \equiv r \pmod 9 \;\Rightarrow\; 3r \equiv 2007 \equiv 0 \pmod 9 \;\Rightarrow\; 3 \mid r \;\Rightarrow\; 3 \mid n$$

💡 Each term carries the same leftover mod $9$, so their triple sum can only reach a multiple of $9$ when $n$ is a multiple of $3$.

#2 Make a Systematic List 4.NBT.A.2 Step 3

Test each surviving candidate

List the multiples of $3$ from $1971$ up to $2004$ and compute $n + S(n) + S(S(n))$ for each.
$1971 \to 1971+18+9 = 1998$.
$1974 \to 1974+21+3 = 1998$.
$1977 \to 1977+24+6 = 2007$.
$1980 \to 1980+18+9 = 2007$.
$1983 \to 1983+21+3 = 2007$.
$1986 \to 1986+24+6 = 2016$.
$1989 \to 1989+27+9 = 2025$.
$1992 \to 1992+21+3 = 2016$.
$1995 \to 1995+24+6 = 2025$.
$1998 \to 1998+27+9 = 2034$.
$2001 \to 2001+3+3 = 2007$.
$2004 \to 2004+6+6 = 2016$.

$$1977,\,1980,\,1983,\,2001 \;\rightarrow\; 2007 \quad(\text{all others miss})$$

💡 With the window this small, a direct place-by-place check of each multiple of $3$ settles the count for sure.

#2 Make a Systematic List 4.OA.B.4 Step 4

Count the hits

Exactly four candidates hit $2007$: $n = 1977$, $1980$, $1983$, and $2001$.
No others in the window work, and the window contains every possible solution.
So there are $4$ values of $n$.
The answer is (D).

$$n \in \{1977,\,1980,\,1983,\,2001\} \;\Rightarrow\; 4 \text{ values} \;\Rightarrow\; \textbf{(D)}$$

💡 Four numbers survive every filter and every check, so the count is four.

[1] #14 4.NBT.B.4 Since $S(n)$ and $S(S(n))$ are both positive, $n < 2007$. Now bound how big thos

[2] #16 4.NBT.B.6 A number leaves the same remainder as its digit sum when divided by $9$, because

[3] #2 4.NBT.A.2 List the multiples of $3$ from $1971$ up to $2004$ and compute $n + S(n) + S(S(n

[4] #2 4.OA.B.4 Exactly four candidates hit $2007$: $n = 1977$, $1980$, $1983$, and $2001$. No o

Review

Reasonableness: Spot-check the four winners by hand. $1977$: digits sum to $1+9+7+7 = 24$, and $2+4 = 6$, giving $1977+24+6 = 2007$. $2001$: digits sum to $3$, and $S(3)=3$, giving $2001+3+3 = 2007$. Both check out. The four solutions land in two natural clusters ($1977$–$1983$ and the lone $2001$), consistent with the digit sums jumping around as $n$ crosses from the $1900$s into the $2000$s. Four is one of the offered choices and matches the multiple-of-$3$ pattern, so (D) is consistent.

Alternative: Skip the mod-$9$ shortcut and brute-force the window directly. Since $1969 \le n \le 2006$ is only $38$ numbers, one can simply compute $n + S(n) + S(S(n))$ for every $n$ in that range. The same four values — $1977, 1980, 1983, 2001$ — turn up, confirming the count without the divisibility argument; the mod-$9$ filter just saves about two thirds of the arithmetic.

CCSS standards used (min grade 4)

4.NBT.B.4 Fluently add and subtract multi-digit whole numbers (Bounding $n$ between $1969$ and $2006$ from $2007 - S(n) - S(S(n))$.)
4.NBT.B.6 Find whole-number quotients and remainders with up to four-digit dividends (Using remainders mod $9$ and the digit-sum rule to force $n$ to be a multiple of $3$.)
4.NBT.A.2 Read and write multi-digit whole numbers using base-ten numerals and expanded form (Computing each digit sum $S(n)$ and $S(S(n))$ for the candidate numbers.)
4.OA.B.4 Find all factor pairs for a whole number and recognize multiples (Restricting candidates to multiples of $3$ and counting the four that work.)

⭐ Because digit sums are tiny, $n$ must sit just below $2007$; checking that short list of multiples of $3$ leaves exactly four winners.

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: D

Trap $n$ in a small window

Keep only multiples of $3$

Test each surviving candidate

Count the hits

Review

CCSS standards used (min grade 4)

More like this