The ordinary game of Noughts and Crosses, also known as Tic-tac-toe, features a board on which two players alternate placing symbols (O for the first player, and X for the second player) in unoccupied squares, attempting to form a line of three collinear squares containing their symbol. It has been known since time immemorial that, assuming perfect play, the game results in a draw. Randall Munroe provided a beautiful illustration of the optimal strategy for each player.
There have been extensions to higher dimensions. For example, a popular variant involves a board, where the first player to obtain four collinear cubes of their symbol wins. Apparently, this one is a victory for the first player (assuming perfect play), although humans play sufficiently suboptimally that this has no impact.
After receiving a particular text message ending with an alternating string of ‘X’s and ‘O’s, I was inspired to go in the opposite direction and consider variants of Noughts and Crosses on a one-dimensional board. One particularly interesting example is a game mentioned on the Advanced Mentoring Scheme:
Two players (Alice and Bob) alternate placing either an ‘X’ or an ‘O’ on an unoccupied square of a board. As soon as three adjacent squares form the string ‘XOX’, the player who has just placed that symbol wins. If the board fills up without this happening, the game is declared a draw.
It’s relatively easy to show that the only losing positions are those where the unoccupied squares form the string ‘X__X’, where placing either of the symbols in one of the empty spaces enables the opponent to secure an immediate win. Since losing positions must have an even number of empty spaces, we can prove that Alice can force at least a draw for odd n, and Bob can force at least a draw for even n.
To force a win, the favoured player must therefore simply attempt to form the string ‘X__X’ and then play naturally, knowing that parity will eventually reward him or her with a victory. If the board is sufficiently large, it is easy to see that a win is guaranteed. The thresholds for forcing a win are n = 7 for Alice and n = 18 for Bob, far below the n = 2010 in the AMS question.
I heard about 1D noughts and crosses where we construct arithmetic progression of given length. No matter how many colors there are or how long progression needs to be, for suffiscently large grids it must be win for either side.
Yes, by van der Waerden’s theorem.
Hales-Jewett is even more relevant, since a corollary is that for fixed n and k, a k-player game on a n*n*…*n board of sufficiently high dimension (where n collinear points results in a victory) cannot result in a draw.
I discussed some of these theorems in my unofficial Ramsey theory talk at the olympiad training camp.