Problem:
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?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Let denote the number of ways that women in seats can be reseated so that each woman reseats herself in the seat she occupied before
or a seat next to it. It is easy to see that and . Now consider the case with women, and focus on the woman at the right end of the line. If this woman sits again in this end seat, then the remaining women can reseat themselves in ways. If this end woman sits in the seat next to hers, then the former occupant of this new seat must sit on the end. Then the remaining women can seat themselves in ways. Thus for , . Therefore , which are some of the first few terms of the Fibonacci Sequence. Thus .
The problems on this page are the property of the MAA's American Mathematics Competitions