CLR cover
Previous problem

Problem 5: Square-Free Game

Next problem
\( \def\sa#1{\tt{#1}} \)

A non-trivial square is a word over an alphabet $A$ of the form $uu$, where $|u|\gt 1$, and it is an odd-square if in addition $|u|$ is an odd number.

The square-free game of length $n$ over $A$ is played between two players, Ann and Ben. The players extend an initially empty word $w$ by alternately appending letters to the word. The game ends when the length of the emerging word is $n$ or a non-trivial square has been created earlier. We assume that Ben makes the first move and that $n$ is even. Ann wins if there are no non-trivial squares in the final word. Otherwise, Ben is the winner.

Odd square-free game. In this limited game Ann wins if no odd-square occurs. On the alphabet $A=\{\sa{0},\sa{1},\sa{2}\}$ we describe Ann's winning strategy as follows. Ann never makes the same move as Ben's last move, and if Ben repeats Ann's last move then she does not repeat his previous move.

To do so, Ann remembers the pair $(b,a)$ where $a$ is the letter appended during her previous move and $b$ is that from Ben's previous move. In other terms, the word $w$ is of even length and after the first move is of the form $w=vba$. Then Ben adds $c$ and Ann responds by adding $d$ to get $w=vbacd$, where $$d\,=\, \cases{ a & if $c\ne a$,\cr 3-b-a& otherwise. }$$ Ann behaves like a finite deterministic automaton whose output has six states. A possible sequence of moves starting with $\sa{1}\,\sa{2}$, potentially winning for Ann, is $$\sa{1}\,\sa{2}\,\sa{1}\,\sa{2}\,\sa{2}\,\sa{0}\,\sa{1}\,\sa{0}\,\sa{0} \,\sa{2}\,\sa{1}\,\sa{2}\,\sa{2}\,\sa{0}.$$

  1. Show that Ann always wins against Ben in the odd square-free game of any even length $n$.
  2. Describe a winning strategy for Ann in the square-free game over an alphabet of size $9$.
To prove (A) show $w$ contains no odd-square. For point (B) mix a simple even-square strategy with the former strategy.

References

  • J. Grytczuk, K. Kosinski, and M. Zmarz. How to play Thue games. Theor. Comput. Sci., 582:83-88, 2015.
  • K. Kosinski, R. Mercas, and D. Nowotka. Corrigendum to "a note on Thue games" [inf. process. lett. 118 (2017) 75-77]. Inf. Process. Lett., 130:63-65, 2018.