HMMT-Nov 2018 thm, Problem 8

Crisp All, a basketball player, is dropping dimes and nickels on a number line. Crisp drops a dime on every positive multiple of 10 , and a nickel on every multiple of 5 that is not a multiple of 10 . Crisp then starts at 0 . Every second, he has a $\frac{2}{3}$ chance of jumping from his current location $x$ to $x+3$, and a $\frac{1}{3}$ chance of jumping from his current location $x$ to $x+7$. When Crisp jumps on either a dime or a nickel, he stops jumping. What is the probability that Crisp stops on a dime?

Solution: Let "a 3" mean a move in which Crisp moves from $x$ to $x+3$, and "a 7 " mean a move in which Crisp moves from $x$ to $x+7$. Note that Crisp stops precisely the first time his number of 3 's and number of 7's differs by a multiple of 5 , and that he'll stop on a dime if they differ by 0 , and stop on a nickel if they differ by 5 . This fact will be used without justification. We split into two cases: (a) Crisp begins with a 3. Rather than consider the integer Crisp is on, we'll count the difference, $n$, between his number of 3's and his number of 7's. Each 3 increases $n$ by 1, and each 7 decreases $n$ by 1 . Currently, $n$ is 1 . The probability of stopping on a dime, then, is the probability $n$ reaches 0 before $n$ reaches 5 , where $n$ starts at 1 . Let $a_{i}$ be the probability $n$ reaches 0 first, given a current position of $i$, for $i=1,2,3,4$. We desire $a_{1}$. We have the system of linear equations \[ \begin{aligned} a_{1} & =\frac{2}{3} a_{2}+\frac{1}{3} \cdot 1 \\ a_{2} & =\frac{2}{3} a_{3}+\frac{1}{3} a_{1} \\ a_{3} & =\frac{2}{3} a_{4}+\frac{1}{3} a_{2} \\ a_{4} & =\frac{2}{3} \cdot 0+\frac{1}{3} a_{3} \end{aligned} \] From which we determine that $a_{1}=\frac{15}{31}$.\\ (b) Crisp begins with a 7. Now, let $m$ be the difference between his number of 7's and his number of 3 's. Let $b_{i}$ denote his probability of stopping on a dime, given his current position of $m=i$. We desire $b_{1}$. We have the system of linear equations \[ \begin{aligned} b_{1} & =\frac{1}{3} b_{2}+\frac{2}{3} \cdot 1 \\ b_{2} & =\frac{1}{3} b_{3}+\frac{2}{3} b_{1} \\ b_{3} & =\frac{1}{3} b_{4}+\frac{2}{3} b_{2} \\ b_{4} & =\frac{1}{3} \cdot 0+\frac{2}{3} b_{3} \end{aligned} \] From which we determine that $b_{1}=\frac{30}{31}$. We conclude that the answer is $\frac{2}{3} a_{1}+\frac{1}{3} b_{1}=\frac{2}{3} \cdot \frac{15}{31}+\frac{1}{3} \cdot \frac{30}{31}=\frac{20}{31}$. $\fbox{\frac{20}{31}}$.

Answer: \frac{20}{31}