HMMT-Feb 2021 comb, Problem 5

Teresa the bunny has a fair 8 -sided die. Seven of its sides have fixed labels $1,2, \ldots, 7$, and the label on the eighth side can be changed and begins as 1 . She rolls it several times, until each of $1,2, \ldots, 7$ appears at least once. After each roll, if $k$ is the smallest positive integer that she has not rolled so far, she relabels the eighth side with $k$. The probability that 7 is the last number she rolls is $\frac{a}{b}$, where $a$ and $b$ are relatively prime positive integers. Compute $100 a+b$.

Solution: Solution 1: Let $n=7$ and $p=\frac{1}{4}$. Let $q_{k}$ be the probability that $n$ is the last number rolled, if $k$ numbers less than $n$ have already been rolled. We want $q_{0}$ and we know $q_{n-1}=1$. We have the relation \[ q_{k}=(1-p) \frac{k}{n-1} q_{k}+\left[1-(1-p) \frac{k+1}{n-1}\right] q_{k+1} \] This rearranges to \[ \left[1-(1-p) \frac{k}{n-1}\right] q_{k}=\left[1-(1-p) \frac{k+1}{n-1}\right] q_{k+1} \] This means that the expression on the LHS does not depend on $k$, so \[ [1-0] \cdot q_{0}=[1-(1-p)] \cdot q_{n-1}=p \] Solution 2: For a given sequence of Teresa's rolls, let $x_{i}$ be the $i$ th distinct number rolled. We want to compute the probability that $x_{7}=7$. For a given index $i$, we say that $x_{i}$ is correct if $x_{i}$ is the least positive integer not in $\left\{x_{1}, \ldots, x_{i-1}\right\}$. Note that the probability of a given sequence $x_{1}, \ldots, x_{7}$ depends only on the number of correct $x_{i}$, since the probability of rolling the correct number on a given roll is higher by a factor of 2 . Now, suppose $x_{7}=7$. Consider $x_{i}^{\prime}=x_{i-1}+1$ for $1<i \leq 7$, and $x_{1}^{\prime}=1$. Note that this operation on sequences $x_{1}, \ldots, x_{7}$ pairs sequences ending in 7 with sequences starting with 1 . Additionally, we have that $x_{7}$ and $x_{1}^{\prime}$ are both correct, and that $x_{i}^{\prime}$ is correct if and only if $x_{i-1}$ is correct. Thus $x_{1}, \ldots, x_{7}$ and $x_{1}^{\prime}, \ldots, x_{7}^{\prime}$ have the same probability. So, we conclude that the probability of $x_{7}=7$ is the same as the probability of $x_{1}=1$. But this is just $\frac{1}{4}$. $\fbox{104}$.

Answer: 104