AMC12 2009 B

AMC12 2009 B · Q21

AMC12 2009 B · Q21. It mainly tests Sequences & recursion (algebra), Recursion & DP style counting (basic).

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?

十位女士坐在一条直线上的 $10$ 个座位上。她们全部站起来，然后重新坐下，使用所有 $10$ 个座位，并且每位女士坐在她之前坐的座位或与其相邻的座位上。她们重新坐下的方式有多少种？

(A) 89 89

(B) 90 90

(D) 210 210

(E) 2238 2238

Answer

Correct choice: (A)

正确答案：（A）

Solution

Notice that either a woman stays in her own seat after the rearrangement, or two adjacent women swap places. Thus, our answer is counting the number of ways to arrange 1x1 and 2x1 blocks to form a 1x10 rectangle. This can be done via casework depending on the number of 2x1 blocks. The cases of 0, 1, 2, 3, 4, 5 2x1 blocks correspond to 10, 8, 6, 4, 2, 0 1x1 blocks, and so the sum of the cases is \[\binom{10}{0} + \binom{9}{1} + \binom{8}{2} + \binom{7}{3} + \binom{6}{4} + \binom{5}{5} = 1 + 9 + 28 + 35 + 15 + 1 = \boxed{89}.\] Recall that the number of ways to arrange 1x1 and 2x1 blocks to form a 1xn rectangle results in Fibonacci numbers. Clearly, $\boxed{89}$ is the only fibonacci number, so no calculation is needed for this problem.

注意到重排后，要么某位女士仍坐在原来的座位上，要么两位相邻的女士互换座位。因此，我们要数的是用 $1\times 1$ 和 $2\times 1$ 的块拼成一个 $1\times 10$ 矩形的方式数。可以按 $2\times 1$ 块的数量分类讨论。$2\times 1$ 块分别取 $0,1,2,3,4,5$ 个时，对应的 $1\times 1$ 块数量分别为 $10,8,6,4,2,0$，因此总数为 \[\binom{10}{0} + \binom{9}{1} + \binom{8}{2} + \binom{7}{3} + \binom{6}{4} + \binom{5}{5} = 1 + 9 + 28 + 35 + 15 + 1 = \boxed{89}.\] 回忆：用 $1\times 1$ 与 $2\times 1$ 块拼成 $1\times n$ 矩形的方式数给出斐波那契数。显然 $\boxed{89}$ 是唯一符合的斐波那契数，因此本题甚至不必计算。

Topics