Difference between revisions of "2009 AMC 12B Problems/Problem 21"
(New page: == Problem == Ten women sit in <math>10</math> seats in a line. All of the <math>10</math> get up and then reseat themselves using all <math>10</math> seats, each sitting in the seat she w...) |
m |
||
Line 8: | Line 8: | ||
Let <math>W_n</math> be the answer for <math>n</math> women, we want to find <math>W_{10}</math>. | Let <math>W_n</math> be the answer for <math>n</math> women, we want to find <math>W_{10}</math>. | ||
− | Clearly <math>W_0=W_1=1</math>. Now let <math>n>1</math>. Let the row of seats go from left to right. Label both the seats and the women <math>1</math> to <math> | + | Clearly <math>W_0=W_1=1</math>. Now let <math>n>1</math>. Let the row of seats go from left to right. Label both the seats and the women <math>1</math> to <math>n</math>, going from left to right. Consider the rightmost seat. Which women can sit there after the swap? It can either be woman <math>n</math> or woman <math>n-1</math>, as for any other woman the seat is too far. |
If woman <math>n</math> stays in her seat, there are exactly <math>W_{n-1}</math> valid arrangements of the other <math>n-1</math> women. If woman <math>n-1</math> sits on seat <math>n</math>, we only have one option for woman <math>n</math>: she must take seat <math>n-1</math>, all the other seats are too far for her. We are left with women <math>1</math> to <math>n-2</math> sitting on seats <math>1</math> to <math>n-2</math>, and there are clearly <math>W_{n-2}</math> valid arrangements of these. | If woman <math>n</math> stays in her seat, there are exactly <math>W_{n-1}</math> valid arrangements of the other <math>n-1</math> women. If woman <math>n-1</math> sits on seat <math>n</math>, we only have one option for woman <math>n</math>: she must take seat <math>n-1</math>, all the other seats are too far for her. We are left with women <math>1</math> to <math>n-2</math> sitting on seats <math>1</math> to <math>n-2</math>, and there are clearly <math>W_{n-2}</math> valid arrangements of these. |
Revision as of 09:43, 27 February 2009
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
2002 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 |