2009 AMC 12B Problems/Problem 21
Problem
Ten women sit in seats in a line. All of the
get up and then reseat themselves using all
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?
Solution
Let be the answer for
women, we want to find
.
Clearly . Now let
. Let the row of seats go from left to right. Label both the seats and the women
to
, going from left to right. Consider the rightmost seat. Which women can sit there after the swap? It can either be woman
or woman
, as for any other woman the seat is too far.
If woman stays in her seat, there are exactly
valid arrangements of the other
women. If woman
sits on seat
, we only have one option for woman
: she must take seat
, all the other seats are too far for her. We are left with women
to
sitting on seats
to
, and there are clearly
valid arrangements of these.
We get the recurrence . (Hence
is precisely the
-th Fibonacci number.) Using this recurrence we can easily compute that
.
See Also
2009 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 20 |
Followed by Problem 22 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.