Question

A sequence $a_1, a_2, \ldots$ of non-negative integers is defined by the rule $a_{n+2} = |a_{n+1} - a_n|$ for $n \ge 1.$ If $a_1 = 999,$ $a_2 \lt 999,$ and $a_{2006} = 1,$ how many different values of $a_2$ are possible?

$165$

$324$

$495$

$499$

$660$

Solution:

The rule gives $a_n \equiv a_{n+3} \pmod 2,$ so $a_2$ has the same parity as $a_{2006} = 1;$ thus $a_2$ is odd.

Every term is a multiple of $\gcd(a_1, a_2),$ and $a_{2006} = 1$ forces $\gcd(999, a_2) = 1.$ Since $999 = 3^3 \cdot 37,$ we need $a_2$ not divisible by $3$ or $37.$

Among the odd integers in $[1, 998]$ there are $499;$ removing the $166$ multiples of $3$ and $13$ multiples of $37,$ then adding back the $4$ multiples of $111,$ leaves $499 - 166 - 13 + 4 = 324.$

Each such $a_2$ works: with $\gcd(a_1, a_2) = 1$ the sequence eventually cycles through $1, 1, 0,$ and the parity condition makes $a_{2006} = 1.$

Thus, the correct answer is B.

2006 AMC 12B Problem 25

Solution:

Problem 25 in Other Years