2015 AMC 12A 第 22 题

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

小提示：

一个合法序列以长度为

1

，

2

，或

3

的同字母段结尾，因此

S(n) = S(n-1)

+ S(n-2)

+ S(n-3)

A valid sequence ends in a run of

1,

2,

or

3

equal letters, giving

S(n) = S(n-1)

+ S(n-2)

+ S(n-3)

大提示：

分别模

3

和模

4

化简递推式以寻找周期

Reduce the recurrence modulo

3

and modulo

4

separately to find its period

解答：

注意

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}\text{。}

模

3

时，前

13

项为

2,1,2,2,2,0,1,0,1,2,0,0,2\text{。}

接下来的三项是

2,1,2

，与初始状态相同，所以递推式以

13

为周期重复。因为

2015 = 13\cdot 155

，可得

S(2015) \equiv S(13) \equiv 2 \pmod 3

。

模

4

时，各项按

2,0,0,2

循环，因为这四项之后的三项状态又回到

(2,0,0)

。所以周期为

4

。因为

2015 = 4\cdot 503 + 3

，所以

S(2015) \equiv S(3) \equiv 0 \pmod 4

。

写

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 题