Question

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}$

Solution:

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 Problem 21

Solution:

Problem 21 in Other Years