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$.
Answer:
104
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 bee 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}$.