Tic-Tac-Toe to the Nth Dimension

Consider a $6 \times 6 \times 6$ outer shell built around the given $4 \times 4 \times 4$ cube. Each winning line of the $4 \times 4 \times 4$ intersects exactly two $1 \times 1 \times 1$ cubes in the outer shell. On the other hand, each such $1 \times 1 \times 1$ cube located in the outer shell lies on a single winning line. The total number of the winning lines, therefore, is given by

$\frac{6^3 - 4^3}{2} = \boxed{76}$

The tic-tac-toe board is a $4\times 4\times 4$ cube.

One must consider 3 different orientations: Up/Down, East/West, and North/South. First consider the winning lines which are composed of adjacent cubes:

For each orientation, there are $4\times 4=16$ winning lines. Therefore, there are $16\times 3=48$ winning lines of this type.

Now consider diagonals:

For each orientation, there are $2 \times 4=8$ winning lines. Therefore, there are $8\times 3=24$ winning lines of this type.

Now consider diagonals from opposite vertices of the cube:

There are exactly $4$ winning lines of this type.

In total, there are $48+24+4=\boxed{76}$ winning lines.

For an $n^d$ cube, the solution is $L(n,d) = \frac{(n+2)^d - n^d}2.$ Here, $L(4,3) = \frac{6^3 - 4^3}2 = \frac{216 - 64}2 = \boxed{76}.$

Rationale

For each of the $d$ dimensions, choose

• either one of the $n$ positions,

• or one of the two directions to traverse that dimension (e.g. left to right or right to left).

This yields $(n+2)^d$ possible choices. If for all dimensions the first option was selected, we are dealing with a single box; this does not count, so we subtract out these $n^d$ possibilities.

Each of the remaining $(n+2)^d - n^d$ possibilities describes a way to traverse the cube in some way. However, each row is now covered twice: left-to-right and right-to-left, top-to-bottom and bottom-to-top, and so on. Therefore we finally divide by two.

Alternatively ,

• There are $d$ choices for the "diagonality" of the row, i.e. the number of dimensions that varies: $\Delta = 1$ for horizontal/vertical, $\Delta = 2$ for plane diagonals, $\Delta = 3$ for body diagonal.

• For each diagonality $\Delta$ , there are $\binom d \Delta$ ways to pick the varying dimensions.

• For each of these choices, there are $2^{\Delta-1}$ different directions for the row.

• For each of these directions, there are $n^{d - \Delta}$ rows (based on the dimensions that do not vary).

Thus,

$L(n,d) = \sum_{\Delta = 1}^d \binom d \Delta 2^{\Delta - 1} n^{d - \Delta} \\ = \frac12\left(\sum_{\Delta = 0}^d \binom d \Delta 2^\Delta n^{d - \Delta} - \binom d 0 2^0 n^d \right) \\ = \frac12((n+2)^d - n^d).$

Something else to consider: our $4^3$ tic-tac-toe game is a first player win. What is the winning strategy?

I didn't come up with the solution of considering an outer shell that others did. I considered the lines associated with the faces, edges and vertexes like Andy Hayes did. Namely that there are 6 faces each of which is associated with 16 ( $n^2$ ) winning lines, 12 edges each associated with 4 ( $n^1$ ) winning lines and 8 vertexes each associated with 1 ( $n^0$ ) winning lines. This double counts each winning line so add those up and divide them by 2 to get 76.

For the bonus question I found the solution:

${\Large f({d,n}) = \sum_{x=0}^{d-1} \frac{1}{2} \binom{d}{x} 2^{d-x} n^{x}}$

This is similar to Arjen Vreugdenhil's alternative solution. The winning lines associated with vertexes are being counted when x=0, those associated with edges when x=1, faces when x=2. I find it interesting and hard to imagine how there can be winning lines associated with cubes when considering hypercubes (counted when x=3).

The $\Large \binom{d}{x}$ part of the equation counts how many edges, faces, cubes or hypercubes (cubes of dimension x) are associated with each vertex of the total board, that is multiplied by $\Large 2^{d-x}$ since there are $\Large 2^d$ vertexes in a cube of dimension d but each cube of dimension x is counted $\Large 2^x$ times. $\Large n^x$ is the number of winning lines associated with each cube of dimension x and the $\Large \frac{1}{2}$ is to account for double counting the winning lines.