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 "2013 AMC 10A Problems/Problem 24"
 
(47 intermediate revisions by 22 users not shown)
Line 1: Line 1:
 +
==Problem==
 +
 
Central High School is competing against Northern High School in a backgammon match. Each school has three players, and the contest rules require that each player play two games against each of the other school's players. The match takes place in six rounds, with three games played simultaneously in each round. In how many different ways can the match be scheduled?
 
Central High School is competing against Northern High School in a backgammon match. Each school has three players, and the contest rules require that each player play two games against each of the other school's players. The match takes place in six rounds, with three games played simultaneously in each round. In how many different ways can the match be scheduled?
  
 
<math> \textbf{(A)}\ 540\qquad\textbf{(B)}\ 600\qquad\textbf{(C)}\ 720\qquad\textbf{(D)}\ 810\qquad\textbf{(E)}\ 900</math>
 
<math> \textbf{(A)}\ 540\qquad\textbf{(B)}\ 600\qquad\textbf{(C)}\ 720\qquad\textbf{(D)}\ 810\qquad\textbf{(E)}\ 900</math>
  
−
==Solution==
+
==Solution 1==
 +
 
 +
Let us label the players of the first team <math>A</math>, <math>B</math>, and <math>C</math>, and those of the second team, <math>X</math>, <math>Y</math>, and <math>Z</math>.
 +
 
 +
<math>\textbf{1}</math>. One way of scheduling all six distinct rounds could be:
 +
 
 +
Round 1: <math>AX</math> <math>BY</math> <math>CZ</math>
 +
 
 +
Round 2: <math>AX</math> <math>BZ</math> <math>CY</math>
 +
 
 +
Round 3: <math>AY</math> <math>BX</math> <math>CZ</math>
 +
 
 +
Round 4: <math>AY</math> <math>BZ</math> <math>CX</math>
 +
 
 +
Round 5: <math>AZ</math> <math>BX</math> <math>CY</math>
 +
 
 +
Round 6: <math>AZ</math> <math>BY</math> <math>CX</math>
 +
 
 +
 
 +
The above mentioned schedule ensures that each player of one team plays twice with each player from another team. Now you can generate a completely new schedule by permutating those <math>6</math> rounds and that can be done in <math>6!=720</math> ways.
 +
 
 +
<math>\textbf{2}</math>. One can also make the schedule in such a way that two rounds are repeated. 
 +
 
 +
(a)
 +
 
 +
Round 1: <math>AX</math> <math>BZ</math> <math>CY</math>
 +
 
 +
Round 2: <math>AX</math> <math>BZ</math> <math>CY</math>
 +
 
 +
Round 3: <math>AY</math> <math>BX</math> <math>CZ</math>
  
−
*Credit to the Math Jam for this solution
+
Round 4: <math>AY</math> <math>BX</math> <math>CZ</math>
  
 +
Round 5: <math>AZ</math> <math>BY</math> <math>CX</math>
  
−
Let us label the players of the first team <math>A</math>, <math>B</math>, and <math>C</math>, and those of the second team, <math>X</math>, <math>Y</math>, and <math>Z</math>.
+
Round 6: <math>AZ</math> <math>BY</math> <math>CX</math>
  
−
Let us first consider how to organize A's matches, <math>AX</math>, <math>AX</math>, <math>AY</math>, <math>AY</math>, <math>AZ</math>, and <math>AZ</math>.  Because we have three duplicates, there are <math>\frac{6!}{2!*2!*2!} = 90</math> ways to organize A's matches.
+
(b)
  
−
Now, consider <math>B</math> and <math>C</math>.  WLOG assume that A's matches were <math>XXYYZZ</math>, as we will multiply by <math>90</math> the end anyways, and that, in the first round, <math>B</math> played <math>Y</math> and <math>C</math> played <math>Z</math>.
+
Round 1: <math>AX</math> <math>BY</math> <math>CZ</math>
  
−
There are two cases.
+
Round 2: <math>AX</math> <math>BY</math> <math>CZ</math>
  
−
1.  <math>B</math> plays <math>Y</math> again in the second round (and <math>C</math> plays <math>Z</math> in the second round)
+
Round 3: <math>AY</math> <math>BZ</math> <math>CX</math>
  
−
In this case, the rest of the matches are forced, as <math>C</math> must play <math>X</math> in both of rounds <math>3</math> and <math>4</math> (as it has already played <math>Z</math> twice) and same with rounds <math>5</math> and <math>6</math> with <math>B</math> and <math>Y</math>.  Thus, there is only one option.
+
Round 4: <math>AY</math> <math>BZ</math> <math>CX</math>
  
−
2.  <math>B</math> plays <math>Z</math> in the second round (and <math>C</math> plays <math>Y</math> in the second round)
+
Round 5: <math>AZ</math> <math>BX</math> <math>CY</math>
  
−
In this case, <math>B</math> can play <math>Z</math> in either round <math>3</math> or <math>4</math> and <math>Y</math> in either round <math>5</math> or <math>6</math>, so there are <math>2(2) = 4</math> options. 
+
Round 6: <math>AZ</math> <math>BX</math> <math>CY</math>
  
−
Thus, with <math>B</math> playing <math>Y</math> in the first round, there are <math>4+1 = 5</math> options.  Multiplying this by <math>2</math> for the case where <math>B</math> plays <math>Z</math> in the first round, we get <math>10</math> options.
+
As mentioned earlier any permutation of (a) and (b) will also give us a new schedule. For both (a) and (b) the number of permutations are
 +
<math>\frac{6!}{2!2!2!}</math> = <math>90</math>
  
−
Finally, to get our final answer, we multiply <math>10 * 90 = 900</math> ways to organize the matches, <math>\textbf{(E)}</math>.
 
  
 +
So the total number of schedules is <math>720+90+90</math> =<math>\boxed{\textbf{(E)} 900}</math>.
  
 +
==Solution 2==
 +
Label the players of the first team <math>A</math>, <math>B</math>, and <math>C</math>, and those of the second team, <math>X</math>, <math>Y</math>, and <math>Z</math>. We can start by assigning an opponent to person <math>A</math> for all <math>6</math> games. Since <math>A</math> has to play each of <math>X</math>, <math>Y</math>, and <math>Z</math> twice, there are <math>\frac{6!}{2!2!2!} = 90</math> ways to do this. We can assume that the opponents for <math>A</math> in the <math>6</math> rounds are <math>X</math>, <math>X</math>, <math>Y</math>, <math>Y</math>, <math>Z</math>, <math>Z</math> and multiply by <math>90</math> afterwards.
 +
 +
 +
Notice that for every valid assignment of the opponents of <math>A</math> and <math>B</math>, there is only <math>1</math> valid assignment of opponents for <math>C</math>. More specifically, the opponents for <math>C</math> are the leftover opponents after the opponents for <math>A</math> and <math>B</math> are chosen in each round. Therefore, all we have to do is assign the opponents for <math>B</math>. This is the same as finding the number of permutations of <math>X</math>, <math>Y</math>, and <math>Z</math> that do not have a <math>X</math> in the first two spots, an <math>Y</math> in the next two spots, and a <math>Z</math> in the final two spots.
 +
 +
 +
 +
We can use casework to find this by using the fact that after we put down the <math>X</math>'s and <math>Y</math>'s first there is <math>1</math> way to put down the <math>Z</math>'s (the two remaining spots).
 +
 +
If <math>X</math>'s are put in the middle <math>2</math> spots, then there is <math>1</math> way to assign spots to <math>Y</math>, namely the last <math>2</math> spots. (If one of the last two spots are left empty, there will have to be a <math>Z</math> there, which which not valid).
 +
 +
If <math>X</math>'s are put in the last <math>2</math> spots, then there is <math>1</math> way to assign spots to <math>Y</math>.
 +
 +
Finally, if one <math>X</math> was put in on of the middle two spots and one <math>X</math> was put in one of the last two spots, there are <math>2\cdot2</math> ways to assign spots to <math>X</math> and <math>2\cdot1</math> ways to assign spots to <math>Y</math> (one of the first two spots and the remaining spot in the last <math>2</math>).
 +
 +
There are <math>1+1+2\cdot2\cdot2\cdot1 = 10</math> ways to assign opponents to <math>B</math> and <math>90\cdot10 = 900</math> ways to order the games. <math>\boxed{\textbf{(E)} 900}</math>
 +
 +
== Solution 3(similar to 2) ==
 +
We only need to worry about what the other member of the pair would be for our own competitors. If our competitors are <math>A,B,C</math> and the others are <math>1,2,3</math>, then we only need to arrange the numbers <math>1,1,2,2,3,3</math> such that we don't have the same number in the same spots. For our first row of numbers, or our first player, they can be arranged in any of <cmath>\frac{6!}{2!2!2!}</cmath> ways as nothing has happened yet. This contributes <math>90</math> to our final product. Once we determine our second row, or player, the third will immediately follow thus we only need to figure out the second one. WLOG, our first arrangement was <math>112233</math>. For our <math>1</math>'s, we can put them anywhere that is not in our first <math>2</math> spots. If we put both of them in the same "region", like the <math>2</math>'s or the <math>3</math>'s, then it will give a different case than if they were in different regions.
 +
 +
Case 1 : They are in the same region
 +
 +
There are <math>2</math> ways that the <math>1</math>'s can be in the same region. If, let's say its in the <math>2</math>'s region, we try placing the <math>2's</math>, we can only place them in the <math>3</math> region in order to fit the <math>3</math>'s. Therefore, this entire case produces <math>2</math> arrangements. \\
 +
 +
Case 2: They are in a different region
 +
 +
There are <math>4</math> ways that the <math>1</math>'s can be in different regions. For the <math>2</math>'s and <math>3</math>'s, they will have to go in each other's region with <math>1</math> and the other can be arranged in <math>2</math> ways in the <math>1</math> region giving a total of <math>8</math> for this case.\\
 +
 +
Finally, <math>90(2+8) = 900</math>
 +
 +
~Vedoral
 +
 +
==Graph Theory Insight==
 +
This is a bipartite graph perfect matching problem.  This bipartite graph has <math>3!=6</math> perfect matchings.  Arranging these 6 perfect matchings in 6 rounds gives <math>6!=720</math> ways of scheduling, as Solution 1 states. But Solution 1 did not write about why there are 90 ways to make the schedule that two rounds are repeated, and why 90 is added twice.
 +
Let's call round 1 and 2  <math>P</math>, round 3 and 4  <math>Q</math>, round 5 and 6  <math>R</math>.
 +
Round 1----><math>AX</math> <math>BZ</math> <math>CY</math>    <math>P</math>
 +
Round 2----><math>AX</math> <math>BZ</math> <math>CY</math>    <math>P</math>
 +
Round 3----><math>AY</math> <math>BX</math> <math>CZ</math>    <math>Q</math>
 +
Round 4----><math>AY</math> <math>BX</math> <math>CZ</math>    <math>Q</math>
 +
Round 5----><math>AZ</math> <math>BY</math> <math>CX</math>    <math>R</math>
 +
Round 6----><math>AZ</math> <math>BY</math> <math>CX</math>    <math>R</math>
 +
And now the schedule is simply the permutation of <math>PPQQRR</math>, which is:
 +
<math>\frac{6!}{2!2!2!}</math> = <math>90</math>
 +
So now we have to figure out how many <math>PPQQRR</math>s there are. We first put in the <math>AX</math>, <math>AY</math>, and <math>AZ</math>:
 +
<math>P</math>----><math>AX</math>
 +
<math>Q</math>----><math>AY</math>
 +
<math>R</math>----><math>AZ</math>
 +
Then there are 2 ways to put in <math>B</math>'s match in <math>P</math>:
 +
 +
a)
 +
<math>P</math>----><math>AX</math> <math>BY</math>
 +
<math>Q</math>----><math>AY</math>
 +
<math>R</math>----><math>AZ</math>
 +
b)
 +
<math>P</math>----><math>AX</math> <math>BZ</math>
 +
<math>Q</math>----><math>AY</math>
 +
<math>R</math>----><math>AZ</math>
 +
Now we fill in <math>B</math>'s match for <math>Q</math> and <math>R</math>.
 +
Notice how that for each a) and b) there is only one way to fill in <math>B</math>'s match for <math>Q</math> and <math>R</math>. For a), if we put <math>BX</math> in <math>Q</math>, then <math>BZ</math> must be in <math>R</math>. But <math>AZ</math> is already in <math>R</math>, which makes it impossible. For b), if we put <math>BY</math> in <math>Q</math>, <math>BX</math> must be in <math>R</math>. Then, <math>CY</math> has to be in both <math>P</math> and <math>R</math> which is impossible. So there is only one way to fill in <math>B</math>'s match for <math>Q</math> and <math>R</math>.
 +
 +
a)
 +
<math>P</math>----><math>AX</math> <math>BY</math>
 +
<math>Q</math>----><math>AY</math> <math>BZ</math>
 +
<math>R</math>----><math>AZ</math> <math>BX</math>
 +
b)
 +
<math>P</math>----><math>AX</math> <math>BZ</math>
 +
<math>Q</math>----><math>AY</math> <math>BX</math>
 +
<math>R</math>----><math>AZ</math> <math>BY</math>
 +
Now we fill in <math>C</math>'s matchs:
 +
 +
a)
 +
<math>P</math>----><math>AX</math> <math>BY</math> <math>CZ</math>
 +
<math>Q</math>----><math>AY</math> <math>BZ</math> <math>CX</math>
 +
<math>R</math>----><math>AZ</math> <math>BX</math> <math>CY</math>
 +
b)
 +
<math>P</math>----><math>AX</math> <math>BZ</math> <math>CY</math>
 +
<math>Q</math>----><math>AY</math> <math>BX</math> <math>CZ</math>
 +
<math>R</math>----><math>AZ</math> <math>BY</math> <math>CX</math>
 +
There are 2 <math>PPQQRR</math>s, therefore 90 must be added twice.
 +
 +
~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen]
 +
 +
==Video Solution by Richard Rusczyk==
 +
https://artofproblemsolving.com/videos/amc/2013amc10a/358
  
 
==See Also==
 
==See Also==
  
 
{{AMC10 box|year=2013|ab=A|num-b=23|num-a=25}}
 
{{AMC10 box|year=2013|ab=A|num-b=23|num-a=25}}
 +
 +
[[Category:Introductory Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 19:13, 15 July 2024

Problem

Central High School is competing against Northern High School in a backgammon match. Each school has three players, and the contest rules require that each player play two games against each of the other school's players. The match takes place in six rounds, with three games played simultaneously in each round. In how many different ways can the match be scheduled?

$\textbf{(A)}\ 540\qquad\textbf{(B)}\ 600\qquad\textbf{(C)}\ 720\qquad\textbf{(D)}\ 810\qquad\textbf{(E)}\ 900$

Solution 1

Let us label the players of the first team $A$, $B$, and $C$, and those of the second team, $X$, $Y$, and $Z$.

$\textbf{1}$. One way of scheduling all six distinct rounds could be:

Round 1: $AX$ $BY$ $CZ$

Round 2: $AX$ $BZ$ $CY$

Round 3: $AY$ $BX$ $CZ$

Round 4: $AY$ $BZ$ $CX$

Round 5: $AZ$ $BX$ $CY$

Round 6: $AZ$ $BY$ $CX$


The above mentioned schedule ensures that each player of one team plays twice with each player from another team. Now you can generate a completely new schedule by permutating those $6$ rounds and that can be done in $6!=720$ ways.

$\textbf{2}$. One can also make the schedule in such a way that two rounds are repeated.

(a)

Round 1: $AX$ $BZ$ $CY$

Round 2: $AX$ $BZ$ $CY$

Round 3: $AY$ $BX$ $CZ$

Round 4: $AY$ $BX$ $CZ$

Round 5: $AZ$ $BY$ $CX$

Round 6: $AZ$ $BY$ $CX$

(b)

Round 1: $AX$ $BY$ $CZ$

Round 2: $AX$ $BY$ $CZ$

Round 3: $AY$ $BZ$ $CX$

Round 4: $AY$ $BZ$ $CX$

Round 5: $AZ$ $BX$ $CY$

Round 6: $AZ$ $BX$ $CY$

As mentioned earlier any permutation of (a) and (b) will also give us a new schedule. For both (a) and (b) the number of permutations are $\frac{6!}{2!2!2!}$ = $90$


So the total number of schedules is $720+90+90$ =$\boxed{\textbf{(E)} 900}$.

Solution 2

Label the players of the first team $A$, $B$, and $C$, and those of the second team, $X$, $Y$, and $Z$. We can start by assigning an opponent to person $A$ for all $6$ games. Since $A$ has to play each of $X$, $Y$, and $Z$ twice, there are $\frac{6!}{2!2!2!} = 90$ ways to do this. We can assume that the opponents for $A$ in the $6$ rounds are $X$, $X$, $Y$, $Y$, $Z$, $Z$ and multiply by $90$ afterwards.


Notice that for every valid assignment of the opponents of $A$ and $B$, there is only $1$ valid assignment of opponents for $C$. More specifically, the opponents for $C$ are the leftover opponents after the opponents for $A$ and $B$ are chosen in each round. Therefore, all we have to do is assign the opponents for $B$. This is the same as finding the number of permutations of $X$, $Y$, and $Z$ that do not have a $X$ in the first two spots, an $Y$ in the next two spots, and a $Z$ in the final two spots.


We can use casework to find this by using the fact that after we put down the $X$'s and $Y$'s first there is $1$ way to put down the $Z$'s (the two remaining spots).

If $X$'s are put in the middle $2$ spots, then there is $1$ way to assign spots to $Y$, namely the last $2$ spots. (If one of the last two spots are left empty, there will have to be a $Z$ there, which which not valid).

If $X$'s are put in the last $2$ spots, then there is $1$ way to assign spots to $Y$.

Finally, if one $X$ was put in on of the middle two spots and one $X$ was put in one of the last two spots, there are $2\cdot2$ ways to assign spots to $X$ and $2\cdot1$ ways to assign spots to $Y$ (one of the first two spots and the remaining spot in the last $2$).

There are $1+1+2\cdot2\cdot2\cdot1 = 10$ ways to assign opponents to $B$ and $90\cdot10 = 900$ ways to order the games. $\boxed{\textbf{(E)} 900}$

Solution 3(similar to 2)

We only need to worry about what the other member of the pair would be for our own competitors. If our competitors are $A,B,C$ and the others are $1,2,3$, then we only need to arrange the numbers $1,1,2,2,3,3$ such that we don't have the same number in the same spots. For our first row of numbers, or our first player, they can be arranged in any of \[\frac{6!}{2!2!2!}\] ways as nothing has happened yet. This contributes $90$ to our final product. Once we determine our second row, or player, the third will immediately follow thus we only need to figure out the second one. WLOG, our first arrangement was $112233$. For our $1$'s, we can put them anywhere that is not in our first $2$ spots. If we put both of them in the same "region", like the $2$'s or the $3$'s, then it will give a different case than if they were in different regions.

Case 1 : They are in the same region

There are $2$ ways that the $1$'s can be in the same region. If, let's say its in the $2$'s region, we try placing the $2's$, we can only place them in the $3$ region in order to fit the $3$'s. Therefore, this entire case produces $2$ arrangements. \\

Case 2: They are in a different region

There are $4$ ways that the $1$'s can be in different regions. For the $2$'s and $3$'s, they will have to go in each other's region with $1$ and the other can be arranged in $2$ ways in the $1$ region giving a total of $8$ for this case.\\

Finally, $90(2+8) = 900$

~Vedoral

Graph Theory Insight

This is a bipartite graph perfect matching problem. This bipartite graph has $3!=6$ perfect matchings. Arranging these 6 perfect matchings in 6 rounds gives $6!=720$ ways of scheduling, as Solution 1 states. But Solution 1 did not write about why there are 90 ways to make the schedule that two rounds are repeated, and why 90 is added twice. Let's call round 1 and 2 $P$, round 3 and 4 $Q$, round 5 and 6 $R$. 

Round 1---->$AX$ $BZ$ $CY$    $P$
Round 2---->$AX$ $BZ$ $CY$    $P$
Round 3---->$AY$ $BX$ $CZ$    $Q$
Round 4---->$AY$ $BX$ $CZ$    $Q$
Round 5---->$AZ$ $BY$ $CX$    $R$
Round 6---->$AZ$ $BY$ $CX$    $R$

And now the schedule is simply the permutation of $PPQQRR$, which is: $\frac{6!}{2!2!2!}$ = $90$ So now we have to figure out how many $PPQQRR$s there are. We first put in the $AX$, $AY$, and $AZ$: 

$P$---->$AX$
$Q$---->$AY$
$R$---->$AZ$

Then there are 2 ways to put in $B$'s match in $P$:

a) 

$P$---->$AX$ $BY$
$Q$---->$AY$
$R$---->$AZ$

b) 

$P$---->$AX$ $BZ$
$Q$---->$AY$
$R$---->$AZ$

Now we fill in $B$'s match for $Q$ and $R$. Notice how that for each a) and b) there is only one way to fill in $B$'s match for $Q$ and $R$. For a), if we put $BX$ in $Q$, then $BZ$ must be in $R$. But $AZ$ is already in $R$, which makes it impossible. For b), if we put $BY$ in $Q$, $BX$ must be in $R$. Then, $CY$ has to be in both $P$ and $R$ which is impossible. So there is only one way to fill in $B$'s match for $Q$ and $R$.

a) 

$P$---->$AX$ $BY$
$Q$---->$AY$ $BZ$
$R$---->$AZ$ $BX$

b) 

$P$---->$AX$ $BZ$
$Q$---->$AY$ $BX$
$R$---->$AZ$ $BY$

Now we fill in $C$'s matchs:

a) 

$P$---->$AX$ $BY$ $CZ$
$Q$---->$AY$ $BZ$ $CX$
$R$---->$AZ$ $BX$ $CY$

b) 

$P$---->$AX$ $BZ$ $CY$
$Q$---->$AY$ $BX$ $CZ$
$R$---->$AZ$ $BY$ $CX$

There are 2 $PPQQRR$s, therefore 90 must be added twice.

~isabelchen

Video Solution by Richard Rusczyk

https://artofproblemsolving.com/videos/amc/2013amc10a/358

See Also

2013 AMC 10A (Problems • Answer Key • Resources)
Preceded by
Problem 23 		Followed by
Problem 25
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_AMC_10A_Problems/Problem_24&oldid=222666"