Question

非负整数序列 $a_1$ ， $a_2$ ， $\ldots$ 由规则 $a_{n+2} = |a_{n+1} - a_n|$ （ $n \ge 1$ ）定义。若 $a_1 = 999$ 、 $a_2 \lt 999$ ，且 $a_{2006} = 1$ ，那么 $a_2$ 可能有多少个不同的值？

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$

答案：B

知识点：最大公约数奇偶性容斥原理

难度评级：2520

小提示：

$a_n$ 和 $a_{n+3}$ 总是同奇偶；结合 $a_{2006} = 1$ 使用这一点。

The terms $a_n$ and $a_{n+3}$ always share the same parity; use this with $a_{2006} = 1$

大提示：

每一项都是 $\gcd(a_1, a_2)$ 的倍数，所以 $\gcd(999, a_2) = 1$ ；注意 $999 = 3^3 \cdot 37$ 。

Every term is a multiple of $\gcd(a_1, a_2),$ so $\gcd(999, a_2) = 1;$ note $999 = 3^3 \cdot 37$

解答：

递推规则给出 $a_n \equiv a_{n+3} \pmod 2$ ，所以 $a_2$ 与 $a_{2006} = 1$ 的奇偶性相同，因此 $a_2$ 是奇数。

每一项都是 $\gcd(a_1, a_2)$ 的倍数，而 $a_{2006} = 1$ 迫使 $\gcd(999, a_2) = 1$ 。因为 $999 = 3^3 \cdot 37$ ，所以 $a_2$ 不能被 $3$ 或 $37$ 整除。

区间 $[1, 998]$ 中有 $499$ 个奇数；去掉 $166$ 个 $3$ 的倍数和 $13$ 个 $37$ 的倍数，再加回 $4$ 个 $111$ 的倍数，得到 $499 - 166 - 13 + 4 = 324\text{。}$

每个这样的 $a_2$ 都可行。对连续正项 $u,v$ ，更新 $(u,v)\mapsto(v,|v-u|)$ 至多每两步就会减小两者的最大值。因为初始两项都不超过 $999$ ，所以某个 $a_N=0$ 会在 $N\le1999$ 时出现。

每对连续项的最大公因数不变，所以零之前的两个相等项都等于 $\gcd(999,a_2)=1$ 。此后序列循环经过 $1,1,0$ 。最后， $2006\equiv2\pmod3$ ，所以 $a_{2006}$ 与 $a_2$ 同为奇数；在这个循环中，它必定为 $1$ 。

所以正确答案是 B。

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. For consecutive positive terms $u,v,$ the update $(u,v)\mapsto(v,|v-u|)$ reduces their maximum within at most two steps. Since both initial terms are at most $999,$ some $a_N=0$ occurs by $N\le1999.$

The gcd of each consecutive pair is invariant, so the equal terms immediately before that zero both equal $\gcd(999,a_2)=1.$ The sequence then cycles through $1,1,0.$ Finally, $2006\equiv2\pmod3,$ so $a_{2006}$ has the same odd parity as $a_2;$ in this cycle it must therefore be $1.$

Thus, the correct answer is B.

2006 AMC 12B 第 25 题

答案：B

难度评级：2520

小提示：

大提示：

解答：

其他年份的第 25 题