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 |