Tic-Tac-Toe in n-Dimensions
Jerome L. Paul · Mathematics Magazine · 1978
There are several three dimensional tic-tactoe games currently being marketed. Most of those games are played on a cubical board having 4 cells on a side, which we shall call a 4 x 4 x 4 game. Two players alternately choose a cell in the , / / / / 4 x 4 x 4 cube, the winner being the first player to / /> </ / the 24 diagonal rows, or the 4 main diagonals of / / / / the cube (see FIGURE 1), making 76 winning sets altogether. _ _ _ _ _ _ _ _ In going from the traditional two dimensional 3 x 3 game of tic-tac-toe to a three dimensional Z/ / game, there is good reason to add a fourth cell on L each side, since it is easy to see that the first player has an easy win in the 3 x 3 x 3 game if he Three typical winning sets in the 4 x 4 x 4 game. takes the center cubical on his first move. Moreover, two players cannot play tic-tac-toe to FIGURE 1. a tie in the 3 x 3 x 3 game even if they try! More precisely, whenever the cells in the 3 x 3 x 3 cube are divided arbitrarily into two sets, then at least one of the two sets will contain 3 cells in a row. We shall prove this fact below. Generalizing to n dimensions, it will be notationally convenient to consider an m x m x ... x m (n times) hypercube as having its cells centered at the points of an n-dimensional hypercube Cn(m) of lattice points in euclidean n-space having m points on a side, e.g., Cn(m) = {(xl, , Xn) E Zn: 1 < xi -' m}, where Z denotes the set of integers. A winning set in Cn(m) then consists of m points of Cn(Mi) lying along a straight line. Tic-tac-toe is played in Cn (m ) by two players alternately selecting a point in Cn (m), the winner being the first player to obtain a winning set. A tie partition of Cn(mi) is a partition of Cn(M) into two sets which differ in cardinality by at most one, and neither of which contains a winning set. We discuss in this note the question of determining the values of n and m for which tie partitions of Cn (m) exist. We shall not consider the question of when winning strategies exist, except to mention the fact that whenever tie partitions do not exist, then a well-known theorem in game theory implies that the first