Question

整数数列 $a_1$ ， $a_2$ ， $\ldots$ 按如下规则确定：若 $a_{n-1}$ 为偶数，则 $a_n = \frac{a_{n-1}}{2}$ ；若 $a_{n-1}$ 为奇数，则 $a_n = 3a_{n-1} + 1$ 。有多少个正整数 $a_1 \le 2008$ 满足 $a_1$ 小于 $a_2$ ， $a_3$ 和 $a_4$ 中的每一个？

Let $a_1,$ $a_2,$ $\ldots$ be a sequence of integers determined by the rule $a_n = \frac{a_{n-1}}{2}$ if $a_{n-1}$ is even and $a_n = 3a_{n-1} + 1$ if $a_{n-1}$ is odd. For how many positive integers $a_1 \le 2008$ is it true that $a_1$ is less than each of $a_2,$ $a_3,$ and $a_4?$

$250$

$251$

$501$

$502$

$1004$

答案：D

知识点：递推模运算分类讨论

难度评级：1870

小提示：

若 $a_1$ 为偶数，则 $a_2 \lt a_1$ ，所以 $a_1$ 必须是奇数。

If $a_1$ is even then $a_2 \lt a_1,$ so $a_1$ must be odd

大提示：

在奇数情形中，按 $a_1 \equiv 1$ 或 $a_1 \equiv 3 \pmod 4$ 分类。

Split the odd case according to whether $a_1 \equiv 1$ or $a_1 \equiv 3 \pmod 4$

解答：

若 $a_1$ 为偶数，则 $a_2 = \frac{a_1}{2} \lt a_1$ ，条件失败。

若 $a_1 \equiv 1 \pmod 4$ ，则 $a_2 = 3a_1 + 1$ 是 $4$ 的倍数， $a_3 = \frac{3a_1 + 1}{2}$ ，且 $a_4 = \frac{3a_1 + 1}{4} \le a_1$ ，条件也失败。

若 $a_1 \equiv 3 \pmod 4$ ，则 $a_2$ 为偶数但不是 $4$ 的倍数，所以 $a_3 = \frac{3a_1 + 1}{2} \gt a_1$ ，且 $a_3$ 为奇数， $a_4 = 3a_3 + 1 \gt a_3 \gt a_1$ 。此时条件成立。

满足条件的 $a_1 \le 2008$ 且 $a_1 \equiv 3 \pmod 4$ 的数恰有 $\tfrac{2008}{4} = 502$ 个。

所以正确答案是 D。

If $a_1$ is even, then $a_2 = \frac{a_1}{2} \lt a_1,$ so the condition fails.

If $a_1 \equiv 1 \pmod 4,$ then $a_2 = 3a_1 + 1$ is a multiple of $4,$ so $a_3 = \frac{3a_1 + 1}{2}$ and $a_4 = \frac{3a_1 + 1}{4} \le a_1,$ and again the condition fails.

If $a_1 \equiv 3 \pmod 4,$ then $a_2$ is even but not a multiple of $4,$ so $a_3 = \frac{3a_1 + 1}{2} \gt a_1,$ and $a_3$ is odd, giving $a_4 = 3a_3 + 1 \gt a_3 \gt a_1.$ The condition holds.

Exactly $\tfrac{2008}{4} = 502$ values of $a_1 \le 2008$ satisfy $a_1 \equiv 3 \pmod 4.$

Thus, D is the correct answer.

2008 AMC 12A 第 17 题

答案：D

难度评级：1870

小提示：

大提示：

解答：

其他年份的第 17 题