2006 AMC 12B Problems/Problem 25

Problem

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

$\mathrm{(A)}\ 165 \qquad \mathrm{(B)}\ 324 \qquad \mathrm{(C)}\ 495 \qquad \mathrm{(D)}\ 499 \qquad \mathrm{(E)}\ 660$

Solution 1

Define $g:= \gcd(999,a_2)$ ; then $g\mid a_3$ , and, by induction, $g\mid a_k$ for all $k>0$ . Since $a_{2006}=1$ , we have $g=1$ , i.e. $a_2$ is in the set, $S$ , of positive integers less than $999$ and relatively prime to $999$ . We have $|S|=\varphi(999)=648$ . Moreover, $a_2$ must be odd, because if $a_2$ is even, then every third term after $a_2$ will be even; in particular, $2006\equiv 2\pmod 3$ , so $a_{2006}$ must be even, which is not the case. The subset of odd integers in $S$ (denoted $S_{\textrm{o}}$ ) is in $1$ -- $1$ correspondence with the subset of even integers in $S$ via $x \mapsto 999 - x$ ; so $a_2\in S_{\textrm{o}}$ with $|S_{\textrm{o}}|=324$ .

We will now show that $a_{2006}=1$ whenever $a_2\in S_{\textrm{o}}$ . Suppose $a_2\in S$ is odd, and define $M_i=\max(a_{i}, a_{i+1})$ and $m_i=\min(a_{i}, a_{i+1})$ .

Since $a_{i+1}=M_{i-1}-m_{i-1} \le M_{i-1}$ , we have $M_i \le M_{i-1}$ for all $i>0$ . In fact, as long as $a_j\neq 0$ for $j\le i$ , we have $a_{i+1}< M_{i-1}$ and it follows that $M_{i+1} < M_{i-1}$ . Then $M_1=999$ , $M_3\le 998$ , $M_5\le 997$ , and, in general, $M_{2k+1}\le 999-k$ . This implies that $m_k=0$ for some $k< 2000$ , i.e. $a_k=0$ for some $k\le 2000$ . If $a_k=0$ then $a_{k-2}=a_{k-1}=a$ (say), and it follows that $a\mid a_{k-3}$ , and, by induction, $a\mid a_j$ for all $j=1,2,\ldots , k-1$ . Then $a\mid \gcd(999,a_2)=1$ , so $a=1$ . Therefore, the sub-sequence $\{a_i\}_{i\ge k-2}$ $(k\le 2000)$ will be $1, 1, 0, 1, 1, 0, \ldots$ In particular, $a_{2006}$ will be either $0$ or $1$ ; but since $a_2$ is odd, every third term after $a_2$ will be odd, so $a_{2006}$ must be odd, so it must equal $1$ . We have shown that $a_2\in S_{\textrm{o}}$ implies $a_{2006}=1$ . So our final answer is $|S_{\textrm{o}}|=324$ , or $\boxed{\text{B}}$ .

Solution 2

We say the sequence $(a_n)$ completes at $i$ if $i$ is the minimal positive integer such that $a_i = a_{i + 1} = 1$ . Otherwise, we say $(a_n)$ does not complete.

Note that if $d = \gcd(999, a_2) \neq 1$ , then $d|a_n$ for all $n \geq 1$ , and $d$ does not divide $1$ , so if $\gcd(999, a_2) \neq 1$ , then $(a_n)$ does not complete. (Also, $a_{2006}$ cannot be 1 in this case since $d$ does not divide $1$ , so we do not care about these $a_2$ at all.)

From now on, suppose $\gcd(999, a_2) = 1$ .

We will now show that $(a_n)$ completes at $i$ for some $i \leq 2006$ . We will do this with 3 lemmas.

Lemma: If $a_j \neq a_{j + 1}$ , and neither value is $0$ , then $\max(a_j, a_{j + 1}) > \max(a_{j + 2}, a_{j + 3})$ .

Proof: There are 2 cases to consider.

If $a_j > a_{j + 1}$ , then $a_{j + 2} = a_j - a_{j + 1}$ , and $a_{j + 3} = |a_j - 2a_{j + 1}|$ . So $a_j > a_{j + 2}$ and $a_j > a_{j + 3}$ .

If $a_j < a_{j + 1}$ , then $a_{j + 2} = a_{j + 1} - a_j$ , and $a_{j + 3} = a_j$ . So $a_{j + 1} > a_{j + 2}$ and $a_{j + 1} > a_{j + 3}$ .

In both cases, $\max(a_j, a_{j + 1}) > \max(a_{j + 2}, a_{j + 3})$ , as desired.

Lemma: If $a_i = a_{i + 1}$ , then $a_i = 1$ . Moreover, if instead we have $a_i = 0$ for some $i > 2$ , then $a_{i - 1} = a_{i - 2} = 1$ .

Proof: By the way $(a_n)$ is constructed in the problem statement, having two equal consecutive terms $a_i = a_{i + 1}$ implies that $a_i$ divides every term in the sequence. So $a_i | 999$ and $a_i | a_2$ , so $a_i | \gcd(999, a_2) = 1$ , so $a_i = 1$ . For the proof of the second result, note that if $a_i = 0$ , then $a_{i - 1} = a_{i - 2}$ , so by the first result we just proved, $a_{i - 2} = a_{i - 1} = 1$ .

Lemma: $(a_n)$ completes at $i$ for some $i \leq 2000$ .

Proof: Suppose $(a_n)$ completed at some $i > 2000$ or not at all. Then by the second lemma and the fact that neither $999$ nor $a_2$ are $0$ , none of the pairs $(a_1, a_2), ..., (a_{1999}, a_{2000})$ can have a $0$ or be equal to $(1, 1)$ . So the first lemma implies $\max(a_1, a_2) > \max(a_3, a_4) > \cdots > \max(a_{1999}, a_{2000}) > 0,$ so $999 = \max(a_1, a_2) \geq 1000$ , a contradiction. Hence $(a_n)$ completes at $i$ for some $i \leq 2000$ .

Now we're ready to find exactly which values of $a_2$ we want to count.

Let's keep in mind that $2006 \equiv 2 \pmod 3$ and that $a_1 = 999$ is odd. We have two cases to consider.

Case 1: If $a_2$ is odd, then $a_3$ is even, so $a_4$ is odd, so $a_5$ is odd, so $a_6$ is even, and this pattern must repeat every three terms because of the recursive definition of $(a_n)$ , so the terms of $(a_n)$ reduced modulo 2 are $1, 1, 0, 1, 1, 0, ...,$ so $a_{2006}$ is odd and hence $1$ (since if $(a_n)$ completes at $i$ , then $a_k$ must be $0$ or $1$ for all $k \geq i$ ).

Case 2: If $a_2$ is even, then $a_3$ is odd, so $a_4$ is odd, so $a_5$ is even, so $a_6$ is odd, and this pattern must repeat every three terms, so the terms of $(a_n)$ reduced modulo 2 are $1, 0, 1, 1, 0, 1, ...,$ so $a_{2006}$ is even, and hence $0$ .

We have found that $a_{2006} = 1$ is true precisely when $\gcd(999, a_2) = 1$ and $a_2$ is odd. This tells us what we need to count.

There are $\phi(999) = 648$ numbers less than $999$ and relatively prime to it ( $\phi$ is the Euler totient function). We want to count how many of these are even. Note that $t \mapsto 999 - t$ is a 1-1 correspondence between the odd and even numbers less than and relatively prime to $999$ . So our final answer is $648/2 = 324$ , or $\boxed{\text{B}}$ .

2006 AMC 12B (Problems • Answer Key • Resources)
Preceded by Problem 24	Followed by Last Question
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

Page

Toolbox

Search

2006 AMC 12B Problems/Problem 25

Contents

Problem

Solution 1

Solution 2

See also