AMC 10 · 2011 · #17

Grade 11 algebrapattern
Archetype Lattice / Grid Pattern from Small Cases └ Sub-archetype Figure-N Growth Sequence
function-compositionlogarithm-propertiesrecursive-sequencedigit-sum pattern-recognition ↑ Prerequisites: function-composition
📏 Long solution 💡 3 insights
Problem
One composite is applied over and over from a starting value. Add the digits of the result.

Pick an answer.

(A)
16081
(B)
16089
(C)
18089
(D)
18098
(E)
18099
How to solve
Strategy Look for a Pattern

The scary-looking log and power of 10 cancel, so Tool #13 (Convert to Algebra) first collapses h₁ into the plain rule x ↦ 10x-1 and turns the 2011-fold composition into a one-line recursion. Tool #9 (Solve an Easier Related Problem) then runs n=1,2,3,4 to see what the numbers look like. That is where the real work starts: the question asks for a digit sum, so seeing 9, 89, 889 and guessing is not enough — the digit spelling itself has to be proved. Tool #5 (Look for a Pattern) supplies that proof by induction on the digit string, and a closed formula gives a second, independent description of the same number. Tool #3 (Eliminate Possibilities) is held back for the check: a digit sum is pinned down mod 9, and only one answer choice survives that filter.

1STEP 1

Collapse the composition

The composition collapses to one linear rule.

h₁(x)=g(10¹0x)=log₁₀(10¹0x)-1=10x-1
2STEP 2

Turn the tower into a recursion

Repeating it is a plain recursion.

a_n=h_n(1), a₁=9, a_n=10a_n-1-1
3STEP 3

Run the first few terms

The first few terms show a clear pattern.

a₁=9, a₂=89, a₃=889, a₄=8889
4STEP 4

Prove the digit spelling

The recursion proves that spelling continues.

10a_n=8… 8_n-190 ⟹ a_n+1=10a_n-1=8… 8_n9
5STEP 5

Confirm with a closed formula

A closed formula confirms it.

a_n=10ⁿ-(10ⁿ-1)/9=(8 · 10ⁿ+1)/9=8·1… 1_n+1
6STEP 6

Add the digits

Adding the digits gives 16089, choice (B).

8 · 2010+9=16080+9=16089
Answer
16089
Two checks agree. First, size: the number has 2011 digits, each an 8 or a 9, so its digit sum has to sit between 8 · 2011=16088 and 9 · 2011=18099, and hugging the low end is right because only one digit is a 9 — that alone kills 18089 and 18098, which would need hundreds more nines. Second, and sharper, a number is congruent to its own digit sum mod 9, so the answer can be tested without ever spelling out the digits. From a_n=10a_n-1-1 alone, a_n≡ a_n-1-1 (mod 9) with a₁≡ 0, hence a_n≡ 1-n, and a₂₀₁₁≡ 1-2011=-2010≡ 6 (mod 9). The digit sums of the five choices are congruent to 7, 6, 8, 8, 0 mod 9 respectively, so 16089 is the only survivor — confirming (B) by a route that never touches the induction.
💡Key takeaway

Every round is just "times 10, minus 1", which slides the digits over and turns the ending 90 into 89, so the number grows into a wall of 8s with one 9 at the end.

  • Collapse the composition
  • Turn the tower into a recursion
  • Run the first few terms
  • Prove the digit spelling
  • Confirm with a closed formula
  • Add the digits

More like this

Same archetype — closest grade level first.