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>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.  
+
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 $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?

$\textbf{(A)}\ 89\qquad \textbf{(B)}\ 90\qquad \textbf{(C)}\ 120\qquad \textbf{(D)}\ 2^{10}\qquad \textbf{(E)}\ 2^2 3^8$

Solution

Let $W_n$ be the answer for $n$ women, we want to find $W_{10}$.

Clearly $W_0=W_1=1$. Now let $n>1$. Let the row of seats go from left to right. Label both the seats and the women $1$ to $n$, going from left to right. Consider the rightmost seat. Which women can sit there after the swap? It can either be woman $n$ or woman $n-1$, as for any other woman the seat is too far.

If woman $n$ stays in her seat, there are exactly $W_{n-1}$ valid arrangements of the other $n-1$ women. If woman $n-1$ sits on seat $n$, we only have one option for woman $n$: she must take seat $n-1$, all the other seats are too far for her. We are left with women $1$ to $n-2$ sitting on seats $1$ to $n-2$, and there are clearly $W_{n-2}$ valid arrangements of these.

We get the recurrence $W_n = W_{n-1} + W_{n-2}$. (Hence $W_n$ is precisely the $n$-th Fibonacci number.) Using this recurrence we can easily compute that $W_{10} = \boxed{89}$.

See Also

2002 AMC 12B (ProblemsAnswer KeyResources)
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
Invalid username
Login to AoPS