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$ 名女性的合法重新入座方式数。考虑最右边座位，可分为剩下 $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 题