AMC12 2015 A

AMC12 2015 A · Q22

AMC12 2015 A · Q22. It mainly tests Recursion & DP style counting (basic), Remainders & modular arithmetic.

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$?

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

(A) 0 0

(B) 4 4

(D) 8 8

(E) 10 10

Answer

Correct choice: (D)

正确答案：（D）

Solution

Answer (D): Note that $S(1)=2$, $S(2)=4$, and $S(3)=8$. Call a sequence with $A$ and $B$ entries valid if it does not contain 4 or more consecutive symbols that are the same. For $n\ge 4$, every valid sequence of length $n-1$ can be extended to a valid sequence of length $n$ by appending a symbol different from its last symbol. Similarly, valid sequences of length $n-2$ or $n-3$ can be extended to valid sequences of length $n$ by appending either two or three equal symbols different from its last symbol. Note that all of these sequences are pairwise distinct. Conversely, every valid sequence of length $n$ ends with either one, two, or three equal consecutive symbols. Removal of these equal symbols at the end produces every valid sequence of length $n-1$, $n-2$, or $n-3$, respectively. Thus $S(n)=S(n-1)+S(n-2)+S(n-3)$. This recursive formula implies that the remainders modulo 3 of the sequence $S(n)$ for $1\le n\le 16$ are $2,1,2,2,2,0,1,0,1,2,0,0,2,2,1,2.$ Thus the sequence is periodic with period-length 13. Because $2015=13\cdot 155$, it follows that $S(2015)\equiv S(13)\equiv 2\pmod 3$. Similarly, the remainders modulo 4 of the sequence $S(n)$ for $1\le n\le 7$ are $2,0,0,2,2,0,0$. Thus the sequence is periodic with period-length 4. Because $2015=4\cdot 503+3$, it follows that $S(2015)\equiv S(3)\equiv 0\pmod 4$. Therefore $S(2015)=4k$ for some integer $k$, and $4k\equiv 2\pmod 3$. Hence $k\equiv 2\pmod 3$ and $S(2015)=4k\equiv 8\pmod{12}$.

答案（D）：注意 $S(1)=2$，$S(2)=4$，$S(3)=8$。把仅由 $A$ 和 $B$ 组成且不包含 4 个或更多相同符号连续出现的序列称为“有效”。当 $n\ge 4$ 时，每个长度为 $n-1$ 的有效序列，都可以通过在末尾添加一个与其最后一个符号不同的符号，扩展为长度为 $n$ 的有效序列。同样，长度为 $n-2$ 或 $n-3$ 的有效序列，也可以通过在末尾添加两个或三个相同且与其最后一个符号不同的符号，扩展为长度为 $n$ 的有效序列。注意这些得到的序列两两不同。反过来，任意长度为 $n$ 的有效序列，其末尾必为 1 个、2 个或 3 个相同的连续符号。去掉末尾这些相同符号，分别得到长度为 $n-1$、$n-2$ 或 $n-3$ 的所有有效序列。因此 $S(n)=S(n-1)+S(n-2)+S(n-3)$。该递推式推出：当 $1\le n\le 16$ 时，序列 $S(n)$ 模 3 的余数为 $2,1,2,2,2,0,1,0,1,2,0,0,2,2,1,2.$ 因此该序列以 13 为周期。由于 $2015=13\cdot 155$，可得 $S(2015)\equiv S(13)\equiv 2\pmod 3$。同理，当 $1\le n\le 7$ 时，序列 $S(n)$ 模 4 的余数为 $2,0,0,2,2,0,0$，因此该序列以 4 为周期。由于 $2015=4\cdot 503+3$，可得 $S(2015)\equiv S(3)\equiv 0\pmod 4$。因此存在整数 $k$ 使得 $S(2015)=4k$，且 $4k\equiv 2\pmod 3$。于是 $k\equiv 2\pmod 3$，并且 $S(2015)=4k\equiv 8\pmod{12}$。

Topics