Difference between revisions of "2018 AIME II Problems/Problem 13"
(→Solution 4) |
m (→Solution5 5 quick cheat) |
||
Line 53: | Line 53: | ||
0 & 0 & 0 & 0 \\ | 0 & 0 & 0 & 0 \\ | ||
\end{bmatrix}</math>. <math>A</math> is a transition matrix for the prefix of 1-2-3 matched so far. The state corresponding to a complete match has no outgoing probability mass. The probability that we roll the dice exactly <math>k</math> times is <math>(A^k)_{1,4}</math>. Thus the probability that we roll the dice an odd number of times is <math>1-\left(\sum_{k=0}^\infty A^{2k}\right)_{1,4} = 1-\left((I - A^2)^{-1}\right)_{1,4} = \frac{216}{431}</math>. Thus the answer is <math>216+431=\boxed{647}</math>. | \end{bmatrix}</math>. <math>A</math> is a transition matrix for the prefix of 1-2-3 matched so far. The state corresponding to a complete match has no outgoing probability mass. The probability that we roll the dice exactly <math>k</math> times is <math>(A^k)_{1,4}</math>. Thus the probability that we roll the dice an odd number of times is <math>1-\left(\sum_{k=0}^\infty A^{2k}\right)_{1,4} = 1-\left((I - A^2)^{-1}\right)_{1,4} = \frac{216}{431}</math>. Thus the answer is <math>216+431=\boxed{647}</math>. | ||
− | == | + | ==Solution 5 quick cheat == |
Consider it as a contest of Odd and Even. Let <math>P_o</math> and <math>P_e</math> be probability that Odd and Even wins, respectively. If we consider every 3 rolls as an atomic action, then we can have a simple solution. If the rolls is 1-2-3, Odd wins; otherwise, Odd and Even switch the odds of winning. Therefore, we have | Consider it as a contest of Odd and Even. Let <math>P_o</math> and <math>P_e</math> be probability that Odd and Even wins, respectively. If we consider every 3 rolls as an atomic action, then we can have a simple solution. If the rolls is 1-2-3, Odd wins; otherwise, Odd and Even switch the odds of winning. Therefore, we have | ||
<cmath> P_o = \frac{1}{216} + \frac{215}{216}P_e</cmath> | <cmath> P_o = \frac{1}{216} + \frac{215}{216}P_e</cmath> |
Revision as of 02:22, 26 January 2019
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 where
and
are relatively prime positive integers. Find
.
Solution 1
Let , with the subscript indicating an odd number of rolls. Then
.
The ratio of is just
.
We see that is the sum of
,
,
,... , while
is the sum of
,
,
,... .
, the probability of getting rolls of 1-2-3 in exactly 3 rolls, is obviously
.
We set this probability of aside, meaning we totally remove the chance of getting 1-2-3 in 3 rolls. Now the ratio of
to
should be equal to the ratio of
, 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 , and also
So we have .
Finally, we get .
Therefore,
.
Solution 2
Call the probability you win on a certain toss , where
is the toss number.
Obviously, since the sequence has length 3,
and
.
Additionally,
. We can call this value
, to keep our further equations looking clean.
We can now write our general form for
as
. 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
since you'll win at some point.
An intermediate step here is figuring out
. This is equal to
.
Adding up all the differences, i.e.
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
.
Another way to find the odd probability is simply summing it up, which turns out to be
. Note the infinite sums in both expressions are equal; let's call it
. Equating them gives
, or
.
Finally, substituting
, we find that
, giving us a final answer of
.
--DanDan0101
Solution 3
Let be the number of strings of length
containing the digits
through
that do not contain the string
. Then we have
because we can add any digit to end of a string with length
but we have to subtract all the strings that end in
. We rewrite this as
We wish to compute
since the last three rolls are
for the game to end. Summing over the recursion, we obtain
Now shift the indices so that the inside term is the same:
Note that
and
. Therefore,
Solving for
, we obtain
. -Vfire
Solution 4
Let .
is a transition matrix for the prefix of 1-2-3 matched so far. The state corresponding to a complete match has no outgoing probability mass. The probability that we roll the dice exactly
times is
. Thus the probability that we roll the dice an odd number of times is
. Thus the answer is
.
Solution 5 quick cheat
Consider it as a contest of Odd and Even. Let and
be probability that Odd and Even wins, respectively. If we consider every 3 rolls as an atomic action, then we can have a simple solution. If the rolls is 1-2-3, Odd wins; otherwise, Odd and Even switch the odds of winning. Therefore, we have
Plug in
and we can easily solve for
.
.
Of course this is not a rigorous solution. I think it works because the requirement is a strict sequence of pure random events.
-Mathdummy
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.