## PROBLEM 13. TIC-TAC-TOE

Consider the game of "tic-tac-toe" on a three-dimensional cube $8 \times 8 \times 8$. How many straight lines can be indicated on which 8 symbols lie in a row?
Solution. This is not a difficult problem; it can be solved by simple counting. However, there is a brilliant solution proposed by Leo Moser. It involves considering a $10 \times 10 \times 10$ cube, obtained by covering the given $8 \times 8 \times 8$ cube with a layer of unit thickness. A winning line in the inner $8 \times 8 \times 8$ cube intersects two of the unit cubes surrounding this cube, and each unit cube in the shell is intersected by one winning line. Thus, each winning line corresponds to a unique pair of unit cubes in the outer shell, and the number of winning lines is half the number of unit cubes in the shell, which is

$$
\frac{10^{3}-8^{3}}{2}=\frac{1000-512}{2}=244
$$

This approach is entirely general. The number of winning lines for a cube with side length $k$ in $n$-dimensional space is

$$
\frac{(k+2)^{n}-k^{n}}{2}
$$