AMC 10 · 2007 · #25

Grade 4 number-theory

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

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.

How to solve

Strategy Extreme Principle

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.

1STEP 1

Trap n in a small window

Both extra terms are positive, so n is below 2007; digits at most 1,9,9,9 give S(n) ≤ 28 and S(S(n)) ≤ 10, hence n ≥ 1969.

S(n)+S(S(n)) ≤ 28+10 = 38 → n = 2007 - S(n) - S(S(n)) ≥ 1969, so 1969 ≤ n ≤ 2006

2STEP 2

Keep only multiples of 3

All three terms leave the same remainder r mod 9, so the total leaves 3r; since 2007 is a multiple of 9, n must be a multiple of 3.

n ≡ S(n) ≡ S(S(n)) ≡ r (mod 9) → 3r ≡ 2007 ≡ 0 (mod 9) → 3 ∣ r → 3 ∣ n

3STEP 3

Test each surviving candidate

Sweep the multiples of 3 from 1971 to 2004, adding n + S(n) + S(S(n)): only 1977, 1980, 1983, 2001 land on 2007.

1977, 1980, 1983, 2001 → 2007 (all others miss)

4STEP 4

Count the hits

The window holds every possible solution, and exactly four of its numbers work: 1977, 1980, 1983, 2001. The answer is (D).

n ∈ {1977, 1980, 1983, 2001} → 4 values → (D)

Answer

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 1900s into the 2000s. Four is one of the offered choices and matches the multiple-of-3 pattern, so (D) is consistent.

💡Key takeaway

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

Trap n in a small window
Keep only multiples of 3
Test each surviving candidate
Count the hits

Trap n in a small window

Keep only multiples of 3

Test each surviving candidate

Count the hits

More like this