, 2006

It is easy to handle the cases $n = 3, 5, 6$:

a. $n=3$: $WWW \rightarrow BB$, by removing middle $W$ and reversing the other two;

b. $n=5$: $(WWW)WW \rightarrow (BB)WW = B(BWW) \rightarrow BWB \rightarrow WW$;

c. $n = 6$: $(WWW)WWW \rightarrow BB(WWW) = B(BWW)W \rightarrow B(WB)W = (BWB)W \rightarrow WWW$.

The last reduction shows that for $n > 6$, we can pick any six $W$'s and reduce it three $W$'s there by reducing the case to that of $n - 3$. Since we have ended with 2 markers for $n = 3$ and $5$, it follows by induction that the 'two marker state' is achievable for $n = 3k$ or $3k + 2$.

We have to show that this is not possible for $n = 3k + 1$. Observe that the number of $B$'s is invariant modulo $2$ in each move: $WWW \rightarrow BB$; $WWB \rightarrow BW$; $BWW \rightarrow WB$; $BWB \rightarrow WW$. Since all are $W$ in the beginning, the final two markers must be either $BB$ or $WW$. We assign weights to $W$ and $B$.

Take the group of symmetries of an equilateral triangle with centre at origin and $y$-axis passing through a vertex; let $\phi$ denote rotation by $120^\circ$ about the centre in clock-wise direction; and let $\psi$ denote the reflection in $y$ axis. Then it is easy to see that
$$\phi^3 = \psi^2 = 1, \phi^2\psi = \psi\phi, \psi\phi^2 = \phi\psi, \psi\phi\psi = \phi^2.$$
Thus we may assign $\omega(W) = \phi$, $\omega(B) = \psi$. The properties of $\phi$ and $\psi$ show that they obey the reductions $WWW \rightarrow BB$, $WWB \rightarrow BW$; $BWW \rightarrow WB$; $BWB \rightarrow WW$ and the total weights remain unchanged after each move. Hence if the 'two marker state is achievable, then the end weights must be either $\phi^2$ or $\psi^2$ (corresponding to $WW$ and $BB$ respectively). If $n = 3k + 1$, the total weight at the beginning is $\phi^{(3k+1)} = \phi$. But $\phi \neq \phi^2$ or $\psi^2$ as is evident from the definitions of these functions. Hence 'two marker state' is not achievable for $n = 3k + 1$.