Problem 1044

Solution:

Let $E_{0}$ be the expected number of flips needed. Let $E_{1}$ be the expected number more of flips needed if the first flip landed on H. Let $E_{2}$ be the expected number more if the first two landed on HM. In general, let $E_{k}$ be the expected number more of flips needed if the first $k$ flips landed on the first $k$ values of the sequence HMMTHMMT...HMMT.

We have
$$E_{i} = \left\{ \begin{array}{lll} 1 + \frac{1}{3} E_{i+1} + \frac{1}{3} E_{1} + \frac{1}{3} E_{0} & i \not\equiv 0 & (\bmod 4) \\ 1 + \frac{1}{3} E_{i+1} + \frac{2}{3} E_{0} & i \equiv 0 & (\bmod 4) \end{array} \right.$$

Using this relation for $i=0$ gives us $E_{1} = E_{0} - 3$. Let $F_{i} = \frac{1}{3^{i}} E_{i}$. By simple algebraic manipulations we have
$$F_{i+1} - F_{i} = \left\{ \begin{array}{lll} -\frac{2}{3^{i+1}} \cdot E_{0} & i \not\equiv 0 & (\bmod 4) \\ -\frac{1}{3^{i}} - \frac{2}{3^{i+1}} \cdot E_{0} & i \equiv 0 & (\bmod 4) \end{array} \right.$$

We clearly have $F_{2016 \cdot 4} = 0$ and $F_{0} = E_{0}$. So adding up the above relations for $i=0$ to $i=2016 \cdot 4 - 1$ gives
$$\begin{aligned} -E_{0} & = -2 E_{0} \sum_{i=1}^{2016 \cdot 4} \frac{1}{3^{i}} - \sum_{k=0}^{2015} \frac{1}{3^{4k}} \\ & = E_{0}\left(\frac{1}{3^{2016 \cdot 4}} - 1\right) - \frac{1 - \frac{1}{3^{2016 \cdot 4}}}{\frac{80}{81}} \end{aligned}$$
so $E_{0} = \frac{3^{8068} - 81}{80}$.