Play the square-free ternary sequence game!

Choose a letter:
a b c
you will lose by the 16th move


Consider the game where players take turns selecting symbols to form an infinite sequence. Player 1 (you in this case) is trying to avoid the production of any squares (consecutive identical subsequences) while Player 2 is trying to force their appearance. Of course, Player 2 can always force the repetition of single symbols just by imitating Player 1's moves. Player 1 only loses if there is a square whose constituent subsequences each have length at least 2.

In [1], we use a generalization of the Local Lemma to show the existance of a winning strategy for Player 1 in this game, so long as there are at least 37 symbols. The proof is probabilistic and totally nonconstructive.

Of course, a natural question is how many symbols are actually necessary. It is simple to check that two symbols is not enough. (Even if Player 2 always chooses the same symbol, Player 1 will loose by the 8th move; in fact Player 2 can win in six moves.) This page is the product of a computer search showing that 3 symbols is not enough either. The website knows the entire "backwards labeled" game tree, allowing it to play optimally (as Player 2) and keep track of how far away it is from victory. It will always defeat you by the 16th move of the game (and often earlier if you don't play well!). Player 2's strategy actually has a very simple description and proof of correctness, which we give below.

Together with the proof in [1], this implies that the minimum number of symbols required for Player 1 to have a winning strategy is between 4 and 37. A computer search seems to be impractical to rule out 4 symbols: the backwards labeling takes an hour just to search up to move 40. To search up to move 42 takes a day (and at up until this point at least Player 2 still cannot win). Indeed, Player 1 may be able to win on 4 symbols (i.e., survive forever), in which case the computer search can tell us nothing!

We mentioned above that the computer's strategy has a simple description, and it here it is: the computer always simply selects the symbol which follows the symbol Player 1 has just chosen in the cyclic order (a,b,c). Observe a few things: Player 1 can never make the same choice of symbol on two consecutive turns, otherwise he loses (e.g., abab). Thus, on each turn Player 1 only really has 2 choices: whether to choose the symbol which comes after the symbol of his previous move in the cyclic order (a,b,c), or the one which comes before his previous move. Thus we can represent the play of a game as a sequence of +'s and -'s for each of Player 1's moves. For example, the game abcaabbcabbc corresponds to the sequence -++-+ of choices by Player 1 (without loss of generality, we can assume the first symbol chosen was a). It is easy to check now that Player 1 loses (there is a square) if the two -'s occur consecutively (e.g., abcabc). There will also always be a square if the sequence of choices +-+ occurs. Together, these two facts imply that if +- ever occurs, Player 1 will lose on the next turn. Now we are basically done: if a - occurs anywhere after the beginning, Player 1 loses on the next turn. Therefore, the sequence choices must be all +'s, except possibly for the first and last choices. But +++++ produces a square (e.g., abbccaabbccaa), and the proof is done. Note that, while we have been able to apply rather sophisticated techniques in [1] to establish the upper bound of 37 for the number of symbols required for Player 1 to win (in particular, implying that there is such a finite number), we know of nothing better than simple case studies as described here to establish lower bounds.

[1] W. P., Highly nonrepetitive sequences: winning strategies from the Local Lemma. Preprint available here.