CLR cover
Previous problem

Problem 76: Overlap-Free Game

Next problem
\( \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.