AMC 10 · 2006 · #25

Grade 8 number-theorypattern

Archetype Branching State Enumeration └ Sub-archetype Rule-Governed Process Simulation

recursive-sequencegcdparitymodular-arithmetic invariant-monovariantpattern-recognition ↑ Prerequisites: gcdrecursive-sequence

📏 Long solution 💡 4 insights

Problem

A list starts at 999 and a second value, and each later term is the positive difference of the two before it. Count the starting values that make the 2006th term equal one.

Pick an answer.

(A)

165

(B)

324

(C)

495

(D)

499

(E)

660

How to solve

Strategy Look for a Pattern

Term 2006 is unreachable by direct computation, so the plan is to find quantities that do not change (or change only in one direction) as the list runs. Tool #15 says to look at the same list two different ways: through the greatest common divisor of neighbouring terms, and through its remainders modulo 2. The first never changes at all; the second cycles with period 3, and 2006's remainder on division by 3 is what the whole problem hangs on. Those two views together rule out most starting values. But ruling out is only half the job: a starting value that survives both tests still has to actually arrive at 1 before term 2006, and nothing so far says it does. That gap is closed by Tool #14 (Extreme Principle): watch the largest of two neighbouring terms and show it must strictly drop every two steps, so it cannot keep dropping past 999 times. Tool #16 turns the final count into a count of numbers sharing no factor with 999, and Tool #9 checks the whole characterization on a miniature version with 999 replaced by 9.

1STEP 1

Watch one list grind down

One example shows the list grinds down into a repeating block.

a₂=4: 999, 4, 995, 991, 4, 987, 983, 4, … ; c, c → c, c, 0, c, c, 0, … forever

2STEP 2

The shared factor never changes

The rule leaves the shared factor unchanged forever.

gcd(a_n+1,|a_n+1-a_n|)=gcd(a_n+1,a_n) → g=gcd(999,a₂) for all n ; g ∣ a₂₀₀₆=1 → gcd(999,a₂)=1, 999=3³ · 37

3STEP 3

Even and odd repeat every three

Parity repeats every three terms, deciding the target term.

a₂ odd: 1,1,0,1,1,0,… (mod 2) → a₂₀₀₆ odd ; a₂ even: 1,0,1,1,0,1,… (mod 2) → a₂₀₀₆ even ; 2006=3 · 668+2

4STEP 4

Name the gap that is left

So far only one direction is proved, leaving a gap.

proved: a₂₀₀₆=1 → (gcd(999,a₂)=1 and a₂ odd) ; still needed: (gcd(999,a₂)=1 and a₂ odd) → a₂₀₀₆=1

5STEP 5

The bigger of two neighbours must fall

The larger of two neighbours must fall, so the list cannot stall forever.

a_j ＞ a_j+1 ＞ 0: a_j+2=a_j-a_j+1, a_j+3=|a_j-2a_j+1| → max(a_j+2,a_j+3) ＜ a_j ; a_j+1 ＞ a_j ＞ 0: a_j+2=a_j+1-a_j, a_j+3=a_j → max(a_j+2,a_j+3) ＜ a_j+1 ; 999=M₁ ＞ M₂ ＞ … ＞ M₁₀₀₀ → M₁₀₀₀ ≤ 0, impossible

6STEP 6

Close the gap and reach 1

That closes the gap and the list really reaches one.

a_i=a_i+1=c → c=gcd(a_i,a_i+1)=g=1 ; a_j=0, j ≥ 3 → a_j-2=a_j-1=1 ; ∃ i ≤ 1997: a_i=a_i+1=1 → a₂₀₀₆∈{0,1}, and odd → a₂₀₀₆=1

7STEP 7

Count odd numbers coprime to 999

Counting the coprime odd values gives 648.

a₂ odd and gcd(a₂,999)=1⇔ gcd(a₂,1998)=1, 1998=2 · 3³ · 37 ; φ(1998)=φ(2) φ(27) φ(37)=1 · 18 · 36=648

8STEP 8

Fold the range in half

Folding the range in half gives 324, choice (B).

x⟼ 1998-x is a fixed-point-free involution on the 648 numbers, swapping [1,998] with [1000,1997] ; 648/2=324 → (B)

Answer

324

The claim being counted is an exact characterization — a₂₀₀₆=1 if and only if a₂ is odd and gcd(a₂,999)=1 — so it deserves testing from both sides. Shrink the problem (Tool #9): replace 999 by 9 and keep an index ≡ 2 (mod 3). The characterization predicts the working starts are the odd numbers below 9 coprime to 9, namely 1,5,7, i.e. φ(9)/2=3 of them; running the list confirms exactly {1,5,7} work. The same test with 999 replaced by 27 predicts and delivers {1,5,7,11,13,17,19,23,25}, and with 15 predicts and delivers {1,7,11,13}. Second, the count itself can be redone without any totient: among {1,…,998} there are 499 odd numbers; of those, 166 are multiples of 3 (the odd multiples 3,9,…,993) and 13 are multiples of 37 (the odd multiples 37,111,…,925), and 4 are multiples of both (the odd multiples of 111: 111,333,555,777). Inclusion-exclusion gives 499-166-13+4=324, matching. Third, and most important, the index bound in step 5 is genuinely load-bearing rather than a formality: the slowest survivor is a₂=1, whose list is 999,1,998,997,1,996,995,1,… and which does not reach 1,1 until index 1498. So 2006 is large enough with room to spare, but not by a huge margin — if the problem had asked for a₁₀₁=1 (also an index ≡ 2 (mod 3)), only 301 of the 324 would qualify, and the parity-plus-gcd argument alone would give the wrong count. Finally, the distractors are exactly the shortcuts: 499 is the count of odd a₂ if you forget the gcd condition, and φ(999)=648 is the count of coprime a₂ if you forget parity — 324 is half of it, which is the right size for a condition that keeps roughly one a₂ in three.

💡Key takeaway

When a list is defined by a rule you cannot follow all the way, look for something that never changes (here the shared factor of neighbours) and something that can only shrink (here the bigger of two neighbours) — together they tell you where term 2006 has to be.

Watch one list grind down
The shared factor never changes
Even and odd repeat every three
Name the gap that is left
The bigger of two neighbours must fall
Close the gap and reach 1
Count odd numbers coprime to 999
Fold the range in half