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"
(→‎Clarification of Solution 2)
Line 31: Line 31:
  
 
Calculating <math>S_1 = 1</math> and <math>S_2 =2,</math> then following the recursive rule from above, we get <math>S_{10} = 89 \Rightarrow \boxed{\text{A}}</math>.
 
Calculating <math>S_1 = 1</math> and <math>S_2 =2,</math> then following the recursive rule from above, we get <math>S_{10} = 89 \Rightarrow \boxed{\text{A}}</math>.
 +
==Solution 3==
 +
let <math>a_n=</math> the number of ways to order n women as per the constraints of the problem. We wish to find <math>a_{10}</math>. Lets take a look at 3 cases regarding the 2 women on the outside:
  
 +
Case 1: Both women stay in the same spot
 +
Then, we wish to order the inner people. This gives us <math>a_8</math> ways to do so
 +
 +
Case 2: One woman stays in her spot, and the other moves
 +
In this case, the woman that moves has to swap spots with the person right next to her, because that is the only way to use all 10 seats. If this doesn't make sense, look at the diagram below (each star is a woman, and the a represents the woman who will move:
 +
 +
a * * * * * * * * b
 +
 +
After "b" moves:
 +
 +
a * * * * * * * b ?
 +
 +
Now, the * has to go somewhere. If the star doesn't fill the spot that "b" was in, then only 9 seats would be used. Thus, the star has to go to the spot where "b" was, giving:
 +
 +
a * * * * * * * b *
 +
 +
This leaves us to order the 7 people who have not yet decided where they want to go. Since either of the women can move, this gives us <math>2a_7</math>.
 +
 +
Finally, Case 3: Both women switch
 +
In this case, we only have to order the inner 6 people, because the two women will swap spots with the people right next to them (see logic above). Thus, this yeilds <math>a_6</math>
 +
 +
So: <math>a_10=a_8+a_6+2a_7</math> We can generalize this to <math>a_{n+2}=a_n+a_{n-2}+2a_{n-1}</math>
 +
 +
Now, we calculate by hand that:
 +
<cmath>a_1=1</cmath>
 +
<cmath>a_2=2</cmath>
 +
<cmath>a_3=3</cmath>
 +
<cmath>a_4=5</cmath>
 +
Finally, we use the recurrence relation we developed to build our way to <math>a_{10}</math>
 +
<cmath>a_5=8</cmath>
 +
<cmath>a_6=13</cmath>
 +
<cmath>a_7=21</cmath>
 +
<cmath>a_8=34</cmath>
 +
<cmath>a_9=55</cmath>
 +
<cmath>a_{10}=89</cmath>
 +
So, we get $\boxed{10 \left(\text{A}\right)}
  
 
== See Also ==
 
== See Also ==

Revision as of 19:58, 28 November 2020

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

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 via casework depending on the number of 2x1 blocks. The cases of 0, 1, 2, 3, 4, 5 2x1 blocks correspond to 10, 8, 6, 4, 2, 0 1x1 blocks, and so the sum of the cases is \[\binom{10}{0} + \binom{9}{1} + \binom{8}{2} + \binom{7}{3} + \binom{6}{4} + \binom{5}{5} = 1 + 9 + 28 + 35 + 15 + 1 = \boxed{89}.\]


Solution 2

Let $S_n$ be the number of possible seating arrangements with $n$ women. Consider $n \ge 3,$ and focus on the rightmost woman. If she returns back to her seat, then there are $S_{n-1}$ ways to seat the remaining $n-1$ women. If she sits in the second to last seat, then the woman who previously sat there must now sit at the rightmost seat. This gives us $S_{n-2}$ ways to seat the other $n-2$ women, so we obtain the recursion \[S_n = S_{n-1}+S_{n-2}.\]

Starting with $S_1=1$ and $S_2=2,$ we can calculate $S_{10}=\boxed{89}.$

Clarification of Solution 2

The seating possibilities of woman #$10$ become the two cases which we work out. $S_n$ was defined to be the number of different seating arrangements with $n$ women.

In the first "case" if woman #$10$ sits in the seat #$10$, this leads to a similar scenario, but with $9$ women instead. That means that for this case, there are a total of $S_{9}$ possible arrangements. We don't know how many exactly, but we are able to define it in terms of $S$.

During the second "case", woman #$10$ sits in seat #$9$. This time, woman #9 must go to seat #$10$, as she is the only other person who can go there. This leaves us with $8$ women, and we again represent this in terms of $S \Rightarrow S_8$.

Therefore, we can write $S_{10}$ in terms of $S_8$ and $S_9$, like so:

\[S_{10} = S_8 + S_9.\]

We can then generalize this to say

\[S_n = S_{n-1}+S_{n-2}.\]

Calculating $S_1 = 1$ and $S_2 =2,$ then following the recursive rule from above, we get $S_{10} = 89 \Rightarrow \boxed{\text{A}}$.

Solution 3

let $a_n=$ the number of ways to order n women as per the constraints of the problem. We wish to find $a_{10}$. Lets take a look at 3 cases regarding the 2 women on the outside:

Case 1: Both women stay in the same spot Then, we wish to order the inner people. This gives us $a_8$ ways to do so

Case 2: One woman stays in her spot, and the other moves In this case, the woman that moves has to swap spots with the person right next to her, because that is the only way to use all 10 seats. If this doesn't make sense, look at the diagram below (each star is a woman, and the a represents the woman who will move:

a * * * * * * * * b

After "b" moves:

a * * * * * * * b ?

Now, the * has to go somewhere. If the star doesn't fill the spot that "b" was in, then only 9 seats would be used. Thus, the star has to go to the spot where "b" was, giving:

a * * * * * * * b *

This leaves us to order the 7 people who have not yet decided where they want to go. Since either of the women can move, this gives us $2a_7$.

Finally, Case 3: Both women switch In this case, we only have to order the inner 6 people, because the two women will swap spots with the people right next to them (see logic above). Thus, this yeilds $a_6$

So: $a_10=a_8+a_6+2a_7$ We can generalize this to $a_{n+2}=a_n+a_{n-2}+2a_{n-1}$

Now, we calculate by hand that: \[a_1=1\] \[a_2=2\] \[a_3=3\] \[a_4=5\] Finally, we use the recurrence relation we developed to build our way to $a_{10}$ \[a_5=8\] \[a_6=13\] \[a_7=21\] \[a_8=34\] \[a_9=55\] \[a_{10}=89\] So, we get $\boxed{10 \left(\text{A}\right)}

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