The Monkeys Are At It Again

Consider an alphabet of $\alpha$ letters and a string of length $n$ . We call a string valid if it does not have three or more of the same letter in a row. Let $X_n$ be the number of valid strings of length $n$ .

Obviously, all strings of lengths less than 3 are valid: $X_1 = \alpha;\ X_2 = \alpha^2$ ; each valid string of length $n \geq 3$ is generated by

• either taking a valid string of length $n-1$ and adding a letter unequal to the last letter, e.g. $\mathtt{OLD} \mapsto \mathtt{OLDN}$ ; there are $\alpha-1$ ways to choose the new letter.

• or taking a valid string of length $n-2$ and adding twice a letter unequal to the last letter, e.g. $\mathtt{OL} \mapsto \mathtt{OLNN}$ ; there are $\alpha-1$ ways to choose the new letter.

Thus $X_n = (\alpha-1)X_{n-1} + (\alpha-1)X_{n-2}$ and To solve this recurrence relation, try a function of the form $X_n = p^n$ . Then $p^2 = (\alpha-1)p + (\alpha-1);$ $p_{\pm} = \tfrac12(\alpha-1) \pm \tfrac12\sqrt{(\alpha+1)^2 - 4}.$ The general solution of the recurrence relation is any linear combination of these solutions, i.e. $X_n = A_{+}p_{+}^n + A_{-}p_{-}^n.$

From $X_1 = \alpha$ and $X_2 = \alpha^2$ we find that $A_\pm = \frac{\alpha}{2(\alpha-1)} \pm \frac{\alpha}{2\sqrt{(\alpha+1)^2 - 4}}.$

However, it can be shown that the second term is always less than one half: $|A_{-}p_{-}^n| < \tfrac12$ . Thus, we may simply round to an integer: $\boxed{X_n = [A_{+}p_{+}^n] = \left[\left(\dfrac{\alpha}{2(\alpha-1)} + \dfrac{\alpha}{2\sqrt{(\alpha+1)^2 - 4}}\right) \left(\tfrac12(\alpha-1) + \tfrac12\sqrt{(\alpha+1)^2 - 4}\right)^n\right]}.$

---

Now we must calculate for which value $N$ , $X_N \approx f\alpha^N$ . The equation takes the form $A_{+}p_{+}^N \approx f\alpha^N;$ The solution is $N \approx \frac{\log f - \log A_{+}}{\log p_{+} - \log \alpha}.$ Substituting $\alpha = 26$ , $f = 0.5$ , we find $N \approx \frac{\log 0.5 - \log 1.0028078}{\log 25.962912 - \log 26} = 487.54;$ the monkeys type strings of 487 or 488 letters. (The fraction of valid strings will be 50.04% and 49.97%, respectively.) The answer to the problem is thus $\lfloor N/10 \rfloor = \boxed{48}$ .