2009 AMC 12B 第 21 题

Question

十名女性坐在一排

10

个座位上。所有

10

人都起身，然后重新坐满这

10

个座位，每个人坐在自己原来的座位或与原座位相邻的座位上。她们有多少种重新入座方式？

Ten women sit in

10

seats in a line. All of the

10

get up and then reseat themselves using all

10

seats, each sitting in the seat she was in before or a seat next to the one she occupied before. In how many ways can the women be reseated?

89

90

120

210

2^{38}

答案：A

知识点：递推斐波那契数列

难度评级：2160

小提示：

设

S_n

表示

n

名女性的合法重新入座数；考虑最右边女性的选择。

Let

S_n

count the valid reseatings of

n

women; consider the rightmost woman’s choice

大提示：

若她不动，剩下

S_{n-1}

种；若她向左移动，则必须与左邻座交换，剩下

S_{n-2}

种，所以

S_n = S_{n-1} + S_{n-2}

。

If she stays she leaves

S_{n-1}

ways; if she moves left a swap is forced, leaving

S_{n-2}

— so

S_n = S_{n-1} + S_{n-2}

解答：

设

S_n

为

n

名女性的合法重新入座方式数。最右边的女性要么留在原座位，此时其余人有

S_{n-1}

种方式；要么与左边的邻座交换（这是填满最右端座位的唯一其他方式），此时剩下

S_{n-2}

种方式。

因此

S_n = S_{n-1} + S_{n-2}

，且

S_1 = 1

、

S_2 = 2

，得到斐波那契数列

1, 2, 3, 5, 8, 13, 21, 34, 55, 89

。所以

S_{10} = 89

。

所以正确答案是 A。

Let

S_n

be the number of valid reseatings of

n

women. The rightmost woman either keeps her seat, leaving

S_{n-1}

ways for the rest, or swaps with her left neighbor — the only other way to fill the end seat — leaving

S_{n-2}

ways.

Thus

S_n = S_{n-1} + S_{n-2}

with

S_1 = 1

and

S_2 = 2,

giving the Fibonacci values

1, 2, 3, 5, 8, 13, 21, 34, 55, 89.

So

S_{10} = 89.

Thus, the correct answer is A.

2009 AMC 12B 第 21 题

答案：A

难度评级：2160

小提示：

大提示：

解答：

其他年份的第 21 题