Recursive (Counting) AIME Challenging
2018


Problem - 4128

Misha rolls a standard, fair six-sided die until she rolls $1-2-3$ in that order on three consecutive rolls. Find the probability that she will roll the die an odd number of times.


Answer     647

$\underline{Solution\ 1}$

Let $P(n)$ be the probability that a series rolls of length $n$ ends with $1-2-3$. Clearly, $P(1)=P(2)=0$ and $P(3)=\frac{1}{6^3}=\frac{1}{216}$. We claim that $$\frac{P(3)+P(5)+P(7)+\cdots}{P(4)+P(6)+P(8)+\cdots}=\frac{P(4)+P(6)+P(8)+\cdots}{P(5)+P(7)+\cdots}$$

The left side of this equation is the ratio of the game ends with an odd number rolls vs an even number of rolls. The right side of the equation is the same value but discard the first roll. In this case, the $3^{rd}$ roll because the new $2^{nd}$ roll with no chance to win, and all the following rolls change odd-even parity.

Now let $P=P(3)+P(5)+P(7)+\cdots$ and $1-P=P(4)+P(6)+P(8)+\cdots$. The previous relation becomes $$\frac{P}{1-P}=\frac{1-P}{P-\frac{1}{216}}\implies P=\boxed{\frac{216}{431}}$$

$\underline{Solution\ 2}$

Let $F(n)$ be a series of $n$ rolls without containing $1-2-3$. Then the desired result equals $$P=\sum_{n=1}^{\infty}\frac{F(2n)}{6^{2n+3}}$$

This is because Misha has to roll at least $3$ times (corresponding to $n=1$), but the last three rolls must be $1-2-3$ which means that the number of ways for a $(2n+3)$ roll to end with $1-2-3$ is the same as the number of ways in the first $(2n)$ rolls, i.e. $F(2n)$.

Meanwhile, we have the following recursion because we can have any of the six numbers in the $n^{th}$ roll, but we have to subtract the case when the $n^{th}$ roll makes the series end with $1-2-3$ $$F(n)=6\cdot F(n-1) - F(n-3)$$

This recursion can be expanded to make $F(n)$ depend on $F(n-2)$, $(n-4)$, and $F(n-6)$ so that we can iterate over odd term only. $$\begin{array}{rl} F(n)=& 6\cdot F(n-1) - F(n-3)\\=& 6\cdot(6\cdot F(n-2) - F(n-4)) - (6\cdot F(n-4) - F(n-6))\\=& 36\cdot F(n-2) - 12\cdot F(n-4)-F(n-6) \end{array}$$

Now are have $$P=\sum_{n=0}^{\infty}\frac{F(2n)}{6^{2n+3}} =\frac{F(0)}{6^3} + \frac{F(2)}{6^5} + \frac{F(4)}{6^7} +\sum_{n=3}^{\infty}\frac{F(2n)}{6^{2n+3}}$$

Meanwhile we have $$\begin{array}{rl} \displaystyle\sum_{n=3}^{\infty}\frac{F(2n)}{6^{2n+3}} = &36\cdot\displaystyle\sum_{n=3}^{\infty} \frac{F(2n-2)}{6^{2n+3}} - 12\cdot\displaystyle\sum_{n=3}^{\infty}\frac{ F(2n-4)}{6^{2n+3}}+\displaystyle\sum_{n=3}^{\infty}\frac{F(2n-6)}{6^{2n+3}} \\ = &\frac{36}{6^2}\cdot\displaystyle\sum_{n=2}^{\infty} \frac{F(2n)}{6^{2n+3}} - \frac{12}{6^4}\cdot\displaystyle\sum_{n=1}^{\infty}\frac{ F(2n)}{6^{2n+3}}+\frac{1}{6^6}\cdot\displaystyle\sum_{n=0}^{\infty}\frac{F(2n)}{6^{2n+3}} \\=& \frac{36}{6^2}\cdot\left(P- \displaystyle\sum_{n=0}^{1} \frac{F(2n)}{6^{2n+3}}\right) - \frac{12}{6^4}\cdot\left(P- \displaystyle\sum_{n=0}^{0}\frac{ F(2n)}{6^{2n+3}}\right)+\frac{1}{6^6}\cdot P\end{array}$$

Setting this to the previous relation will yield $$2586\cdot P = 12 + F(4)$$

Clearly, we have $F(1)=6$, $F(2)=6^2=36$, $F(3)=6^3-1=215$, and $F(4)=6\times 215 - 6 =1284$. Setting this into the above relations and solving $P$ give $P=\boxed{\frac{246}{431}}$.

report an error