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?
一个非负整数序列 $a_1,a_2,\dots$ 由规则 $a_{n+2}=|a_{n+1}-a_n|$（对 $n\geq 1$）定义。若 $a_1=999$，$a_2<999$ 且 $a_{2006}=1$，则 $a_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 odd. 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}}$.
称序列 $(a_n)$ 在 $i$ 处“完成”，若 $i$ 是满足 $a_i=a_{i+1}=1$ 的最小正整数；否则称 $(a_n)$ 不完成。
注意若 $d=\gcd(999,a_2)\neq 1$，则对所有 $n\geq 1$ 都有 $d\mid a_n$，而 $d$ 不整除 $1$，因此当 $\gcd(999,a_2)\neq 1$ 时，$(a_n)$ 不完成。（并且此时 $a_{2006}$ 不可能为 $1$，因为 $d$ 不整除 $1$，所以这些 $a_2$ 不必考虑。）
从现在起，设 $\gcd(999,a_2)=1$。
下面证明 $(a_n)$ 会在某个 $i\leq 2006$ 处完成。我们用 3 个引理。
引理：若 $a_j\neq a_{j+1}$，且两者都不为 $0$，则 $\max(a_j,a_{j+1})>\max(a_{j+2},a_{j+3})$。
证明：分两种情况。
若 $a_j>a_{j+1}$，则 $a_{j+2}=a_j-a_{j+1}$，且 $a_{j+3}=|a_j-2a_{j+1}|$。因此 $a_j>a_{j+2}$ 且 $a_j>a_{j+3}$。
若 $a_j<a_{j+1}$，则 $a_{j+2}=a_{j+1}-a_j$，且 $a_{j+3}=a_j$。因此 $a_{j+1}>a_{j+2}$ 且 $a_{j+1}>a_{j+3}$。
两种情况下都有 $\max(a_j,a_{j+1})>\max(a_{j+2},a_{j+3})$，证毕。
引理：若 $a_i=a_{i+1}$，则 $a_i=1$。此外，若对某个 $i>2$ 有 $a_i=0$，则 $a_{i-1}=a_{i-2}=1$。
证明：由题目中 $(a_n)$ 的构造方式，若出现相邻两项相等 $a_i=a_{i+1}$，则 $a_i$ 整除序列中的每一项。因此 $a_i\mid 999$ 且 $a_i\mid a_2$，从而 $a_i\mid \gcd(999,a_2)=1$，故 $a_i=1$。第二个结论：若 $a_i=0$，则 $a_{i-1}=a_{i-2}$，由刚证得的第一个结论可知 $a_{i-2}=a_{i-1}=1$。
引理：$(a_n)$ 会在某个 $i\leq 2000$ 处完成。
证明：假设 $(a_n)$ 在某个 $i>2000$ 处完成，或根本不完成。则由第二个引理以及 $999$ 与 $a_2$ 都不为 $0$，可知在 $(a_1,a_2),\dots,(a_{1999},a_{2000})$ 这些相邻对中，没有任何一对包含 $0$，也没有任何一对等于 $(1,1)$。于是由第一个引理得到
\[\max(a_1,a_2)>\max(a_3,a_4)>\cdots>\max(a_{1999},a_{2000})>0,\]
从而 $999=\max(a_1,a_2)\geq 1000$，矛盾。故 $(a_n)$ 必在某个 $i\leq 2000$ 处完成。
现在可以确定需要计数的 $a_2$。
注意 $2006\equiv 2\pmod 3$，且 $a_1=999$ 为奇数。分两种情况。
情况 1：若 $a_2$ 为奇数，则 $a_3$ 为偶数，$a_4$ 为奇数，$a_5$ 为奇数，$a_6$ 为偶数，并且由于递推定义，这种模式每三项重复一次，因此 $(a_n)$ 模 $2$ 的序列为
\[1,1,0,1,1,0,\dots\]
所以 $a_{2006}$ 为奇数，从而为 $1$（因为若 $(a_n)$ 在 $i$ 处完成，则对所有 $k\geq i$，$a_k$ 必为 $0$ 或 $1$）。
情况 2：若 $a_2$ 为偶数，则 $a_3$ 为奇数，$a_4$ 为奇数，$a_5$ 为偶数，$a_6$ 为奇数，并且这种模式每三项重复一次，因此 $(a_n)$ 模 $2$ 的序列为
\[1,0,1,1,0,1,\dots\]
所以 $a_{2006}$ 为偶数，从而为 $0$。
因此，$a_{2006}=1$ 当且仅当 $\gcd(999,a_2)=1$ 且 $a_2$ 为奇数。于是我们只需计数满足这些条件的 $a_2$。
小于 $999$ 且与其互素的数共有 $\phi(999)=648$ 个（$\phi$ 为欧拉函数）。我们要数其中有多少是奇数。注意映射
\[t\mapsto 999-t\]
在小于 $999$ 且与 $999$ 互素的奇数与偶数之间建立了一一对应。因此最终答案为 $648/2=324$，即 $\boxed{\text{B}}$。