Difference between revisions of "2018 AMC 10B Problems/Problem 18"

(Solution 2)
m (Solution 6 (Derangement))
(25 intermediate revisions by 13 users not shown)
Line 1: Line 1:
 +
==Problem==
 +
 
Three young brother-sister pairs from different families need to take a trip in a van. These six children will occupy the second and third rows in the van, each of which has three seats. To avoid disruptions, siblings may not sit right next to each other in the same row, and no child may sit directly in front of his or her sibling. How many seating arrangements are possible for this trip?
 
Three young brother-sister pairs from different families need to take a trip in a van. These six children will occupy the second and third rows in the van, each of which has three seats. To avoid disruptions, siblings may not sit right next to each other in the same row, and no child may sit directly in front of his or her sibling. How many seating arrangements are possible for this trip?
  
 
<math>\textbf{(A)} \text{ 60} \qquad \textbf{(B)} \text{ 72} \qquad \textbf{(C)} \text{ 92} \qquad \textbf{(D)} \text{ 96} \qquad \textbf{(E)} \text{ 120}</math>
 
<math>\textbf{(A)} \text{ 60} \qquad \textbf{(B)} \text{ 72} \qquad \textbf{(C)} \text{ 92} \qquad \textbf{(D)} \text{ 96} \qquad \textbf{(E)} \text{ 120}</math>
 +
 +
== Video Solution ==
 +
https://youtu.be/3MiGotKnC_U?t=1982
 +
~ ThePuzzlr
 +
 +
== Video Solution ==
 +
https://youtu.be/0W3VmFp55cM?t=1288
 +
 +
~ pi_is_3.14
  
 
==Solution 1 (Casework)==
 
==Solution 1 (Casework)==
Line 7: Line 18:
 
We can begin to put this into cases. Let's call the pairs <math>a</math>, <math>b</math> and <math>c</math>, and assume that a member of pair <math>a</math> is sitting in the leftmost seat of the second row. We can have the following cases then.
 
We can begin to put this into cases. Let's call the pairs <math>a</math>, <math>b</math> and <math>c</math>, and assume that a member of pair <math>a</math> is sitting in the leftmost seat of the second row. We can have the following cases then.
  
Case 1:  
+
Case <math>1</math>:  
 
Second Row: a b c
 
Second Row: a b c
 
Third Row: b c a
 
Third Row: b c a
  
Case 2:
+
Case <math>2</math>:
 
Second Row: a c b
 
Second Row: a c b
 
Third Row: c b a
 
Third Row: c b a
  
Case 3:  
+
Case <math>3</math>:  
 
Second Row: a b c
 
Second Row: a b c
 
Third Row: c a b
 
Third Row: c a b
  
Case 4:  
+
Case <math>4</math>:  
 
Second Row: a c b
 
Second Row: a c b
 
Third Row: b a c
 
Third Row: b a c
  
For each of the four cases, we can flip the siblings, as they are distinct. So, each of the cases has <math>2 \cdot 2 \cdot 2 = 8</math> possibilities. Since there are four cases, when pair <math>a</math> has someone in the leftmost seat of the second row, there are 32 ways to rearrange it. However, someone from either pair <math>a</math>, <math>b</math>, or <math>c</math> could be sitting in the leftmost seat of the second row. So, we have to multiply it by 3 to get our answer of <math>32 \cdot 3 = 96</math>. So, the correct answer is <math>\boxed{\textbf{(D)} \text{ 96}}</math>.
+
For each of the four cases, we can flip the siblings, as they are distinct. So, each of the cases has <math>2 \cdot 2 \cdot 2 = 8</math> possibilities. Since there are four cases, when pair <math>a</math> has someone in the leftmost seat of the second row, there are <math>32</math> ways to rearrange it. However, someone from either pair <math>a</math>, <math>b</math>, or <math>c</math> could be sitting in the leftmost seat of the second row. So, we have to multiply it by <math>3</math> to get our answer of <math>32 \cdot 3 = 96</math>. So, the correct answer is <math>\boxed{\textbf{(D)} \text{ 96}}</math>.
  
 
Written By: Archimedes15
 
Written By: Archimedes15
Line 29: Line 40:
 
==Solution 2 (Easy Casework)==
 
==Solution 2 (Easy Casework)==
  
Lets call the siblings <math>A_1</math>, <math>A_2</math>, <math>B_1</math>, <math>B_2</math>, <math>C_1</math>, and <math>C_2</math>. We can split our problem into 2 cases:  
+
Lets call the siblings <math>A_1</math>, <math>A_2</math>, <math>B_1</math>, <math>B_2</math>, <math>C_1</math>, and <math>C_2</math>. We can split our problem into two cases:  
  
 
There is a child of each family in each row (There is an A, B, C in each row )
 
There is a child of each family in each row (There is an A, B, C in each row )
Line 35: Line 46:
 
There are two children of the same family in a row.
 
There are two children of the same family in a row.
  
Starting off with the first case, we see that there are <math>3!=6</math> ways to arrange the A,B,C. Then, we have to choose which sibling sits. There are 2 choices for each set of siblings meaning we have <math>2^3=8</math> ways to arrange that. So, there are 48 ways to arrange the siblings in the first row. The second row is a bit easier. We see that there are 2 ways to place the A sibling and each placement yields only 1 possibility. So, our first case has <math>48\cdot2=96 possibilities.</math>
+
Starting off with the first case, we see that there are <math>3!=6</math> ways to arrange the A,B,C. Then, we have to choose which sibling sits. There are <math>2</math> choices for each set of siblings meaning we have <math>2^3=8</math> ways to arrange that. So, there are <math>48</math> ways to arrange the siblings in the first row. The second row is a bit easier. We see that there are <math>2</math> ways to place the A sibling and each placement yields only <math>1</math> possibility. So, our first case has <math>48\cdot2=96</math> possibilities.
  
In our second case, there are 3 ways to choose which set of siblings will be in the same row, two ways to choose which set of sibling will sit in between them and 2 ways to choose whether it is the brother or sister. So, there <math>3*2*2 = 18</math> ways to arrange the first row. In the second row, however, we see that it is impossible to make everything work out. So, there are 0 possibilities for this case.  
+
In our second case, there are <math>3</math> ways to choose which set of siblings will be in the same row and <math>4</math> ways to choose the person in between. So, there <math>3*4 = 12</math> ways to arrange the first row. In the second row, however, we see that it is impossible to make everything work out. So, there are <math>0</math> possibilities for this case.  
  
Thus, there are <math>96+0 = \boxed{96 possibilities for this trip.}</math>
+
Thus, there are <math>96+0 = \boxed{D) 96}</math>  possibilities for this trip.
  
 
-Conantwiz2023
 
-Conantwiz2023
Line 47: Line 58:
 
Call the siblings <math>A_1</math>, <math>A_2</math>, <math>B_1</math>, <math>B_2</math>, <math>C_1</math>, and <math>C_2</math>.
 
Call the siblings <math>A_1</math>, <math>A_2</math>, <math>B_1</math>, <math>B_2</math>, <math>C_1</math>, and <math>C_2</math>.
  
There are 6 choices for the child in the first seat, and it doesn't matter which one takes it, so suppose [[Without loss of generality]] that <math>A_1</math> takes it (a <math>\circ</math> is an empty seat):
+
There are 6 choices for the child in the first seat, and it doesn't matter which one takes it, so suppose [[Without loss of generality]] that <math>A_1</math> takes it (<math>\circ</math> denotes an empty seat):
  
 
<math>A_1 \circ \circ \\ \circ \ \circ \ \circ </math>
 
<math>A_1 \circ \circ \\ \circ \ \circ \ \circ </math>
Line 55: Line 66:
 
<math>A_1 B_1 \circ \\ \circ \ \circ \ \circ</math>
 
<math>A_1 B_1 \circ \\ \circ \ \circ \ \circ</math>
  
The last seat in the first row cannot be <math>A_2</math> because it would be impossible to create a second row that satisfies the conditions. Therefore, it must be <math>C_1</math> or <math>C_2</math>. Let's say WLOG that it is <math>C_1</math>. There are two ways to create a second row:,,,,'
+
The last seat in the first row cannot be <math>A_2</math> because it would be impossible to create a second row that satisfies the conditions. Therefore, it must be <math>C_1</math> or <math>C_2</math>. Let's say WLOG that it is <math>C_1</math>. There are two ways to create a second row:
  
 
<math>A_1 B_1 C_1 \\ B_2 C_2 A_2</math>
 
<math>A_1 B_1 C_1 \\ B_2 C_2 A_2</math>
Line 65: Line 76:
 
Written by: HoloGuard1728
 
Written by: HoloGuard1728
  
== Solution 3 (a bit of group theory) ==
+
== Solution 4 ==
 +
 
 +
WLOG, define the three pairs of siblings to be: <math>A</math>, <math>B</math>, and <math>C</math>. Now, notice that you can only form a correct grouping either like this:
 +
 
 +
<math>A B C</math>
 +
 
 +
<math>B C A</math>
 +
 
 +
or this:
 +
 
 +
<math>C B A</math>
 +
 
 +
<math>A C B</math>
 +
 
 +
However, we need to consider the different orders. There are <math>3!</math> ways to order each pair (eg. the same letters) and <math>2^3</math> was to order the people each of the three pairs. Now, we can just multiply everything together, yielding:
 +
 
 +
<math>2\cdot3!\cdot2^3</math>
 +
 
 +
Which is <math>\boxed{\textbf{(D) } 96}</math>
 +
 
 +
-Ericshi1685
 +
 
 +
==Solution 5 (using answer choices)==
 +
Let the families be a, b, c. In any given possible arrangement, there are 3! = 6 ways to arrange the families and 2 • 2 • 2 = 8 ways to arrange the siblings. This means the answer has to be divisble by 6 • 8 = 48. The only answer choice that satisfies this is <math>\boxed{\textbf{(D) } 96}</math>
 +
 
 +
==Solution 6 (Derangement)==
 +
If a pair of siblings are in the same row, the other <math>2</math> pairs of siblings cannot fit in the remaining <math>4</math> seats to meet the requirements. Therefore, the siblings must be in different rows.
 +
 
 +
Let the first pair of siblings be <math>a_1</math>, <math>a_2</math>, the second pair of siblings be <math>b_1</math>, <math>b_2</math>, and the third pair of siblings be <math>c_1</math>, <math>c_2</math>. For each row there must be <math>1</math> child from each family. WLOG, let <math>a_1</math>, <math>b_1</math>, <math>c_1</math> be in the first row. There are <math>3!</math> arrangements. <math>a_2</math>, <math>b_2</math>, <math>c_2</math> are in the second row, and they cannot be in the same column as their sibling. Now the problem becomes a <math>3</math> element [https://en.wikipedia.org/wiki/Derangement Derangement] problem.
  
Note that there is a free <math>S_2\wr S_3</math> action on the set of allowed seating arrangements: any brother-sister pair can be switched, and the 3 pairs can be permuted among each other in any way. Hence the answer must be a multiple of the order of <math>S_2\wr S_3</math>, which is <math>2^3\cdot 6=48</math>. The only answer choice satisfying this is <math>\boxed{\textbf{(D)} \text{ 96}}</math>.
+
An <math>n</math> element derangement problem is to find the number of permutations of <math>n</math> elements where each element has a specified location, and no element is in it's specified location. For example, there are <math>3</math> elements <math>1</math>, <math>2</math>, <math>3</math>. <math>1</math> cannot be in the first location, <math>2</math> cannot be in the second location, and <math>3</math> cannot be in the third location. The derangements are: <math>(2,3,1)</math>, <math>(3,1,2)</math>. <math>D_3=2</math>.
  
To finish the solution, with a bit of work we see that there are only two orbits of seating arrangements: the orbit of
+
Each pair of siblings can swap their position. There are <math>2^3</math> swaps. The total arrangements are: <math>3! \cdot D_3 \cdot 2^3=6 \cdot 2 \cdot 8 =\boxed{\textbf{(D) } 96}</math>
123/231
 
and the orbit of
 
123/312.
 
  
So the answer is indeed <b>96</b>.
+
~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen]
  
 
==See Also==
 
==See Also==

Revision as of 09:29, 28 December 2021

Problem

Three young brother-sister pairs from different families need to take a trip in a van. These six children will occupy the second and third rows in the van, each of which has three seats. To avoid disruptions, siblings may not sit right next to each other in the same row, and no child may sit directly in front of his or her sibling. How many seating arrangements are possible for this trip?

$\textbf{(A)} \text{ 60} \qquad \textbf{(B)} \text{ 72} \qquad \textbf{(C)} \text{ 92} \qquad \textbf{(D)} \text{ 96} \qquad \textbf{(E)} \text{ 120}$

Video Solution

https://youtu.be/3MiGotKnC_U?t=1982 ~ ThePuzzlr

Video Solution

https://youtu.be/0W3VmFp55cM?t=1288

~ pi_is_3.14

Solution 1 (Casework)

We can begin to put this into cases. Let's call the pairs $a$, $b$ and $c$, and assume that a member of pair $a$ is sitting in the leftmost seat of the second row. We can have the following cases then.

Case $1$: Second Row: a b c Third Row: b c a

Case $2$: Second Row: a c b Third Row: c b a

Case $3$: Second Row: a b c Third Row: c a b

Case $4$: Second Row: a c b Third Row: b a c

For each of the four cases, we can flip the siblings, as they are distinct. So, each of the cases has $2 \cdot 2 \cdot 2 = 8$ possibilities. Since there are four cases, when pair $a$ has someone in the leftmost seat of the second row, there are $32$ ways to rearrange it. However, someone from either pair $a$, $b$, or $c$ could be sitting in the leftmost seat of the second row. So, we have to multiply it by $3$ to get our answer of $32 \cdot 3 = 96$. So, the correct answer is $\boxed{\textbf{(D)} \text{ 96}}$.

Written By: Archimedes15

Solution 2 (Easy Casework)

Lets call the siblings $A_1$, $A_2$, $B_1$, $B_2$, $C_1$, and $C_2$. We can split our problem into two cases:

There is a child of each family in each row (There is an A, B, C in each row ) or There are two children of the same family in a row.

Starting off with the first case, we see that there are $3!=6$ ways to arrange the A,B,C. Then, we have to choose which sibling sits. There are $2$ choices for each set of siblings meaning we have $2^3=8$ ways to arrange that. So, there are $48$ ways to arrange the siblings in the first row. The second row is a bit easier. We see that there are $2$ ways to place the A sibling and each placement yields only $1$ possibility. So, our first case has $48\cdot2=96$ possibilities.

In our second case, there are $3$ ways to choose which set of siblings will be in the same row and $4$ ways to choose the person in between. So, there $3*4 = 12$ ways to arrange the first row. In the second row, however, we see that it is impossible to make everything work out. So, there are $0$ possibilities for this case.

Thus, there are $96+0 = \boxed{D) 96}$ possibilities for this trip.

-Conantwiz2023

Solution 3

Call the siblings $A_1$, $A_2$, $B_1$, $B_2$, $C_1$, and $C_2$.

There are 6 choices for the child in the first seat, and it doesn't matter which one takes it, so suppose Without loss of generality that $A_1$ takes it ($\circ$ denotes an empty seat):

$A_1 \circ \circ \\ \circ \ \circ \ \circ$

Then there are 4 choices for the second seat ($B_1$, $B_2$, $C_1$, or $C_2$). Like before, it doesn't matter who takes the seat, so WLOG suppose it is $B_1$:

$A_1 B_1 \circ \\ \circ \ \circ \ \circ$

The last seat in the first row cannot be $A_2$ because it would be impossible to create a second row that satisfies the conditions. Therefore, it must be $C_1$ or $C_2$. Let's say WLOG that it is $C_1$. There are two ways to create a second row:

$A_1 B_1 C_1 \\ B_2 C_2 A_2$

$A_1 B_1 C_1 \\ C_2 A_2 B_2$

Therefore, there are $6 \cdot 4 \cdot 2 \cdot 2= \boxed{\textbf{(D)} \text{ 96}}$ possible seating arrangements.

Written by: HoloGuard1728

Solution 4

WLOG, define the three pairs of siblings to be: $A$, $B$, and $C$. Now, notice that you can only form a correct grouping either like this:

$A B C$

$B C A$

or this:

$C B A$

$A C B$

However, we need to consider the different orders. There are $3!$ ways to order each pair (eg. the same letters) and $2^3$ was to order the people each of the three pairs. Now, we can just multiply everything together, yielding:

$2\cdot3!\cdot2^3$

Which is $\boxed{\textbf{(D) } 96}$

-Ericshi1685

Solution 5 (using answer choices)

Let the families be a, b, c. In any given possible arrangement, there are 3! = 6 ways to arrange the families and 2 • 2 • 2 = 8 ways to arrange the siblings. This means the answer has to be divisble by 6 • 8 = 48. The only answer choice that satisfies this is $\boxed{\textbf{(D) } 96}$

Solution 6 (Derangement)

If a pair of siblings are in the same row, the other $2$ pairs of siblings cannot fit in the remaining $4$ seats to meet the requirements. Therefore, the siblings must be in different rows.

Let the first pair of siblings be $a_1$, $a_2$, the second pair of siblings be $b_1$, $b_2$, and the third pair of siblings be $c_1$, $c_2$. For each row there must be $1$ child from each family. WLOG, let $a_1$, $b_1$, $c_1$ be in the first row. There are $3!$ arrangements. $a_2$, $b_2$, $c_2$ are in the second row, and they cannot be in the same column as their sibling. Now the problem becomes a $3$ element Derangement problem.

An $n$ element derangement problem is to find the number of permutations of $n$ elements where each element has a specified location, and no element is in it's specified location. For example, there are $3$ elements $1$, $2$, $3$. $1$ cannot be in the first location, $2$ cannot be in the second location, and $3$ cannot be in the third location. The derangements are: $(2,3,1)$, $(3,1,2)$. $D_3=2$.

Each pair of siblings can swap their position. There are $2^3$ swaps. The total arrangements are: $3! \cdot D_3 \cdot 2^3=6 \cdot 2 \cdot 8 =\boxed{\textbf{(D) } 96}$

~isabelchen

See Also

2018 AMC 10B (ProblemsAnswer KeyResources)
Preceded by
Problem 17
Followed by
Problem 19
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 10 Problems and Solutions

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