Usually the game tic-tac-toe is played on an infinite board (i.e. 30 times 40 or something). The two players draw X:s and 0:s to the squares of a notepad paper. Player 1 (beginner) is the X-drawer and the Player 2 is the 0-drawer. The first player who manages to draw five of his symbols in a row, column or a diagonal wins (and no two symbols can be drawn in the same square). There are plenty variations and the most simple of them is played on a 3×3 grid and the player who gets 3 in a row/column/diagonal wins. According to these rules Player 1 won the game in the above cartoon. A combinatorial line however is a sequence of n-tuples (elements of A^n for a finite A={0,…,k-1}) which do not have both: increasing and decreasing co-ordinates. For instance ((1,0),(1,1),(1,2)) is a combinatorial line, but ((0,2),(1,1),(2,0)) is not. When mathematicians turned their attention to tic-tac-toe they noticed that it is more convenient to work with combinatorial lines rather than the traditional, discrete lines.
Let us return to the ordinary tic-tac-toe on the 3×3-board. There is a simple no-losing strategy for both players. More on this in Wikipedia. However if one extends the board to three dimensional [tex]3\times 3 \times 3[/tex] or four dimensional [tex]3\times 3 \times 3\times 3[/tex], or n-dimensional [tex]3^n[/tex], the X-player has a winning strategy. These games can be in fact played on a paper. For [tex]3\times 3 \times 3[/tex] one draws 3 grids of size 3×3 and imagines that they correspond to the first, second and the third layers in the [tex]3\times 3 \times 3[/tex] cube. For [tex]3\times 3 \times 3\times 3[/tex] draw a grid like in sudoku. More generally we call [tex]k^n[/tex]-tic-tac-toe the game played on an n-dimensional board with sides of length k. In this case a line of length k must be produced. What is a winning line, a discrete line, is formally defined below.
The [tex]3^3[/tex]-tic-tac-toe can be actually played in Finland in Heureka. There is an apparatus with a physical grid of [tex]27=3\times 3 \times 3[/tex] lamps hanging on the roof and people can switch them on and off in two different colours using special joysticks. There is a link to an advertisement of it from here. I found also another version of the game: the player who by the end of the game has more lines of his or her symbols than the opponent, wins.
Let us see how mathematics can be applied to learn more about these games.
Let us consider the [tex]3\times 3 \times 3[/tex] board. The game is played on the set
[tex]A^3=A\times A\times A[/tex], where [tex]A=\{0,1,2\}[/tex].
On the first move Player 1 picks one of the triples in [tex]A^3[/tex] and gives it the colour X (we prefer to talk about colouring the board, but still use X and 0 to denote the colours). Then Player 2 picks another triple and gives it the colour 0. They continue in this manner and the first player who obtains a discrete line (see below) coloured all in his colour (a monochromatic line), wins. If there is no monochromatic discrete line even after all the elements of [tex]A^3[/tex] are coloured, then the game is a draw. The definitions are the same for [tex]A=\{0,\dots,k-1\}[/tex] and the n-dimensional board [tex]A^n[/tex]: players colour elements from the set [tex]A^n[/tex] of sequences of length n and the colour of the first monochromatic discrete line defines the winner.
Let us now define a discrete line or a d-line we referred to above. Suppose [tex]A=\{0,\dots,k-1\}[/tex]. Elements of [tex]A^n[/tex] are sequences of length n. A typical element of [tex]A^4[/tex] for k=3 is (1,1,2,0). A sequence with variables is a sequence in which some elements are replaced by one of the two variables x and y: for example (x,2,x,0) or (y,y,x,0) are sequences with variables. Formally a sequence with variables [tex]s(x,y)[/tex] is an element of the set [tex](A\cup\{x,y\})^n[/tex]. For any sequence with variables [tex]s(x,y)[/tex], let us denote by [tex]s(v,u)[/tex] this sequence but with x replaced by v and y replaced by u everywhere. Now given a sequence with variables [tex]s(x,y)[/tex] the corresponding d-line will be the set
[tex]\{s(u,k-1-u)\mid u\in A\}=\{s(0,k-1),s(1,k-2),\dots,s(k-1,0)\}[/tex].
Examples of d-lines in [tex]A^4[/tex] for k=3 are thus
[tex]\{(0,2,1,2),(1,2,1,2),(2,2,1,2)\}, s(x,y)=(x,2,1,2)[/tex]
[tex]\{(2,0,0,0),(2,1,1,1),(2,2,2,2)\}, s(x,y)=(2,x,x,x)[/tex] and
[tex]\{(2,1,0,0),(1,1,1,0),(0,1,2,0)\}, s(x,y)=(y,1,x,0)[/tex] etc..
So there are increasing, decreasing and constant co-ordinates corresponding respectively to x, y and constants. Now, combinatorial lines are those discrete line which arise from sequences with variables not containing both x and y. Thus the first and the second of above examples are combinatorial but the last is not.
I will now give a proof that Player 1 can always win in the [tex]3^3[/tex]-tic-tac-toe and then I will give a sufficient condition for a winning strategy in [tex]k^n[/tex]-tic-tac-toe.
Theorem 1 There is a winning strategy for Player 1 in the [tex]3^3=3\times 3\times 3[/tex]-tic-tac-toe.
Proof. So now [tex]A=\{0,1,2\}[/tex] and the game board is [tex]A^3[/tex]. On the first move Player 1 picks the element in the middle (the element [tex](1,1,1)[/tex]). Suppose the opponent answers by an element [tex](0,v,u)[/tex]. After that Player 1 just picks a line from the opposite [tex]3\times 3[/tex]-subgrid, [tex]\{(2,x,y)\mid x,y\in A\}[/tex]. This is possible because the opponent has to prevent the formation of a line of the form [tex]\{(2,x,y),(1,1,1),(0,x’,y’)\}[/tex] and has to play only on the subgrid [tex]\{(0,x,y)\mid x,y\in A\}.\,\,\,\,\,\, \square[/tex]
The standard [tex]3^2[/tex]-tic-tac-toe can end in a draw: all squares of the board are filled but there is no monochromatic discrete line. This situation is impossible in the [tex]3^3[/tex]-case. After colouring all elements of the [tex]3^3[/tex]-cube, there will be a monochromatic line (but not necessarily a combinatorial line!). This fact gives another proof of Theorem 1 which follows from the more general Theorem 2:
Theorem 2 Suppose k and n are numbers with the property that whenever the cube [tex]A^n=\{0,\dots,k-1\}^n[/tex] is coloured with two colours, there exists a monochromatic d-line. Then Player 1 has a winning strategy in the [tex]k^n[/tex]-tic-tac-toe.
Proof. The idea is that one of the players must have a winning strategy and if it is Player 2, then Player 1 could use that strategy against her.
So suppose Player 1 does not have a winning strategy. Then independently of what is his first move, it is not a winning move, so Player 2 can reply by a move after which player 1 is still not in a winning position and so forth. This cannot lead to a win by Player 1 and since one of the players wins (by the assumption there cannot be a draw), this is a winning strategy for Player 2. Let us show that this is a contradiction.
If there is a winning strategy for Player 2, then Player 1 can use it! He just ignores his own first move and after the first move by Player 2 he imagines that they switched roles. It has to be checked now that the first extra move doesn’t bother Player 1, but it is an element of his colour, so it certainly cannot help player 2 to win. If he has to play later on the same place as the first extra move occurred, he just picks some random element, since the needed move is already made. [tex]\,\,\,\,\,\,\square[/tex]
Note that there is a huge difference between the proofs of Theorems 1 and 2. The proof of Theorem 1 is constructive: it provides a strategy. So once it has been understood, one can easily win the [tex]3^3[/tex]-tic-tac-toe being in the position of Player 1. But the proof of Theorem 2 is not constructive. Hence, even if you know that your playing board satisfies the conditions of Theorem 2 (i.e. there’s never a draw) and you fully understand the proof, there is still no hint of how actually to play in order to win (being Player 1).
But how do we know whether two given numbers k and n satisfy the premise of Theorem 2? It is certainly a hard question, but at least it is known that for each k there exists an n such that the pair k, n meets the requirements. Since a combinatorial line is a special case of a d-line the following result of Ramsey theory applies as well to our case:
Theorem 3 (Hales-Jewett). Let k be a positive integer and [tex]A=\{0,\dots,k-1\}[/tex]. Then there exists a natural number [tex]n[/tex] such that whenever the elements of the cube [tex]A^n[/tex] are coloured with two colours, there is a monochromatic combinatorial line, i.e. a combinatorial line with all elements being the same colour. [tex]\,\,\,\,\,\,\square.[/tex]
The least such number is denoted by [tex]HJ(k)[/tex]. The general proof of this theorem gives [tex]HJ(3)\leqslant 8[/tex]. Hindman and Tressler proved that [tex]HJ(3)=4[/tex]. Their proof is quite detailed though.
But since we are interested in d-lines, not only combinatorial lines, let us define the function [tex]HJ^*[/tex] such that [tex]n=HJ^*(k)[/tex] is the least natural number such that any two-colouring of [tex]\{0,\dots,k-1\}^n[/tex] contains at least one monochromatic d-line. Equivalently [tex]HJ^*(k)[/tex] is the least dimension in which [tex]k^n[/tex]-tic-tac-toe cannot be a draw. Clearly [tex]HJ^*(k)\leqslant HJ(k)[/tex]. I found that [tex]HJ^*(3)=3[/tex]. But it is a bit easier to show that [tex]HJ^*(3)\leqslant 4[/tex]. The following elegant proof is due to Kerkko Luosto. Using the lemma below, the dedicated reader may verify that [tex]HJ^*(3)=3[/tex].
Theorem 4 [tex] HJ^*(3)\leqslant 4.[/tex]
We will talk in terms of draw positions. The claim is that there is no draw position in [tex]3\times 3 \times 3\times 3[/tex]. The key idea is that if there were a draw position in [tex]3\times 3 \times 3\times 3[/tex], then whenever we took a 3-dimensional subcube, the induced colouring would be a draw position on this subcube.
Lemma. Consider a draw position on the [tex]3^3[/tex]-cube. Then the points [tex](1,1,0)[/tex] and [tex](1,1,2)[/tex] cannot have the same colour.
Proof. So here [tex]A=\{0,1,2\}[/tex].
One easily verifies that up to rotation and mirror symmetries and switching colours the following picture
gives the unique draw position in a [tex]3\times 3[/tex]-grid assuming that two horizontally opposite squares in the middle row have the same colour. So assuming that our [tex]3\times 3\times 3[/tex]-grid has [tex](1,1,0)[/tex] and [tex](1,1,2)[/tex] of the same colour, it implies that the middle subsquare [tex]\{(1,x,y)\mid x,y\in A\}[/tex] is coloured as in the picture above. This implies the same for the subsquares [tex]\{(x,0,y)\mid x,y\in A\}, \{(x,1,y)\mid x,y\in A\}[/tex] and [tex]\{(x,2,y)\mid x,y\in A\}[/tex]. There is only one way (up to symmetry) to do this without introducing monochromatic colours on the subsquares [tex]\{(0,x,y)\mid x,y\in A\}[/tex] and [tex]\{(2,x,y)\mid x,y\in A\}[/tex]. But now there is a monochromatic diagonal ((0,0,0),(1,1,1),(2,2,2)). See the picture below. [tex]\,\,\,\,\,\,\square[/tex]
Suppose now that there is a draw position on 3x3x3x3. By the previous lemma it means that no matter what 3-dimensional subcube we take, it cannot have the same colour at opposite points. Consider the following three subcubes of 3x3x3x3:
[tex]\{(x,y,z,z)\mid x,y,z\in A\}[/tex]
[tex]\{(x,y,z,2)\mid x,y,z\in A\}[/tex]
[tex]\{(x,y,0,z)\mid x,y,z\in A\}[/tex]
Suppose the colour of the point (1,1,0,0) is X. Then using the first subcube we have that (1,1,2,2) must be 0. Using the second subcube this implies that (1,1,0,2) must be X and now using the third subcube this implies that (1,1,0,0) must be 0. A contradiction! [tex]\,\,\,\,\,\,\square[/tex]
