Difference between revisions of "2009 AMC 12B Problems/Problem 21"

(Solution)
m (Latex error)
 
(18 intermediate revisions by 10 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== 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 was in before or a seat next to the one she occupied before. In how many ways can the women be reseated?
+
<!-- don't remove the following tag, for PoTW on the Wiki front page--><onlyinclude>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 was in before or a seat next to the one she occupied before. In how many ways can the women be reseated?<!-- don't remove the following tag, for PoTW on the Wiki front page--></onlyinclude>
  
 
<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 1==
+
==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
 +
<cmath>\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}.</cmath>
  
Let <math>W_n</math> be the answer for <math>n</math> women. We want to find <math>W_{10}</math>.
+
===Solution 1 Shortcut===
 +
Recall that the number of ways to arrange 1x1 and 2x1 blocks to form a 1xn rectangle results in [[Fibonacci numbers]]. Clearly, <math>\boxed{89}</math> is the only fibonacci number, so no calculation is needed for this problem.
  
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.  
+
==Solution 2==
 +
Let <math>S_n</math> be the number of possible seating arrangements with <math>n</math> women. Consider <math>n \ge 3,</math> and focus on the rightmost woman. If she returns back to her seat, then there are <math>S_{n-1}</math> ways to seat the remaining <math>n-1</math> 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 <math>S_{n-2}</math> ways to seat the other <math>n-2</math> women, so we obtain the recursion
 +
<cmath>S_n = S_{n-1}+S_{n-2}.</cmath>
 +
 
 +
Starting with <math>S_1=1</math> and <math>S_2=2,</math> we can calculate <math>S_{10}=\boxed{89}.</math>
 +
 
 +
==Clarification of Solution 2==
 +
The seating possibilities of woman #<math>10</math> become the two cases which we work out. <math>S_n</math> was defined to be the number of different seating arrangements with <math>n</math> women.
  
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.
+
In the first "case" if woman #<math>10</math> sits in the seat #<math>10</math>, this leads to a similar scenario, but with <math>9</math> women instead. That means that for this case, there are a total of <math>S_{9}</math> possible arrangements. We don't know how many exactly, but we are able to define it in terms of <math>S</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>.
+
During the second "case", woman #<math>10</math> sits in seat #<math>9</math>. This time, woman #9 must go to seat #<math>10</math>, as she is the only other person who can go there. This leaves us with <math>8</math> women, and we again represent this in terms of <math>S \Rightarrow S_8</math>.
  
==Solution 2==
+
Therefore, we can write <math>S_{10}</math> in terms of <math>S_8</math> and <math>S_9</math>, like so:
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>
+
<cmath>S_{10} = S_8 + S_9.</cmath>
 +
 
 +
We can then generalize this to say
 +
 
 +
<cmath>S_n = S_{n-1}+S_{n-2}.</cmath>
  
 +
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>.
 
== See Also ==
 
== See Also ==
  

Latest revision as of 22:58, 19 September 2022

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 1 Shortcut

Recall that the number of ways to arrange 1x1 and 2x1 blocks to form a 1xn rectangle results in Fibonacci numbers. Clearly, $\boxed{89}$ is the only fibonacci number, so no calculation is needed for this problem.

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

See Also

2009 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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png