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"

m (→‎See Also)
Line 19: Line 19:
  
 
[[Category:Introductory Combinatorics Problems]]
 
[[Category:Introductory Combinatorics Problems]]
 +
{{MAA Notice}}

Revision as of 09:57, 4 July 2013

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

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=54115"