https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Abhi1664&feedformat=atomAoPS Wiki - User contributions [en]2024-03-28T10:43:35ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=2009_AMC_12B_Answer_Key&diff=748942009 AMC 12B Answer Key2016-01-29T23:12:02Z<p>Abhi1664: </p>
<hr />
<div>#B<br />
#C<br />
#D<br />
#C<br />
#D<br />
#C<br />
#B<br />
#E<br />
#A<br />
#A<br />
#D<br />
#E<br />
#D<br />
#C<br />
#B<br />
#B<br />
#B<br />
#C<br />
#E<br />
#C<br />
#A<br />
#C<br />
#D<br />
#B<br />
#E</div>Abhi1664https://artofproblemsolving.com/wiki/index.php?title=2009_AMC_12B_Problems/Problem_21&diff=748932009 AMC 12B Problems/Problem 212016-01-29T22:58:28Z<p>Abhi1664: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
<!-- 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><br />
<br />
<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><br />
<br />
==Solution 1==<br />
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<br />
<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><br />
<br />
<br />
==Solution 2==<br />
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<br />
<cmath>S_n = S_{n-1}+S_{n-2}.</cmath><br />
<br />
Starting with <math>S_1=1</math> and <math>S_2=2,</math> we can calculate <math>S_{10}=\boxed{89}.</math><br />
<br />
== See Also ==<br />
<br />
{{AMC12 box|year=2009|ab=B|num-b=20|num-a=22}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Abhi1664https://artofproblemsolving.com/wiki/index.php?title=2009_AMC_12B_Problems/Problem_21&diff=748922009 AMC 12B Problems/Problem 212016-01-29T22:48:28Z<p>Abhi1664: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
<!-- 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><br />
<br />
<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><br />
<br />
==Solution 1==<br />
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<br />
<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><br />
<br />
== See Also ==<br />
<br />
{{AMC12 box|year=2009|ab=B|num-b=20|num-a=22}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Abhi1664