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 "2015 AMC 12B Problems/Problem 22"

(→‎Solution 1)
(→‎Solution 2)
Line 55: Line 55:
 
For 6-cycles, note that the neighbors of 1 can be 3 and 4, 3 and 5, or 4 and 5. In the first case, we may assume that it looks like <math>(314\dots)</math> -- the form <math>(413\dots)</math> is also possible, but equivalent to this case. Then we must place the elements 2, 5, and 6. Note that 5 and 6 cannot go together, so 2 must go in between them. Also, 5 cannot neighbor 4, so we are left with one possibility, namely <math>(314625)</math>, which has an analogous possibility <math>(413526)</math>. In the second case, we assume that it looks like <math>(315\dots)</math>. Clearly, the 2 must go next to the 5, and the 6 must go last (to neighbor the 3), so the only possibility here is <math>(315246)</math>, with the analogous possibility <math>(513642)</math>. In the final case, we may assume that it looks like <math>(415\dots)</math>. Then the 2 and 3 cannot go together, so the 6 must go in between them. Therefore, the only possibility is <math>(415362)</math>, with the analogous possibility <math>(514263)</math>. We have covered all possibilities for 6-cycles, and we have found 6 of them.
 
For 6-cycles, note that the neighbors of 1 can be 3 and 4, 3 and 5, or 4 and 5. In the first case, we may assume that it looks like <math>(314\dots)</math> -- the form <math>(413\dots)</math> is also possible, but equivalent to this case. Then we must place the elements 2, 5, and 6. Note that 5 and 6 cannot go together, so 2 must go in between them. Also, 5 cannot neighbor 4, so we are left with one possibility, namely <math>(314625)</math>, which has an analogous possibility <math>(413526)</math>. In the second case, we assume that it looks like <math>(315\dots)</math>. Clearly, the 2 must go next to the 5, and the 6 must go last (to neighbor the 3), so the only possibility here is <math>(315246)</math>, with the analogous possibility <math>(513642)</math>. In the final case, we may assume that it looks like <math>(415\dots)</math>. Then the 2 and 3 cannot go together, so the 6 must go in between them. Therefore, the only possibility is <math>(415362)</math>, with the analogous possibility <math>(514263)</math>. We have covered all possibilities for 6-cycles, and we have found 6 of them.
  
−
Therefore, there are a total of <math>4+6+4+6=20</math> such permutations, and the answer is <math>\boxed{\textbf{(D)}}</math>.
+
Therefore, there are <math>4+6+4+6 = \boxed{\textbf{(D)}\; 20}</math> such permutations.
  
 
==See Also==
 
==See Also==
 
{{AMC12 box|year=2015|ab=B|num-a=23|num-b=21}}
 
{{AMC12 box|year=2015|ab=B|num-a=23|num-b=21}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 14:42, 5 March 2015

Problem

Six chairs are evenly spaced around a circular table. One person is seated in each chair. Each person gets up and sits down in a chair that is not the same chair and is not adjacent to the chair he or she originally occupied, so that again one person is seated in each chair. In how many ways can this be done?

$\textbf{(A)}\; 14 \qquad\textbf{(B)}\; 16 \qquad\textbf{(C)}\; 18 \qquad\textbf{(D)}\; 20 \qquad\textbf{(E)}\; 24$

Solution 1

Label the people sitting at the table $A, B, C, D, E, F,$ and assume that they are initially seated in the order $ABCDEF$. The possible new positions for $A, B, C, D, E,$ and $F$ are respectively (a dash indicates a non-allowed position):

\[\begin{tabular}{| c | c | c | c | c | c |} \hline - & - & A & A & A & - \\ \hline - & - & - & B & B & B \\ \hline C & - & - & - & C & C \\ \hline D & D & - & - & - & D \\ \hline E & E & E & - & - & - \\ \hline - & F & F & F & - & - \\ \hline \end{tabular}\]

The permutations we are looking for should use one letter from each column, and there should not be any repeated letters:

$\begin{tabular}{c} CDEFAB \\ CEAFBD \\ CEFABD \\ CEFBAD \\ CFEABD \\ CFEBAD \\ DEAFBC \\ DEAFCB \\ DEFABC \\ DEFACB \\ DEFBAC \\ DFEABC \\ DFEACB \\ DFEBAC \\ EDAFBC \\ EDAFCB \\ EDFABC \\ EDFACB \\ EDFBAC \\ EFABCD \end{tabular}$

There are $\boxed{\textbf{(D)}\; 20}$ such permutations.

Solution 2

We can represent each rearrangement as a permutation of the six elements $\{1,2,3,4,5,6\}$ in cycle notation. Note that any such permutation cannot have a 1-cycle, so the only possible types of permutations are 2,2,2-cycles, 4,2-cycles, 3,3-cycles, and 6-cycles. We deal with each case separately.

For 2,2,2-cycles, suppose that one of the 2-cycles switches the people across from each other, i.e. $(14)$, $(25)$, or $(36)$. WLOG, we may assume it to be $(14)$. Then we could either have both of the other 2-cycles be across from each other, giving the permutation $(14)(25)(36)$, or else neither of the other 2-cycles are across from each other, in which case the only possible permutation is $(14)(26)(35)$. This can happen for $(25)$ and $(36)$ as well. So since the first permutation is not counted twice, we find a total of $1+3=4$ permutations that are 2,2,2-cycles where at least one of the 2-cycles switches people diametrically opposite from each other. Otherwise, since the elements in a 2-cycle cannot differ by 1, 3, or 5 mod 6, they must differ by 2 or 4 mod 6, i.e. they must be of the same parity. But since we have three odd and three even elements, this is impossible. Hence there are exactly 4 such permutations that are 2,2,2-cycles.

For 4,2-cycles, we assume for the moment that 1 is part of the 2-cycle. Then the 2-cycle can be $(13)$, $(15)$, or $(14)$. The first two are essentially the same by symmetry, and we must arrange the elements 2, 4, 5, 6 into a 4-cycle. However, 5 must have two neighbors that are not next to it, which is impossible, hence the first two cases yield no permutations. If the 2-cycle is $(14)$, then we must arrange the elements 2, 3, 5, 6 into a 4-cycle. Then 2 must have the neighbors 5 and 6. We find that the 4-cycles $(2536)$ and $(2635)$ satisfy the desired properties, yielding the permutations $(14)(2536)$ and $(14)(2635)$. This can be done for the 2-cycles $(25)$ and $(36)$ as well, so we find a total of 6 such permutations that are 4,2-cycles.

For 3,3-cycles, note that if 1 neighbors 4, then the third element in the cycle will neighbor one of 1 and 4, so this is impossible. Therefore, the 3-cycle containing 1 must consist of the elements 1, 3, and 5. Therefore, we obtain the four 3,3-cycles $(135)(246)$, $(153)(246)$, $(135)(264)$, and $(153)(264)$.

For 6-cycles, note that the neighbors of 1 can be 3 and 4, 3 and 5, or 4 and 5. In the first case, we may assume that it looks like $(314\dots)$ -- the form $(413\dots)$ is also possible, but equivalent to this case. Then we must place the elements 2, 5, and 6. Note that 5 and 6 cannot go together, so 2 must go in between them. Also, 5 cannot neighbor 4, so we are left with one possibility, namely $(314625)$, which has an analogous possibility $(413526)$. In the second case, we assume that it looks like $(315\dots)$. Clearly, the 2 must go next to the 5, and the 6 must go last (to neighbor the 3), so the only possibility here is $(315246)$, with the analogous possibility $(513642)$. In the final case, we may assume that it looks like $(415\dots)$. Then the 2 and 3 cannot go together, so the 6 must go in between them. Therefore, the only possibility is $(415362)$, with the analogous possibility $(514263)$. We have covered all possibilities for 6-cycles, and we have found 6 of them.

Therefore, there are $4+6+4+6 = \boxed{\textbf{(D)}\; 20}$ such permutations.

See Also

2015 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 21 		Followed by
Problem 23
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=2015_AMC_12B_Problems/Problem_22&oldid=68491"