Difference between revisions of "2017 AMC 12B Problems/Problem 22"
(→Solution 2 (Less Casework)) |
m (→Solution 2 (Less Casework)) |
||
(18 intermediate revisions by 11 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Problem | + | ==Problem== |
Abby, Bernardo, Carl, and Debra play a game in which each of them starts with four coins. The game consists of four rounds. In each round, four balls are placed in an urn---one green, one red, and two white. The players each draw a ball at random without replacement. Whoever gets the green ball gives one coin to whoever gets the red ball. What is the probability that, at the end of the fourth round, each of the players has four coins? | Abby, Bernardo, Carl, and Debra play a game in which each of them starts with four coins. The game consists of four rounds. In each round, four balls are placed in an urn---one green, one red, and two white. The players each draw a ball at random without replacement. Whoever gets the green ball gives one coin to whoever gets the red ball. What is the probability that, at the end of the fourth round, each of the players has four coins? | ||
<math>\textbf{(A)}\quad \dfrac{7}{576} \qquad \qquad \textbf{(B)}\quad \dfrac{5}{192} \qquad\qquad \textbf{(C)}\quad \dfrac{1}{36} \qquad\qquad \textbf{(D)}\quad \dfrac{5}{144} \qquad\qquad\textbf{(E)}\quad \dfrac{7}{48}</math> | <math>\textbf{(A)}\quad \dfrac{7}{576} \qquad \qquad \textbf{(B)}\quad \dfrac{5}{192} \qquad\qquad \textbf{(C)}\quad \dfrac{1}{36} \qquad\qquad \textbf{(D)}\quad \dfrac{5}{144} \qquad\qquad\textbf{(E)}\quad \dfrac{7}{48}</math> | ||
− | ==Solution== | + | ==Solution 1== |
− | It amounts to filling in a <math>4 \times 4</math> matrix. Columns <math>C_1 - C_4</math> are the random draws each round; | + | It amounts to filling in a <math>4 \times 4</math> matrix. Columns <math>C_1 - C_4</math> are the random draws each round; rowof each player. Also, let <math>\%R_A</math> be the number of nonzero elements in <math>R_A</math>. |
+ | Sidenote: (Not the author)(What does -1, 1, and 0, and R notation represent)? | ||
WLOG, let <math>C_1 = \begin{pmatrix} 1\\-1\\0\\0\end{pmatrix}</math>. Parity demands that <math>\%R_A</math> and <math>\%R_B</math> must equal <math>2</math> or <math>4</math>. | WLOG, let <math>C_1 = \begin{pmatrix} 1\\-1\\0\\0\end{pmatrix}</math>. Parity demands that <math>\%R_A</math> and <math>\%R_B</math> must equal <math>2</math> or <math>4</math>. | ||
Line 20: | Line 21: | ||
Hence, there are <math>3(2+2 \cdot 2)=18</math> ways for this case. | Hence, there are <math>3(2+2 \cdot 2)=18</math> ways for this case. | ||
− | There's a grand total of <math>45</math> ways for this to happen, along with <math>12^3</math> total cases. The probability we're asking for is thus <math>\frac{45}{(12^3)}=\frac{5}{192} | + | There's a grand total of <math>45</math> ways for this to happen, along with <math>12^3</math> total cases. The probability we're asking for is thus <math>\frac{45}{(12^3)}= \boxed{\textbf{(B)}\frac{5}{192}}</math>. |
==Solution 2 (Less Casework)== | ==Solution 2 (Less Casework)== | ||
Line 26: | Line 27: | ||
Basically, (like the previous solution), we think of this as filling out a <math>4\text{x}2</math> matrix of letters, where a letter on the left column represents this person gave, and a letter on the right column means this person received. We need to make sure that for each person that gave in total certain amount, they received in total from other people that same amount, or in other words, we want it such that there are an equal number of A's, B's, C's, and D's in both columns of the matrix. | Basically, (like the previous solution), we think of this as filling out a <math>4\text{x}2</math> matrix of letters, where a letter on the left column represents this person gave, and a letter on the right column means this person received. We need to make sure that for each person that gave in total certain amount, they received in total from other people that same amount, or in other words, we want it such that there are an equal number of A's, B's, C's, and D's in both columns of the matrix. | ||
− | For example, the matrix below represents: A gives B a coin, then B gives C a coin, C gives D a coin, and finally A gives D a coin, in this order. | + | For example, the matrix below represents: A gives B a coin, then B gives C a coin, then C gives D a coin, and finally A gives D a coin, in this order. |
<cmath>\[ | <cmath>\[ | ||
\begin{bmatrix} & A & B & \\ | \begin{bmatrix} & A & B & \\ | ||
Line 36: | Line 37: | ||
Case 1: <math>2</math> people. In this case, we have <math>\binom{4}{2}</math> ways to choose the two people, and <math>\binom{4}{2}</math> ways to order them to get a count of <math>{\binom{4}{2}}^2 = 36</math> ways. | Case 1: <math>2</math> people. In this case, we have <math>\binom{4}{2}</math> ways to choose the two people, and <math>\binom{4}{2}</math> ways to order them to get a count of <math>{\binom{4}{2}}^2 = 36</math> ways. | ||
− | Case 2: <math>3</math> people. In this case, one special person is giving/receiving twice. There are four ways to choose this person, then of the remaining three people we choose two, to be the people | + | Case 2: <math>3</math> people. In this case, one special person is giving/receiving twice. There are four ways to choose this person, then of the remaining three people we choose two, to be the people interacting with the special person. Thus, we have <math>4\cdot\binom{3}{2}\cdot4! = 288</math> ways here. |
− | Case 3: <math>4</math> people | + | Case 3: <math>4</math> people. If we keep the order of A, B, C, D giving in that order (and permute afterward), then there are three options to choose A's receiver, and three options for B's receiver afterward. Then it is uniquely determined who C and D give to. This gives a total of <math>3\cdot3\cdot4! = 216</math> ways, after permuting. |
Line 44: | Line 45: | ||
Now we divide this by the total number of ways: <math>(4\cdot3)^4</math> | Now we divide this by the total number of ways: <math>(4\cdot3)^4</math> | ||
(four rounds, four ways to choose giver, three to choose receiver each round). | (four rounds, four ways to choose giver, three to choose receiver each round). | ||
− | So the answer is <math>\frac{540}{12^4} = \frac{5}{192}</math>. | + | So the answer is <math>\frac{540}{12^4} = \boxed{\textbf{(B)}\frac{5}{192}}</math>. |
~ccx09 | ~ccx09 | ||
− | + | Latex polished by Argonauts16 and by [[Grace.yongqing.yu]]. | |
− | + | ==Solution 3== | |
+ | Similar to solution 2, we think in terms of transactions. WLOG, for the 1st transaction, we assume that A gives to B, which we denote AB. For the 2nd transaction, there are 12 options to choose from, so there are <math>12^3</math> possible options. | ||
+ | |||
+ | Case 1 (Giving back immediately): The 2nd transaction is BA (1 option). Then, the 3rd transaction can be whatever you like (12 options), but the 4th transaction is now fixed to be the opposite of the 3rd transaction (1 option). So here we have <math>1\cdot 12\cdot 1 = 12</math> good options. | ||
+ | |||
+ | Case 2 (Allows a cycle or two back-and-forths): The 2nd transaction is one of BC, BD, CA, DA, CD, DC (6 options). Then, for the 3rd transaction, 2 options force a "cycle" on the 4th transaction (example 2.1), and 2 options force two "back-and-forths" on the 4th transaction (example 2.2). In total, there are <math>2+2=4</math> options for the 3rd transaction. So here we have <math>6\cdot 4\cdot 1 = 24</math> good options. | ||
+ | |||
+ | Example 2.1: suppose 2nd = BC. Then if 3rd = DA or CD, the 4th is forced to be CD or DA respectively, completing a transaction "cycle" | ||
+ | |||
+ | Example 2.2: suppose 2nd = BC. Then if 3rd = AB or BC, the 4th is forced to be BC or AB respectively. In the end, both A-B and B-C had back-and-forth transactions | ||
+ | |||
+ | Case 3 (Allows two back-and-forths only): The 2nd transaction is one of AC, AD, DB, CB (4 options). Then, for the 3th transaction, there are only 2 possible options (namely, to reverse one of the previous transactions). Of course, the final transaction is forced. Here, we have <math>4\cdot 2\cdot 1 = 8</math> good options. | ||
+ | |||
+ | Case 4 (AB again): The 2nd transaction is AB (same as 1st). This forces the later transactions to both be BA. Here we have 1 good option. | ||
+ | |||
+ | Summing, we have <math>12+24+8+1=45</math> good options among <math>12^3</math> total options, so the solution is <math>\frac{45}{(12^3)}= \boxed{\textbf{(B)}\frac{5}{192}}</math>. | ||
+ | |||
+ | SilverLion | ||
+ | |||
+ | |||
+ | == Solution 4 == | ||
+ | |||
+ | Define a cycle of length <math>n</math> to be a sequence of <math>n</math> transactions, starting and ending with the same person. For example, <math>A \to B, B \to C, C \to A</math> would be a cycle of <math>3</math>. | ||
+ | |||
+ | <math>\textbf{Case 1}</math>: Two different cycles of <math>2</math>: There are <math>\binom{4}{2}</math> to choose the people for each cycle, giving <math>\binom{\binom{4}{2}}{2} = 15</math> possible ways to choose the two cycles. Then, there would be <math>4! = 24</math> ways to order the transactions. This will mean <math>15\cdot 24 = 360</math> ways for the first case. | ||
+ | |||
+ | <math>\textbf{Case 2}</math>: Two same cycles of <math>2</math>: There are <math>\binom{4}{2}</math> to choose the two people, multiplying by <math>\binom{4}{2}</math> for the number of orderings of the four transactions. Thus, <math>6\cdot 6 = 36</math> ways for this case. | ||
+ | |||
+ | <math>\textbf{Case 3}</math>: One cycle of <math>4</math>: We choose what goes in front of <math>A</math> (whom <math>A</math> gives a coin to) in <math>3</math> ways, and what goes before <math>A</math> (whom gives a coin to <math>A</math>) in <math>2</math> ways. The remaining two transactions immediately get fixed after that. Again, there are <math>4! = 24</math> ways to order the four transactions, giving <math>2\cdot 3\cdot 24 = 144</math> ways for this case. | ||
+ | |||
+ | Thus, there would be a total of <math>360+36+144 = 540</math> total ways: <math>P = \dfrac{540}{12^4} = \boxed{\textbf{(B)}\frac{5}{192}}</math> | ||
+ | |||
+ | ~sml1809 | ||
+ | |||
+ | === Visualization of three cases === | ||
+ | |||
+ | https://www.happymatheducation.com/uploads/1/3/6/4/136474762/2017amc12b22.jpg | ||
+ | |||
+ | ~Di | ||
+ | |||
+ | ==Solution 5 (Casework)== | ||
+ | |||
+ | Let the notation <math>(a,b,c,d)</math> be the arrangement of the <math>16</math> coins, where order does not matter. Notice that after the first round, <math>(3,5,4,4)</math> is the only possible arrangement. Also, notice that the arrangement after the third round also has to be <math>(3,5,4,4)</math> for the arrangement at the end of the fourth round to return to <math>(4,4,4,4)</math>. The probability of <math>(4,4,4,4)</math> occurring after <math>(3,5,4,4)</math> is <math>\frac{1}{12}</math> | ||
+ | |||
+ | After the arrangement <math>(3,5,4,4)</math>, there are <math>12</math> permutations that are <math>6</math> different arrangements, they are: | ||
+ | <cmath>\begin{align*} | ||
+ | (2,6,4,4) \text{ occurs once} \quad & (4,4,4,4) \text{ occurs once} \quad & (2,5,5,4) \text{ occurs twice}\\ | ||
+ | (4,5,3,4) \text{ occurs 4 times} \quad & (3,6,3,4) \text{ occurs twice} \quad & (3,5,3,5) \text{ occurs twice}\\ | ||
+ | \end{align*}</cmath> | ||
+ | |||
+ | Therefore, we can create <math>6</math> cases and calculate the probability of each case occurring. For each case, only the arrangement after the second round is different, therefore, we will ignore the probability for the fourth round, and consider it in the end when adding the cases. | ||
+ | Case 1: <math>(2,6,4,4)</math> | ||
+ | The probability of <math>(2,6,4,4)</math> occurring after the second round is <math>\frac{1}{12}</math>. | ||
+ | The probability of <math>(3,5,4,4)</math> occurring after <math>(2,6,4,4)</math> is <math>\frac{1}{12}</math>. | ||
+ | <math>\frac{1}{12} \cdot \frac{1}{12} = \frac{1}{144}</math> | ||
+ | |||
+ | Case 2: <math>(4,4,4,4)</math> | ||
+ | The probability of <math>(4,4,4,4)</math> occurring after the second round is <math>\frac{1}{12}</math>. | ||
+ | The probability of <math>(3,5,4,4)</math> occurring after <math>(4,4,4,4)</math> is <math>1</math>. | ||
+ | <math>\frac{1}{12} \cdot 1 = \frac{1}{12}</math> | ||
+ | |||
+ | Case 3: <math>(2,5,5,4)</math> | ||
+ | The probability of <math>(2,5,5,4)</math> occurring after the second round is <math>\frac{1}{6}</math>. | ||
+ | The probability of <math>(3,5,4,4)</math> occurring after <math>(2,5,5,4)</math> is <math>\frac16</math>. | ||
+ | <math>\frac{1}{6} \cdot \frac{1}{6} = \frac{1}{36}</math> | ||
+ | |||
+ | Case 4: <math>(4,5,3,4)</math> | ||
+ | The probability of <math>(4,5,3,4)</math> occurring after the second round is <math>\frac{1}{3}</math>. | ||
+ | The probability of <math>(3,5,4,4)</math> occurring after <math>(4,5,3,4)</math> is <math>\frac{1}{3}</math>. | ||
+ | <math>\frac{1}{3} \cdot \frac{1}{3} = \frac{1}{9}</math> | ||
+ | |||
+ | Case 5: <math>(3,6,3,4)</math> | ||
+ | The probability of <math>(3,6,3,4)</math> occurring after the second round is <math>\frac{1}{6}</math>. | ||
+ | The probability of <math>(3,5,4,4)</math> occurring after <math>(3,6,3,4)</math> is <math>\frac{1}{6}</math>. | ||
+ | <math>\frac{1}{6} \cdot \frac{1}{6} = \frac{1}{36}</math> | ||
+ | |||
+ | Case 6: <math>(3,5,3,5)</math> | ||
+ | The probability of <math>(3,5,3,5)</math> occurring after the second round is <math>\frac{1}{6}</math>. | ||
+ | The probability of <math>(3,5,4,4)</math> occurring after <math>(3,5,3,5)</math> is <math>\frac{1}{3}</math>. | ||
+ | <math>\frac{1}{6} \cdot \frac{1}{3} = \frac{1}{18}</math> | ||
+ | |||
+ | The probability that at the end of the fourth round the arrangement is <math>(4,4,4,4)</math> is | ||
+ | <cmath>\frac{1}{12} \left( \frac{1}{144} + \frac{1}{12} + \frac{1}{36} + \frac19 + \frac{1}{36} + \frac{1}{18} \right) = \boxed{\textbf{(B)}\frac{5}{192}}</cmath> | ||
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ||
==See Also== | ==See Also== |
Latest revision as of 19:24, 19 August 2024
Contents
Problem
Abby, Bernardo, Carl, and Debra play a game in which each of them starts with four coins. The game consists of four rounds. In each round, four balls are placed in an urn---one green, one red, and two white. The players each draw a ball at random without replacement. Whoever gets the green ball gives one coin to whoever gets the red ball. What is the probability that, at the end of the fourth round, each of the players has four coins?
Solution 1
It amounts to filling in a matrix. Columns
are the random draws each round; rowof each player. Also, let
be the number of nonzero elements in
.
Sidenote: (Not the author)(What does -1, 1, and 0, and R notation represent)?
WLOG, let . Parity demands that
and
must equal
or
.
Case 1: and
. There are
ways to place
's in
, so there are
ways.
Case 2: and
. There are
ways to place the
in
,
ways to place the remaining
in
(just don't put it under the
on top of it!), and
ways for one of the other two players to draw the green ball. (We know it's green because Bernardo drew the red one.) We can just double to cover the case of
,
for a total of
ways.
Case 3: . There are three ways to place the
in
. Now, there are two cases as to what happens next.
Sub-case 3.1: The in
goes directly under the
in
. There's obviously
way for that to happen. Then, there are
ways to permute the two pairs of
in
and
. (Either the
comes first in
or the
comes first in
.)
Sub-case 3.2: The in
doesn't go directly under the
in
. There are
ways to place the
, and
ways to do the same permutation as in Sub-case 3.1.
Hence, there are
ways for this case.
There's a grand total of ways for this to happen, along with
total cases. The probability we're asking for is thus
.
Solution 2 (Less Casework)
We will proceed by taking cases based on how many people are taking part in this "transaction." We can have ,
, or
people all giving/receiving coins during the
turns.
Basically, (like the previous solution), we think of this as filling out a
matrix of letters, where a letter on the left column represents this person gave, and a letter on the right column means this person received. We need to make sure that for each person that gave in total certain amount, they received in total from other people that same amount, or in other words, we want it such that there are an equal number of A's, B's, C's, and D's in both columns of the matrix.
For example, the matrix below represents: A gives B a coin, then B gives C a coin, then C gives D a coin, and finally A gives D a coin, in this order.
Case 1:
people. In this case, we have
ways to choose the two people, and
ways to order them to get a count of
ways.
Case 2: people. In this case, one special person is giving/receiving twice. There are four ways to choose this person, then of the remaining three people we choose two, to be the people interacting with the special person. Thus, we have
ways here.
Case 3: people. If we keep the order of A, B, C, D giving in that order (and permute afterward), then there are three options to choose A's receiver, and three options for B's receiver afterward. Then it is uniquely determined who C and D give to. This gives a total of
ways, after permuting.
So we have a total of ways to order the four pairs of people.
Now we divide this by the total number of ways:
(four rounds, four ways to choose giver, three to choose receiver each round).
So the answer is
.
~ccx09
Latex polished by Argonauts16 and by Grace.yongqing.yu.
Solution 3
Similar to solution 2, we think in terms of transactions. WLOG, for the 1st transaction, we assume that A gives to B, which we denote AB. For the 2nd transaction, there are 12 options to choose from, so there are possible options.
Case 1 (Giving back immediately): The 2nd transaction is BA (1 option). Then, the 3rd transaction can be whatever you like (12 options), but the 4th transaction is now fixed to be the opposite of the 3rd transaction (1 option). So here we have good options.
Case 2 (Allows a cycle or two back-and-forths): The 2nd transaction is one of BC, BD, CA, DA, CD, DC (6 options). Then, for the 3rd transaction, 2 options force a "cycle" on the 4th transaction (example 2.1), and 2 options force two "back-and-forths" on the 4th transaction (example 2.2). In total, there are options for the 3rd transaction. So here we have
good options.
Example 2.1: suppose 2nd = BC. Then if 3rd = DA or CD, the 4th is forced to be CD or DA respectively, completing a transaction "cycle"
Example 2.2: suppose 2nd = BC. Then if 3rd = AB or BC, the 4th is forced to be BC or AB respectively. In the end, both A-B and B-C had back-and-forth transactions
Case 3 (Allows two back-and-forths only): The 2nd transaction is one of AC, AD, DB, CB (4 options). Then, for the 3th transaction, there are only 2 possible options (namely, to reverse one of the previous transactions). Of course, the final transaction is forced. Here, we have good options.
Case 4 (AB again): The 2nd transaction is AB (same as 1st). This forces the later transactions to both be BA. Here we have 1 good option.
Summing, we have good options among
total options, so the solution is
.
SilverLion
Solution 4
Define a cycle of length to be a sequence of
transactions, starting and ending with the same person. For example,
would be a cycle of
.
: Two different cycles of
: There are
to choose the people for each cycle, giving
possible ways to choose the two cycles. Then, there would be
ways to order the transactions. This will mean
ways for the first case.
: Two same cycles of
: There are
to choose the two people, multiplying by
for the number of orderings of the four transactions. Thus,
ways for this case.
: One cycle of
: We choose what goes in front of
(whom
gives a coin to) in
ways, and what goes before
(whom gives a coin to
) in
ways. The remaining two transactions immediately get fixed after that. Again, there are
ways to order the four transactions, giving
ways for this case.
Thus, there would be a total of total ways:
~sml1809
Visualization of three cases
https://www.happymatheducation.com/uploads/1/3/6/4/136474762/2017amc12b22.jpg
~Di
Solution 5 (Casework)
Let the notation be the arrangement of the
coins, where order does not matter. Notice that after the first round,
is the only possible arrangement. Also, notice that the arrangement after the third round also has to be
for the arrangement at the end of the fourth round to return to
. The probability of
occurring after
is
After the arrangement , there are
permutations that are
different arrangements, they are:
Therefore, we can create cases and calculate the probability of each case occurring. For each case, only the arrangement after the second round is different, therefore, we will ignore the probability for the fourth round, and consider it in the end when adding the cases.
Case 1:The probability of
occurring after the second round is
. The probability of
occurring after
is
.
![]()
Case 2:The probability of
occurring after the second round is
. The probability of
occurring after
is
.
![]()
Case 3:The probability of
occurring after the second round is
. The probability of
occurring after
is
.
![]()
Case 4:The probability of
occurring after the second round is
. The probability of
occurring after
is
.
![]()
Case 5:The probability of
occurring after the second round is
. The probability of
occurring after
is
.
![]()
Case 6:The probability of
occurring after the second round is
. The probability of
occurring after
is
.
![]()
The probability that at the end of the fourth round the arrangement is is
See Also
2017 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.