Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2009 AMC 12B Problems/Problem 21"
(→‎Solution)
Line 4: Line 4:
 
<math>\textbf{(A)}\ 89\qquad \textbf{(B)}\ 90\qquad \textbf{(C)}\ 120\qquad \textbf{(D)}\ 2^{10}\qquad \textbf{(E)}\ 2^2 3^8</math>
 
<math>\textbf{(A)}\ 89\qquad \textbf{(B)}\ 90\qquad \textbf{(C)}\ 120\qquad \textbf{(D)}\ 2^{10}\qquad \textbf{(E)}\ 2^2 3^8</math>
  
−
== Solution ==
+
== Solution 1==
  
−
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.  
Line 13: Line 13:
  
 
We get the recurrence <math>W_n = W_{n-1} + W_{n-2}</math>. (Hence <math>W_n</math> is precisely the <math>n</math>-th [[Fibonacci number]].) Using this recurrence we can easily compute that <math>W_{10} = \boxed{89}</math>.
 
We get the recurrence <math>W_n = W_{n-1} + W_{n-2}</math>. (Hence <math>W_n</math> is precisely the <math>n</math>-th [[Fibonacci number]].) Using this recurrence we can easily compute that <math>W_{10} = \boxed{89}</math>.
 +
 +
==Solution 2==
 +
Notice that either a woman stays in her own seat after the rearrangement, or two adjacent women swap places. Thus, our answer is counting the number of ways to arrange 1x1 and 2x1 blocks to form a 1x10 rectangle. This can be done by recursion as in Solution 1, or we can casework depending on the number of 2x1 blocks. The cases of 1, 2, 3, 4, 5 2x1 blocks correspond to 8, 6, 4, 2, 0 1x1 blocks, and so the answer is
 +
<cmath>\binom{9}{1} + \binom{8}{2} + \binom{7}{3} + \binom{6}{4} + \binom{5}{5} = 9 + 28 + 35 + 15 + 1 = 89.</cmath>
  
 
== See Also ==
 
== See Also ==

Revision as of 22:28, 31 January 2015

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 1

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}$.

Solution 2

Notice that either a woman stays in her own seat after the rearrangement, or two adjacent women swap places. Thus, our answer is counting the number of ways to arrange 1x1 and 2x1 blocks to form a 1x10 rectangle. This can be done by recursion as in Solution 1, or we can casework depending on the number of 2x1 blocks. The cases of 1, 2, 3, 4, 5 2x1 blocks correspond to 8, 6, 4, 2, 0 1x1 blocks, and so the answer is \[\binom{9}{1} + \binom{8}{2} + \binom{7}{3} + \binom{6}{4} + \binom{5}{5} = 9 + 28 + 35 + 15 + 1 = 89.\]

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_AMC_12B_Problems/Problem_21&oldid=67135"