2009 AMC 12B Problem 21

Problem 21 of 25HarderAlgebra

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?

Show solution

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.

S_{10} = 89.

Thus, the correct answer is A.