2015 AIME II 第 12 题

Question

由

10

个字母组成、且每个字母都是 A 或 B 的字符串共有

2^{10} = 1024

个。求其中不含超过

3

个连续相同字母的字符串个数。

There are

2^{10} = 1024

possible

10

-letter strings in which each letter is either an A or a B. Find the number of such strings that do not have more than

3

adjacent letters that are identical.

答案

答案：548

知识点：递推计数有限制的排列

难度评级：2890

小提示：

条件等价于每一段连续相同字母的长度至多为

3

。按第一段的长度分类有效字符串。

The condition says every run of identical letters has length at most

3.

Classify valid strings by the length of their first run.

大提示：

若

s_n

表示以指定字母开头的有效

n

位字符串个数，则

s_n = s_{n-1} + s_{n-2} + s_{n-3}

If

s_n

counts valid length-

n

strings starting with a given letter, then

s_n = s_{n-1} + s_{n-2} + s_{n-3}

解答：

条件说明每一段连续相同字母的长度至多为

3

。令

s_n

表示以 A 开头的有效

n

位字符串个数；由对称性，答案为

2s_{10}

。去掉第一段（长度为

1

、

2

或

3

）后，剩下的是一个以 B 开头的更短有效字符串，所以

s_n = s_{n-1} + s_{n-2} + s_{n-3}\text{。}

由初值

s_1 = 1

、

s_2 = 2

、

s_3 = 4

出发，序列接下来依次为

7, 13, 24, 44, 81, 149, 274

，所以

s_{10} = 274

。

有效字符串数为

2 \cdot 274 = 548

。

The condition says every maximal run of identical letters has length at most

3.

Let

s_n

count the valid strings of length

n

whose first letter is A; by symmetry the answer is

2s_{10}.

Removing the first run (of length

1,

2,

or

3

) leaves a valid shorter string beginning with B, so

s_n = s_{n-1} + s_{n-2} + s_{n-3}.

Starting from

s_1 = 1,

s_2 = 2,

s_3 = 4,

the sequence runs

7, 13, 24, 44, 81, 149, 274,

so

s_{10} = 274.

The number of valid strings is

2 \cdot 274 = 548.

2015 AIME II 第 12 题

答案：548

难度评级：2890

小提示：

大提示：

解答：

其他年份的第 12 题