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 "2018 AIME II Problems/Problem 13"

(→‎Solution 3 (Simple))
(→‎Solution 3 (Simple))
Line 38: Line 38:
 
<math>P_3</math>, the probability of getting rolls of 1-2-3 in exactly 3 rolls, is obviously <math>\frac{1}{216}</math>.
 
<math>P_3</math>, the probability of getting rolls of 1-2-3 in exactly 3 rolls, is obviously <math>\frac{1}{216}</math>.
  
−
Setting this probability aside, the ratio of <math>P_4+P_6+P_8+...</math> to <math>P_5+P_7+P_9+...</math> should be equal to the ratio of <math>\frac{P_{odd}}{P_{even}}</math>, because in this case the 1st roll no longer matters, so we can disregard it. Thus, 4 rolls, 6 rolls, 8 rolls... would become an odd number of rolls (while 5 rolls, 7 rolls, 9 rolls... would become even number of rolls).
+
We set this probability of <math>P_3</math> aside, meaning we totally remove the chance of getting 1-2-3 in 3 rolls. Now the ratio of <math>P_4+P_6+P_8+...</math> to <math>P_5+P_7+P_9+...</math> should be equal to the ratio of <math>\frac{P_{odd}}{P_{even}}</math>, because in this case the 1st roll no longer matters, so we can disregard the very existence of it in counting how many times of rolls, and thus, 4 rolls, 6 rolls, 8 rolls... would become an odd number of rolls (while 5 rolls, 7 rolls, 9 rolls... would become even number of rolls).
 +
 
 +
Notice <math>P_4+P_6+P_8+...=P_{even}</math>, and also <math>P_5+P_7+P_9+...=P_{odd}-P_3=P_{odd}-\frac{1}{216}</math>
  
 
So we have <math>\frac{P_{even}}{P_{odd}-\frac{1}{216}}=\frac{P_{odd}}{P_{even}}</math>.
 
So we have <math>\frac{P_{even}}{P_{odd}-\frac{1}{216}}=\frac{P_{odd}}{P_{even}}</math>.

Revision as of 16:43, 28 March 2018

Problem

Misha rolls a standard, fair six-sided die until she rolls 1-2-3 in that order on three consecutive rolls. The probability that she will roll the die an odd number of times is $\dfrac{m}{n}$ where $m$ and $n$ are relatively prime positive integers. Find $m+n$.

Solution 1

Call the probability you win on a certain toss $f_n$, where $n$ is the toss number. Obviously, since the sequence has length 3, $f_1=0$ and $f_2=0$. Additionally, $f_3=\left(\frac{1}{6}\right)^3$. We can call this value $x$, to keep our further equations looking clean. We can now write our general form for $f$ as $f_n=x(1-\sum_{i=1}^{n-3}f_i)$. This factors the probability of the last 3 rolls being 1-2-3, and the important probability that the sequence has not been rolled in the past (because then the game would already be over). Note that $\sum_{i=1}^{\infty}f_i=1$ since you'll win at some point. An intermediate step here is figuring out $f_n-f_{n+1}$. This is equal to $x(1-\sum_{i=1}^{n-3}f_i)-x(1-\sum_{i=1}^{n-2}f_i)=x(\sum_{i=1}^{n-2}f_i-\sum_{i=1}^{n-3}f_i)=xf_{n-2}$. Adding up all the differences, i.e. $\sum_{i=2}^{\infty}(f_{2n-1}-f_{2n})$ will give us the amount by which the odds probability exceeds the even probability. Since they sum to 1, that means the odds probability will be half of the difference above one-half. Subbing in our earlier result from the intermediate step, the odd probability is equal to $\frac{1}{2}+\frac{1}{2}x\sum_{i=2}^{\infty}f_{2n-3}$. Another way to find the odd probability is simply summing it up, which turns out to be $\sum_{i=1}^{\infty}f_{2n-1}$. Note the infinite sums in both expressions are equal; let's call it $P$. Equating them gives $\frac{1}{2}+\frac{1}{2}xP=P$, or $P=\frac{1}{2-x}$. Finally, substituting $x=\frac{1}{216}$, we find that $P=\frac{216}{431}$, giving us a final answer of $216 + 431 = \boxed{647}$. --DanDan0101

Solution 2 (Recursion)

Let $S(n)$ be the number of strings of length $n$ containing the digits $1$ through $6$ that do not contain the string $123$. Then we have $S(n) = 6 \cdot S(n-1) - S(n-3)$ because we can add any digit to end of a string with length $n-1$ but we have to subtract all the strings that end in $123$. We rewrite this as \begin{align*} S(n) &= 6 \cdot S(n-1) - S(n-3) \\ &= 6 \cdot (6 \cdot S(n-2) - S(n-4)) - (6 \cdot (S(n-4) - S(n-6)) \\ &= 36 \cdot S(n-2) - 12 \cdot S(n-4) + S(n-6) \end{align*} We wish to compute $P=\sum_{n=0}^\infty \frac{S(2n)}{6^{2n+3}}$ since the last three rolls are $123$ for the game to end. Summing over the recursion, we obtain \[\sum_{n=0}^\infty \frac{S(2n)}{6^{2n+3}} =36 \cdot \sum_{n=0}^\infty \frac{S(2n-2)}{6^{2n+3}} - 12 \cdot \sum_{n=0}^\infty \frac{S(2n-4)}{6^{2n+3}}+ \sum_{n=0}^\infty \frac{S(2n-6)}{6^{2n+3}}\]Now shift the indices so that the inside term is the same: \begin{align*} \sum_{n=3}^\infty \frac{S(2n)}{6^{2n+3}} &= \frac{36}{6^2} \cdot \sum_{n=2}^\infty \frac{S(2n)}{6^{2n+3}} - \frac{12}{6^4} \cdot \sum_{n=1}^\infty \frac{S(2n)}{6^{2n+3}} + \frac{1}{6^6} \cdot \sum_{n=0}^\infty \frac{S(2n)}{6^{2n+3}} \\ \left(P - \frac{S(0)}{6^3} - \frac{S(2)}{6^5} -\frac{S(4)}{6^7} \right) &= \frac{36}{6^2} \cdot \left( P - \frac{S(0)}{6^3} - \frac{S(2)}{6^5}\right) - \frac{12}{6^4} \cdot \left( P - \frac{S(0)}{6^3} \right) + \frac{1}{6^6} \cdot P \end{align*}Note that $S(0) = 1, S(2) = 26$ and $S(4) = 6^4 - 2 \cdot 6 = 1284$. Therefore, \begin{align*} \left(P - \frac{1}{6^3} - \frac{36}{6^5} -\frac{1284}{6^7} \right) = \frac{36}{6^2} \cdot \left( P - \frac{1}{6^3} - \frac{36}{6^5}\right) - \frac{12}{6^4} \cdot \left( P - \frac{1}{6^3} \right) + \frac{1}{6^6} \cdot P \end{align*}Solving for $P$, we obtain $P = \frac{216}{431} \implies m+n = \boxed{647}$. -Vfire

Solution 3 (Simple)

Let $P_{odd}=\frac{m}{n}$, with the subscript indicating an odd number of rolls. Then $P_{even}=1-\frac{m}{n}$.

The ratio of $\frac{P_{odd}}{P_{even}}$ is just $\frac{P_{odd}}{1-P_{odd}}$.

We see that $P_{odd}$ is the sum of $P_3$,$P_5$,$P_7$,... , while $P_{even}$ is the sum of $P_4$, $P_6$, $P_8$,... .

$P_3$, the probability of getting rolls of 1-2-3 in exactly 3 rolls, is obviously $\frac{1}{216}$.

We set this probability of $P_3$ aside, meaning we totally remove the chance of getting 1-2-3 in 3 rolls. Now the ratio of $P_4+P_6+P_8+...$ to $P_5+P_7+P_9+...$ should be equal to the ratio of $\frac{P_{odd}}{P_{even}}$, because in this case the 1st roll no longer matters, so we can disregard the very existence of it in counting how many times of rolls, and thus, 4 rolls, 6 rolls, 8 rolls... would become an odd number of rolls (while 5 rolls, 7 rolls, 9 rolls... would become even number of rolls).

Notice $P_4+P_6+P_8+...=P_{even}$, and also $P_5+P_7+P_9+...=P_{odd}-P_3=P_{odd}-\frac{1}{216}$

So we have $\frac{P_{even}}{P_{odd}-\frac{1}{216}}=\frac{P_{odd}}{P_{even}}$.

Finally, we get $P_{odd}=\frac{m}{n}=\frac{216}{431}$ Therefore, $m+n = \boxed{647}$.


2018 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 12 		Followed by
Problem 14
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME 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=2018_AIME_II_Problems/Problem_13&oldid=93575"