Tick Tack Toe #9

Relevant wiki: Tic Tac Toe

Suppose the game could end in a draw. Then each of the boards on each level must end in a draw. There are two non-ordered ways - that is, accounting for symmetries - for a normal $3 \times 3$ game of tic-tac-toe to end in a draw:

$\begin{array}{c c c c c c c c c} \times & \text{O} & \times & & & & \times & \text{O} & \times \\ \text{O} & \times & \text{O} &&&& \text{O} & \times & \times \\ \text{O} & \times & \text{O} &&&& \text{O} & \times & \text{O} \\ \end{array}$

Now consider a $3 \times 3 \times 3$ game with each of the above cases as the bottom board. Let's work with the left board first. Consider the center space in the middle board: it must be either an X or an O. If it is an O, the middle row on the top board must have Xs on the left and right in order to avoid 3-in-a-rows between the three levels. Similarly, there must be Xs in the middle of the bottom row and on the left and right in the top row of the top level. (For the tables below, the left diagram will represent the bottom board, the center diagram will represent the middle board, and the right diagram will represent the top board.)

$\begin{array}{c c c c c c c c c c c c c c c} \times & \text{O} & \times &&&&-&-&-&&&& \times & - & \times \\ \text{O} & \times & \text{O} &&&&-& \text{O} &-&&&& \times & - & \times \\ \text{O} & \times & \text{O} &&&&-&-&-&&&&-& \times & - \end{array}$

Then all the other spaces on the top level must be Os in order to block 3-in-a-rows on the top level:

$\begin{array}{c c c c c c c c c c c c c c c} \times & \text{O} & \times &&&&-&-&-&&&& \times & \text{O} & \times \\ \text{O} & \times & \text{O} &&&&-& \text{O} &-&&&& \times & \text{O} & \times \\ \text{O} & \times & \text{O} &&&&-&-&-&&&& \text{O} & \times & \text{O} \end{array}$

Then the bottom corners of the middle board must be Xs in order to block vertical 3-in-a-rows. Also the bottom middle of the middle board must be an X to block diagonal 3-in-a-rows between the levels. But this forces there to be 3 Xs in a row! So we can't get a draw this way:

$\begin{array}{c c c c c c c c c c c c c c c} \times & \text{O} & \times &&&&-&-&-&&&& \times & \text{O} & \times \\ \text{O} & \times & \text{O} &&&&-& \text{O} &-&&&& \times & \text{O} & \times \\ \text{O} & \times & \text{O} &&&& \color{#D61F06}{\times} & \color{#D61F06}{\times} & \color{#D61F06}{\times} &&&& \text{O} & \times & \text{O} \end{array}$

Now consider the possibility where we start with the same bottom level and the center square of the middle level is an X. Then we are forced to have 4 Os in the top level: the center, top center, and bottom corners.

$\begin{array}{c c c c c c c c c c c c c c c} \times & \text{O} & \times &&&&-&-&-&&&& - & \text{O} & - \\ \text{O} & \times & \text{O} &&&&-& \times &-&&&& - & \text{O} & - \\ \text{O} & \times & \text{O} &&&&-&-&-&&&& \text{O} & - & \text{O} \end{array}$

Then we are forced to have Xs in the top level top corners, and bottom middle. Also we must have Xs in the middle level in the top, middle and bottom corners. But now there are 3 Xs in a row, shown in red: a top corner on the bottom level, the middle top on the middle level, and the opposite top corner on the top level.

$\begin{array}{c c c c c c c c c c c c c c c} \color{#D61F06}{\times} & \text{O} & \times &&&&-& \color{#D61F06}{\times} &-&&&& \times & \text{O} & \color{#D61F06}{\times} \\ \text{O} & \times & \text{O} &&&&-& \times &-&&&& - & \text{O} & - \\ \text{O} & \times & \text{O} &&&& \times &-& \times &&&& \text{O} & \times & \text{O} \end{array}$

Now let's consider the other draw board as the base. With an O at the center of the middle board, we are forced into the following positions:

$\begin{array}{c c c c c c c c c c c c c c c} \times & \text{O} & \times &&&&-&-&-&&&& \times & - & \times \\ \text{O} & \times & \times &&&&-& \text{O} &-&&&& - & - & \times \\ \text{O} & \times & \text{O} &&&&-&-&-&&&&-& \times & - \end{array}$

$\Big \downarrow$

$\begin{array}{c c c c c c c c c c c c c c c} \times & \text{O} & \times &&&& \color{#D61F06}{\text{O}} & \color{#D61F06}{\text{O}} & \color{#D61F06}{\text{O}} &&&& \times & - & \times \\ \text{O} & \times & \times &&&&-& \text{O} &-&&&& - & - & \times \\ \text{O} & \times & \text{O} &&&&-&-&-&&&&-& \times & - \end{array}$

And with an X at the center of the middle board:

$\begin{array}{c c c c c c c c c c c c c c c} \times & \text{O} & \times &&&&-&-&-&&&& - & \text{O} & - \\ \text{O} & \times & \times &&&&-& \times &-&&&& \text{O} & \text{O} & - \\ \text{O} & \times & \text{O} &&&&-&-&-&&&& \text{O} & - & \text{O} \end{array}$

$\Big \downarrow$

$\begin{array}{c c c c c c c c c c c c c c c} \times & \text{O} & \times &&&&-&-&-&&&& - & \text{O} & - \\ \text{O} & \times & \times &&&&-& \times &-&&&& \text{O} & \text{O} & - \\ \text{O} & \times & \text{O} &&&& \color{#D61F06}{\times} & \color{#D61F06}{\times} & \color{#D61F06}{\times} &&&& \text{O} & - & \text{O} \end{array}$

Thus, by contradiction, there is no way for the game to end in a draw.

---

Edit: @Sean Lourette has pointed out in the comments that I have, indeed, missed a third way for a draw to happen in $3 \times 3$ tic-tac-toe:

$\begin{array}{c c c} \text{O} & \times & \text{O} \\ \times & \times & \text{O} \\ \text{O} & \text{O} & \times \end{array}$

Taking that to be the bottom board and considering the case where there is an X in the center of the middle board, we are forced into the following positions:

$\begin{array}{c c c c c c c c c c c c c c c} \text{O} & \times & \text{O} & & - & - & - && \text{O} & - & - \\ \times & \times & \text{O} & & - & \times & - & & - & \text{O} & \text{O} \\ \text{O} & \text{O} & \times & & - & - & - & & - & \text{O} & - \end{array}$

$\Big \downarrow$

$\begin{array}{c c c c c c c c c c c c c c c} \text{O} & \times & \text{O} & & - & - & - && \text{O} & - & - \\ \times & \times & \text{O} & & \color{#D61F06}{\times} & \color{#D61F06}{\times} & \color{#D61F06}{\times} & & - & \text{O} & \text{O} \\ \text{O} & \text{O} & \times & & - & - & - & & - & \text{O} & - \end{array}$

And with an O at the center of the middle board:

$\begin{array}{c c c c c c c c c c c c c c c} \text{O} & \times & \text{O} & & - & - & - && - & \times & \times \\ \times & \times & \text{O} & & - & \text{O} & - & & \times & - & - \\ \text{O} & \text{O} & \times & & - & - & - & & \times & - & \times \end{array}$

$\Big \downarrow$

$\begin{array}{c c c c c c c c c c c c c c c} \text{O} & \times & \text{O} & & - & - & - && - & \times & \times \\ \times & \times & \text{O} & & \color{#D61F06}{\text{O}} & \color{#D61F06}{\text{O}} & \color{#D61F06}{\text{O}} & & \times & - & - \\ \text{O} & \text{O} & \times & & - & - & - & & \times & - & \times \end{array}$

---

A relevant theorem is the Hales-Jewett theorem , which states that "the higher-dimensional, multiplayer, $n$ -in-a-row generalization of a game of tic-tac-toe cannot end in a draw, no matter how large $n$ is, no matter how many people $c$ are playing, and no matter which player plays each turn, provided only that it is played on a board of sufficiently high dimension $H$ ". I'm not sure the case $H = 3$ would be "sufficiently high," however.

Another question stemming from this, is it possible to prevent a perfect logician from winning in just 4 of their turns if they had the first move and went in middle center to start the game?

Once a player such as X in the example given has played a winning line the game is over so there is no opportunity for Y to play on and complete a second wining line.

Bryan J Carter

I did somewhat like Zach, but a bit quicker. I showed that if the centre of the second layer is X then two X's adjacent on an edge will not lead to a draw. If the centre is O then the same principle applies to the O's. Details omitted! I also thought about letting X be 1 and O be 0. Let each square be a binary variable. We arrive at 36 sums over 27 variables for the rows, columns and diagonals. The sums must be 1 or 2 for a draw to occur. I couldn't take it further, maybe one of your readers can!

I wrote software to run 3d tictactoe games recursively. 800,000 games later - no ties. I took a flyer and selected 'No'.

Once a player put an x or circle, the end result by putting an x or circle can only mean one of the players will win and not both.