, 2020

Solution:

Let $n_{a}$, $n_{b}$, and $n_{c}$ be the number of $a$'s, $b$'s, and $c$'s on the board, respectively. The key observation is that each move always changes the parity of all three of $n_{a}$, $n_{b}$, and $n_{c}$. Since the final configuration must have $n_{a}$, $n_{b}$, and $n_{c}$ equal to $1,0,0$ in some order, Alice cannot leave one letter on the board if $n_{a}$, $n_{b}$, and $n_{c}$ start with the same parity (because then they will always have the same parity). Alice also cannot leave one letter on the board if all the letters are initially the same (because she will have no moves to make).

We claim that in all other cases, Alice can make a sequence of moves leaving one letter on the board. The proof is inductive: the base cases $n_{a}+n_{b}+n_{c} \leq 2$ are easy to verify, as the possible tuples are $(1,0,0)$, $(1,1,0)$, and permutations. If $n_{a}+n_{b}+n_{c} \geq 3$, assume without loss of generality that $n_{a} \geq n_{b} \geq n_{c}$. Then $n_{b} \geq 1$ (because otherwise all the letters are $a$) and $n_{a} \geq 2$ (because otherwise $(n_{a}, n_{b}, n_{c}) = (1,1,1)$, which all have the same parity). Then Alice will replace $a$ and $b$ by $c$, reducing to a smaller case.

We begin by computing the probability that $n_{a}$, $n_{b}$, and $n_{c}$ start with the same parity. Suppose $m$ letters are chosen at random in the same way (so that we are in the case $m=1001$). Let $x_{m}$ be the probability that $n_{a}$, $n_{b}$, and $n_{c}$ all have the same parity. We have the recurrence $x_{m+1} = \frac{1}{3}(1 - x_{m})$ because when choosing the $(m+1)$th letter, the $n_{i}$ can only attain the same parity if they did not before, and the appropriate letter is drawn. Clearly $x_{0} = 1$, which enables us to compute $x_{m} = \frac{1}{4}(1 + 3 \cdot (-3)^{-m})$. Then $x_{1001}$ is the probability that $n_{a}$, $n_{b}$, and $n_{c}$ have the same parity.

The probability that all the letters are initially the same is $3^{-1000}$, as this occurs exactly when all the subsequent letters match the first. Thus our final answer is

$$1 - 3^{-1000} - \frac{1}{4}(1 + 3 \cdot (-3)^{-1001}) = \frac{3}{4} - \frac{1}{4 \cdot 3^{999}}$$