, 2018

Solution:

Answer: 341
Let $a_{n}$ denote the number of adjacent pairs of letters that are the same after $n$ minutes, and $b_{n}$ the number of adjacent pairs that are different.

Lemma 1. $a_{n}=b_{n-1}$ for all $n \geq 0$.

Proof. Any adjacent pair of identical letters $X X$ at stage $n$ either came from the same letter of stage $n-1$ ($W \rightarrow X X$), or two adjacent letters of stage $n-1$ ($V W \rightarrow M X X N$). Because $A \rightarrow A B$ and $B \rightarrow B A$, they cannot have come from the same letter.

If they came from a pair of adjacent letters, then observing what each adjacent pair of letters results in in the next minute,
$$\begin{aligned} & A A \rightarrow A B A B \\ & A B \rightarrow A B B A \\ & B A \rightarrow B A A B \\ & B B \rightarrow B A B A \end{aligned}$$
we see that our adjacent pair $V W$ must have been $A B$ or $B A$. The number of such pairs is precisely $b_{n-1}$.

From the relation $a_{n}+b_{n}=2^{n}-1$ for all $n \geq 0$, we obtain the recurrence relation
$$a_{n}=2^{n-1}-1-a_{n-1}$$
from which we obtain values $a_{0}=0, a_{1}=0, a_{2}=1, a_{3}=2, a_{4}=5, a_{5}=10, a_{6}=21, a_{7}=42$, $a_{8}=85, a_{9}=170$, and $a_{10}=341$.