#
Problem 76: Overlap-Free Game

\(
\def\sa#1{\tt{#1}}
\def\dd{\dot{}\dot{}}
\)

The game relies on the notion of overlaps occurring in words.
A word contains an overlap (factor of exponent larger than $2$)
if one of its factors is of
the form $avava$ for a letter $a$ and a word $v$.

The overlap-free game of length $n$ is played between two players, Ann and
Ben, on the alphabet $A=\{\sa{0},\sa{1},\sa{2},\sa{3}\}$.
Players extend an initially empty word by alternately appending a letter
to the word.
The game ends when the length of the emerging word is $n$.

We assume that Ben makes the first move and that $n$ is even.
Ann wins if there is no overlap in the final word.
Otherwise, Ben is the winner.

### Ann's winning strategy

Let $d\in A$ be the letter Ann adds during the $k$th move.
If Ben just added the letter $c$, $d$ is defined by
$$d = c \oplus {\mathbf f}[k],$$
where $x\oplus y = (x+y)\bmod 4$ and ${\mathbf f}=f^\infty(\sa{1})$ is the
infinite square-free word obtained by iterating the morphism $f$ defined on
$\{\sa{1},\sa{2},\sa{3}\}^*$ by $f(\sa{1})=\sa{123}$, $f(\sa{2})=\sa{13}$ and
$f(\sa{3})=\sa{2}$ (see Problem 79).
Word ${\mathbf f}$ and a series of moves look like

$\begin{array}{@{}rccccccccccccccccccccccccccccccccccccc}
{\mathbf f}& &\sa{1}& &\sa{2}& &\sa{3}& &\sa{1}& &\sa{3}& &\sa{2}& &\sa{1}& &\sa{2}&\dots\\
\mbox{moves} &\sa{0}&\sa{1}&\sa{2}&\sa{0}&\sa{0}&\sa{3}&\sa{2}&\sa{3}&\sa{3}&\sa{2}
&\sa{3}&\sa{1}&\sa{1}&\sa{2}&\sa{1}&\sa{3}&\dots
\end{array}$

Show that Ann always wins against Ben in the overlap-free game of any even
length $n$ when using Ann's strategy.

The sum of letters of any odd-length factor of ${\mathbf f}$ is not divisible by 4.

## References

J. Grytczuk, K. Kosinski, and M. Zmarz. How to play Thue games.
*Theor. Comput. Sci.*, **582**:83-88, 2015.