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 "2019 AMC 10B Problems/Problem 22"

m (→‎Solution)
(→‎Solution 1)
(21 intermediate revisions by 12 users not shown)
Line 3: Line 3:
 
==Problem==
 
==Problem==
  
−
Raashan, Sylvia, and TED play the following game. Each starts with <math> \$1</math>. A bell rings every <math>15</math> seconds, at which time each of the players who currently have money simultaneously chooses one of the other two players independently and at random and gives <math>\$1</math> to that player. What is the probability that after the bell has rung <math>2019</math> times, each player will have <math>\$1</math>? (For example, Raashan and Ted may each decide to give <math>\$1</math> to Sylvia, and Sylvia may decide to give her her dollar to Ted, at which point Raashan will have <math>\$0</math>, Sylvia will have <math>\$2</math>, and Ted will have <math>\$1</math>, and that is the end of the first round of play. In the second round Rashaan has no money to give, but Sylvia and Ted might choose each other to give their <math> \$1</math> to, and the holdings will be the same at the end of the second round.)
+
Raashan, Sylvia, and Ted play the following game. Each starts with <math> \$1</math>. A bell rings every <math>15</math> seconds, at which time each of the players who currently have money simultaneously chooses one of the other two players independently and at random and gives <math>\$1</math> to that player. What is the probability that after the bell has rung <math>2019</math> times, each player will have <math>\$1</math>? (For example, Raashan and Ted may each decide to give <math>\$1</math> to Sylvia, and Sylvia may decide to give her dollar to Ted, at which point Raashan will have <math>\$0</math>, Sylvia will have <math>\$2</math>, and Ted will have <math>\$1</math>, and that is the end of the first round of play. In the second round Rashaan has no money to give, but Sylvia and Ted might choose each other to give their <math> \$1</math> to, and the holdings will be the same at the end of the second round.)
  
 
<math>\textbf{(A) } \frac{1}{7} \qquad\textbf{(B) } \frac{1}{4} \qquad\textbf{(C) } \frac{1}{3} \qquad\textbf{(D) } \frac{1}{2} \qquad\textbf{(E) } \frac{2}{3}</math>
 
<math>\textbf{(A) } \frac{1}{7} \qquad\textbf{(B) } \frac{1}{4} \qquad\textbf{(C) } \frac{1}{3} \qquad\textbf{(D) } \frac{1}{2} \qquad\textbf{(E) } \frac{2}{3}</math>
  
 
==Solution 1==
 
==Solution 1==
−
On the first turn, each player starts off with <math>\$1</math>. Each turn after that, there are only two possibilities: either everyone stays at <math>\$1</math>, which we will write as <math>(1-1-1)</math>, or the distribution of money becomes <math>\$2-\$1-\$0</math> in some order, which we write as <math>(2-1-0)</math>. We will consider these two states separately.
+
On the first turn, each player starts off with <math>\$1</math>. Each turn after that, there are only two possibilities: either everyone stays at <math>\$1</math>, which we will write as <math>(1-1-1)</math>, or the distribution of money becomes <math>\$2-\$1-\$0</math> in some order, which we write as <math>(2-1-0)</math>. (<math>(3-0-0)</math> cannot be achieved since either(1)the person cannot give money to himself or (2)there are a maximum of 2 dollars being distributed and the person has nothing to start with). We will consider these two states separately.
  
 
In the <math>(1-1-1)</math> state, each person has two choices for whom to give their dollar to, meaning there are <math>2^3=8</math> possible ways that the money can be rearranged. Note that there are only two ways that we can reach <math>(1-1-1)</math> again:  
 
In the <math>(1-1-1)</math> state, each person has two choices for whom to give their dollar to, meaning there are <math>2^3=8</math> possible ways that the money can be rearranged. Note that there are only two ways that we can reach <math>(1-1-1)</math> again:  
Line 16: Line 16:
 
2. Raashan gives his money to Ted, who gives his money to Sylvia, who gives her money to Raashan.
 
2. Raashan gives his money to Ted, who gives his money to Sylvia, who gives her money to Raashan.
  
−
Thus, the probability of staying in the <math>(1-1-1)</math> state is <math>\frac{1}{4}</math>, while the probability of going to the <math>(2-1-0)</math> state is <math>\frac{3}{4}</math> (we can check that the 6 other possibilities lead to <math>(2-1-0)</math>)
+
Thus, the probability of staying in the <math>(1-1-1)</math> state is <math>\frac{1}{4}</math>, while the probability of going to the <math>(2-1-0)</math> state is <math>\frac{3}{4}</math> (we can check that the 6 other possibilities lead to <math>(2-1-0)</math>).
  
  
Line 24: Line 24:
  
 
==Solution 2 (Symmetry)==
 
==Solution 2 (Symmetry)==
−
After the first ring, either nothing changes, or someone has <math>\$2</math>. No one can have <math>\$3</math>, since in that hypothetical round, that person would have to give away <math>\$1</math>.  
+
After the first ring, either nothing changes, or someone has <math>\$2</math>. No one can have <math>\$3</math>, since in that hypothetical round, that person would have to give away <math>\$1</math>. Thus, the outcome is either <math>1-1-1</math> or six symmetrical cases where one person gets <math>\$2</math> (e.g. a <math>1-2-0</math> or <math>2-1-0</math> split).  
  
  
−
Thus, the outcome is either 1-1-1 or six symmetrical cases where one person gets <math>\$2</math> (e.g. a 1-2-0 or 2-1-0 split). There are two ways for the three people to exchange dollars to get to the same 1-1-1 result. As such, there are 8 overall possibilities (which make sense, since each person has 2 choices when giving away his or her dollar, resulting in <math>2^3</math> total possibilities). As such, from the 1-1-1 case, there is a <math>1/4</math> chance of returning to 1-1-1.
+
'''Case 1: Probability of returning to 1-1-1 from 1-1-1'''
  
 +
There are two ways for the three people to exchange dollars to get to the same <math>1-1-1</math> result. To see this, seat R, S, and T in a circle. Each person gives their dollar to either the person at left, or at right, to result in again 1 dollar for each person. There are 8 overall possibilities (since each person has 2 choices when giving away his or her dollar, therefore <math>2^3</math> total possibilities). So, there is <math>1/4</math> chance of returning to <math>1-1-1</math>.
  
−
WLOG, take the 1-2-0 case. Only 2 people can give money, so there are now <math>2^2</math> possible outcomes after the bell rings. It either decomposes back into 1-1-1, remains unchanged, turns into 0-1-2, or turns into 0-2-1. As such, from the 1-1-1 case, there is a <math>1/4</math> chance of returning to 1-1-1. Notice that this works for any of the 6 cases.
 
  
 +
'''Case 2: Probability of returning to 1-1-1 from 2-1-0'''
  
−
Since the starting state has a <math>1/4</math> chance of remaining unchanged, and each of the different 6 symmetric states all also have a <math>1/4</math> chance of reverting back to <math>1-1-1</math>, the chance of it being 1-1-1 after any state is always <math>\boxed{\textbf{(B) } \frac{1}{4}}</math>
+
Without loss of generality, take the <math>2-1-0</math> case. Only 2 people can give money, so there are now <math>2^2=4</math> possible outcomes after the bell rings. It either decomposes back into <math>1-1-1</math>, <math>2-1-0</math> (remained unchanged), <math>2-0-1</math>, <math>1-0-2</math>. Thus, there is a <math>1/4</math> chance of returning to <math>1-1-1</math>. Notice that this works for any of the 6 cases, as each is symmetrical to the others.
 +
 
 +
 
 +
'''Answer'''
 +
 
 +
Since the starting state has a <math>1/4</math> chance of remaining unchanged, and each of the different 6 symmetric states all also have a <math>1/4</math> chance of reverting back to <math>1-1-1</math>, the chance of it being <math>1-1-1</math> after any state is always <math>\boxed{\textbf{(B) } \frac{1}{4}}</math>.
 +
 
 +
==Solution 3==
 +
The two possible scenarios are they all have <math>1</math> dollar, or one person has <math>2</math> dollars, another has <math>1</math>, and the last has none. We will consider the second scenario all to be the same no matter who has the <math>2</math> dollars, <math>1</math> dollar or <math>0</math> dollars from symmetry.
 +
 +
Let's consider all possible scenarios when the bell rings if they currently all have 1 dollar.
 +
<cmath>SRR -> 2, 1, 0</cmath>
 +
<cmath>SRS -> 2, 1, 0</cmath>
 +
<cmath>STR -> 1, 1, 1</cmath>
 +
<cmath>STS -> 2, 1, 0</cmath>
 +
<cmath>TRR -> 2, 1, 0</cmath>
 +
<cmath>TRS -> 1, 1, 1</cmath>
 +
<cmath>TTR -> 2, 1, 0</cmath>
 +
<cmath>TTS -> 2, 1, 0</cmath>
 +
We see that <math>\frac{2}{8}</math> or <math>\frac{1}{4}</math> of the cases lead to them continuing to all of them having <math>1</math> dollar.
 +
Now, let's consider all the possible scenarios when the bell rings if they currently have <math>2, 1, 0</math> dollars. Without loss of generality, let's say that R and S have <math>2</math> and <math>1</math> dollar respectively. (We can switch the names, our answer won't change).
 +
<cmath>SR -> 2, 1, 0</cmath>
 +
<cmath>ST -> 1, 1, 1</cmath>
 +
<cmath>TR -> 2, 1, 0</cmath>
 +
<cmath>TT -> 2, 1, 0</cmath>
 +
We see that <math>\frac{1}{4}</math> of the cases lead to them changing to all have <math>1</math> dollar.
 +
 
 +
So, no matter what was the scenario when the bell had been rung <math>2018</math> times, when the bell is rung the <math>2019</math>th time, there is always a <math>\frac{1}{4}</math> chance that it will turn into (or stay as) <math>(1, 1, 1)</math>
 +
 
 +
==Solution 4 (Markov Chain)==
 +
Let the state <math>(1-1-1)</math> be <math>A</math>, and state <math>(2-1-0)</math> without considering the order be <math>B</math>. Similar to the previous <math>3</math> solutions, after a bell ring, the probability of state <math>A</math> staying in state <math>A</math> is <math>\frac{1}{4}</math>, that of state <math>A</math> transiting to state <math>B</math> is <math>\frac{3}{4}</math>, that of state <math>B</math> staying in state <math>B</math> is <math>\frac{3}{4}</math>, that of state <math>B</math> transiting to state <math>A</math> is <math>\frac{1}{4}</math>. Using a [https://en.wikipedia.org/wiki/Markov_chain Markov Chain], the state transition diagram is shown below.
 +
 
 +
[[File:MarkovChain.png|center|300px]]
 +
 
 +
<cmath>\begin{align}
 +
P_A &= P_A \cdot \frac{1}{4} + P_B \cdot \frac{1}{4} \\
 +
P_B &= P_A \cdot \frac{3}{4} + P_B \cdot \frac{3}{4} \\
 +
&P_A + P_B = 1
 +
\end{align}</cmath>
 +
 
 +
<math>(1)</math> and <math>(2)</math> are equivalent, from <math>(1)</math> or <math>(2)</math>, we get <math>P_B = 3P_A</math>. Solving the system of equations, we get <math>P_A = \boxed{\textbf{(B) } \frac{1}{4}}</math>
 +
 
 +
Note: the number of bell rings doesn't matter, <math>2019</math> is redundant.
 +
 
 +
~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen]
 +
 
 +
==Solution 5 (Risky Guessing)==
 +
This works if one is short on time. Looking at how simple answer choices are, it seems like the number of bell rings is extra information (the other solutions show that this is true). So, we assume that the probability will be the same no matter how many times the bell rings, and we calculate it for <math>1</math> bell ring. Each person can give their dollar to <math>2</math> other people, so there are <math>2^3=8</math> ways to switch up the money. Out of these <math>8</math> ways, <math>2! = 2</math> of them leave everyone with a dollar again, so our probability is <math>\tfrac{2}{8} = \boxed{\textbf{(B) } \frac{1}{4}}</math>.
 +
 
 +
== Video Solution by OmegaLearn ==
 +
https://youtu.be/rLAcJe3o-uA?t=1086
 +
 
 +
~ pi_is_3.14
  
 
==Video Solution==
 
==Video Solution==

Revision as of 10:03, 15 July 2024

The following problem is from both the 2019 AMC 10B #22 and 2019 AMC 12B #19, so both problems redirect to this page.

Problem

Raashan, Sylvia, and Ted play the following game. Each starts with $$1$. A bell rings every $15$ seconds, at which time each of the players who currently have money simultaneously chooses one of the other two players independently and at random and gives $$1$ to that player. What is the probability that after the bell has rung $2019$ times, each player will have $$1$? (For example, Raashan and Ted may each decide to give $$1$ to Sylvia, and Sylvia may decide to give her dollar to Ted, at which point Raashan will have $$0$, Sylvia will have $$2$, and Ted will have $$1$, and that is the end of the first round of play. In the second round Rashaan has no money to give, but Sylvia and Ted might choose each other to give their $$1$ to, and the holdings will be the same at the end of the second round.)

$\textbf{(A) } \frac{1}{7} \qquad\textbf{(B) } \frac{1}{4} \qquad\textbf{(C) } \frac{1}{3} \qquad\textbf{(D) } \frac{1}{2} \qquad\textbf{(E) } \frac{2}{3}$

Solution 1

On the first turn, each player starts off with $$1$. Each turn after that, there are only two possibilities: either everyone stays at $$1$, which we will write as $(1-1-1)$, or the distribution of money becomes $$2-$1-$0$ in some order, which we write as $(2-1-0)$. ($(3-0-0)$ cannot be achieved since either(1)the person cannot give money to himself or (2)there are a maximum of 2 dollars being distributed and the person has nothing to start with). We will consider these two states separately.

In the $(1-1-1)$ state, each person has two choices for whom to give their dollar to, meaning there are $2^3=8$ possible ways that the money can be rearranged. Note that there are only two ways that we can reach $(1-1-1)$ again:

1. Raashan gives his money to Sylvia, who gives her money to Ted, who gives his money to Raashan.

2. Raashan gives his money to Ted, who gives his money to Sylvia, who gives her money to Raashan.

Thus, the probability of staying in the $(1-1-1)$ state is $\frac{1}{4}$, while the probability of going to the $(2-1-0)$ state is $\frac{3}{4}$ (we can check that the 6 other possibilities lead to $(2-1-0)$).


In the $(2-1-0)$ state, we will label the person with $$2$ as person A, the person with $$1$ as person B, and the person with $$0$ as person C. Person A has two options for whom to give money to, and person B has 2 options for whom to give money to, meaning there are total $2\cdot 2 = 4$ ways the money can be redistributed. The only way that the distribution can return to $(1-1-1)$ is if A gives $$1$ to B, and B gives $$1$ to C. We check the other possibilities to find that they all lead back to $(2-1-0)$. Thus, the probability of going to the $(1-1-1)$ state is $\frac{1}{4}$, while the probability of staying in the $(2-1-0)$ state is $\frac{3}{4}$.

No matter which state we are in, the probability of going to the $(1-1-1)$ state is always $\frac{1}{4}$. This means that, after the bell rings 2018 times, regardless of what state the money distribution is in, there is a $\frac{1}{4}$ probability of going to the $(1-1-1)$ state after the 2019th bell ring. Thus, our answer is simply $\boxed{\textbf{(B) } \frac{1}{4}}$.

Solution 2 (Symmetry)

After the first ring, either nothing changes, or someone has $$2$. No one can have $$3$, since in that hypothetical round, that person would have to give away $$1$. Thus, the outcome is either $1-1-1$ or six symmetrical cases where one person gets $$2$ (e.g. a $1-2-0$ or $2-1-0$ split).


Case 1: Probability of returning to 1-1-1 from 1-1-1

There are two ways for the three people to exchange dollars to get to the same $1-1-1$ result. To see this, seat R, S, and T in a circle. Each person gives their dollar to either the person at left, or at right, to result in again 1 dollar for each person. There are 8 overall possibilities (since each person has 2 choices when giving away his or her dollar, therefore $2^3$ total possibilities). So, there is $1/4$ chance of returning to $1-1-1$.


Case 2: Probability of returning to 1-1-1 from 2-1-0

Without loss of generality, take the $2-1-0$ case. Only 2 people can give money, so there are now $2^2=4$ possible outcomes after the bell rings. It either decomposes back into $1-1-1$, $2-1-0$ (remained unchanged), $2-0-1$, $1-0-2$. Thus, there is a $1/4$ chance of returning to $1-1-1$. Notice that this works for any of the 6 cases, as each is symmetrical to the others.


Answer

Since the starting state has a $1/4$ chance of remaining unchanged, and each of the different 6 symmetric states all also have a $1/4$ chance of reverting back to $1-1-1$, the chance of it being $1-1-1$ after any state is always $\boxed{\textbf{(B) } \frac{1}{4}}$.

Solution 3

The two possible scenarios are they all have $1$ dollar, or one person has $2$ dollars, another has $1$, and the last has none. We will consider the second scenario all to be the same no matter who has the $2$ dollars, $1$ dollar or $0$ dollars from symmetry.

Let's consider all possible scenarios when the bell rings if they currently all have 1 dollar. \[SRR -> 2, 1, 0\] \[SRS -> 2, 1, 0\] \[STR -> 1, 1, 1\] \[STS -> 2, 1, 0\] \[TRR -> 2, 1, 0\] \[TRS -> 1, 1, 1\] \[TTR -> 2, 1, 0\] \[TTS -> 2, 1, 0\] We see that $\frac{2}{8}$ or $\frac{1}{4}$ of the cases lead to them continuing to all of them having $1$ dollar. Now, let's consider all the possible scenarios when the bell rings if they currently have $2, 1, 0$ dollars. Without loss of generality, let's say that R and S have $2$ and $1$ dollar respectively. (We can switch the names, our answer won't change). \[SR -> 2, 1, 0\] \[ST -> 1, 1, 1\] \[TR -> 2, 1, 0\] \[TT -> 2, 1, 0\] We see that $\frac{1}{4}$ of the cases lead to them changing to all have $1$ dollar.

So, no matter what was the scenario when the bell had been rung $2018$ times, when the bell is rung the $2019$th time, there is always a $\frac{1}{4}$ chance that it will turn into (or stay as) $(1, 1, 1)$

Solution 4 (Markov Chain)

Let the state $(1-1-1)$ be $A$, and state $(2-1-0)$ without considering the order be $B$. Similar to the previous $3$ solutions, after a bell ring, the probability of state $A$ staying in state $A$ is $\frac{1}{4}$, that of state $A$ transiting to state $B$ is $\frac{3}{4}$, that of state $B$ staying in state $B$ is $\frac{3}{4}$, that of state $B$ transiting to state $A$ is $\frac{1}{4}$. Using a Markov Chain, the state transition diagram is shown below.

MarkovChain.png

\begin{align} P_A &= P_A \cdot \frac{1}{4} + P_B \cdot \frac{1}{4} \\ P_B &= P_A \cdot \frac{3}{4} + P_B \cdot \frac{3}{4} \\ &P_A + P_B = 1 \end{align}

$(1)$ and $(2)$ are equivalent, from $(1)$ or $(2)$, we get $P_B = 3P_A$. Solving the system of equations, we get $P_A = \boxed{\textbf{(B) } \frac{1}{4}}$

Note: the number of bell rings doesn't matter, $2019$ is redundant.

~isabelchen

Solution 5 (Risky Guessing)

This works if one is short on time. Looking at how simple answer choices are, it seems like the number of bell rings is extra information (the other solutions show that this is true). So, we assume that the probability will be the same no matter how many times the bell rings, and we calculate it for $1$ bell ring. Each person can give their dollar to $2$ other people, so there are $2^3=8$ ways to switch up the money. Out of these $8$ ways, $2! = 2$ of them leave everyone with a dollar again, so our probability is $\tfrac{2}{8} = \boxed{\textbf{(B) } \frac{1}{4}}$.

Video Solution by OmegaLearn

https://youtu.be/rLAcJe3o-uA?t=1086

~ pi_is_3.14

Video Solution

https://youtu.be/XT440PjAFmQ

See Also

2019 AMC 10B (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 10 Problems and Solutions
2019 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 18 		Followed by
Problem 20
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=2019_AMC_10B_Problems/Problem_22&oldid=222595"