Question

对每个正整数 $n$ ，令 $S(n)$ 表示只由字母 $A$ 和 $B$ 组成、长度为 $n$ 的序列数，其中连续的 $A$ 不超过三个，连续的 $B$ 也不超过三个。 $S(2015)$ 除以 $12$ 的余数是多少？

For each positive integer $n,$ let $S(n)$ be the number of sequences of length $n$ consisting solely of the letters $A$ and $B,$ with no more than three $A$ s in a row and no more than three $B$ s in a row. What is the remainder when $S(2015)$ is divided by $12?$

$0$

$4$

$6$

$8$

$10$

答案：D

知识点：递推计数模运算中国剩余定理

难度评级：2270

解答：

注意 $S(1) = 2$ ， $S(2) = 4$ ， $S(3) = 8$ 。每个合法序列都以一段长度为一、二或三的同字母段结尾；去掉这段后，剩下长度为 $n-1$ ， $n-2$ ，或 $n-3$ 的合法序列。 $\begin{aligned} &S(n) = S(n-1) + S(n-2) \\ &\quad {}+ S(n-3). \end{aligned}$

因此模 $3$ 时，序列 $2,1,2$ 的周期为 $13$ 。因为 $2015 = 13\cdot 155$ ， $S(2015) \equiv S(13) \equiv 2 \pmod 3$ 。 $13$ 。 $2,1,2,2,2,0,1,0,1,2,0,0,2.$

模 $4$ 时，它的周期为 $4$ ，且 $2015 = 4\cdot 503 + 3$ ，所以 $S(2015) \equiv S(3) \equiv 0 \pmod 4$ 。 $2,0,0,2$ ， $(2,0,0)$ 。

写 $S(2015) = 4k$ ，条件 $4k \equiv 2 \pmod 3$ 给出 $k \equiv 2 \pmod 3$ ，因此 $S(2015) \equiv 8 \pmod{12}$ 。

因此，正确答案是 D。

Note $S(1) = 2,$ $S(2) = 4,$ $S(3) = 8.$ Every valid sequence ends in a run of one, two, or three equal letters; removing that run leaves a valid sequence of length $n-1,$ $n-2,$ or $n-3.$ Thus $\begin{aligned} &S(n) = S(n-1) + S(n-2) \\ &\quad {}+ S(n-3). \end{aligned}$

Modulo $3,$ the first $13$ terms are $2,1,2,2,2,0,1,0,1,2,0,0,2.$ The next three terms are $2,1,2,$ which reproduce the initial state, so the recurrence repeats with period $13.$ Since $2015 = 13\cdot 155,$ it follows that $S(2015) \equiv S(13) \equiv 2 \pmod 3.$

Modulo $4,$ the terms repeat as $2,0,0,2,$ because the next three-term state after these four terms is again $(2,0,0).$ Thus the period is $4.$ As $2015 = 4\cdot 503 + 3,$ we have $S(2015) \equiv S(3) \equiv 0 \pmod 4.$

Writing $S(2015) = 4k,$ the condition $4k \equiv 2 \pmod 3$ gives $k \equiv 2 \pmod 3,$ so $S(2015) \equiv 8 \pmod{12}.$

Thus, the correct answer is D.

2015 AMC 12A 第 22 题

答案：D

难度评级：2270

解答：

其他年份的第 22 题