Suppose a game of X's and O's, "tick-tack-toe," is played on an 8 x 8 x 8 cube in 3-dimensional space. How many lines of "8-in-a-row" are there through the cube by which the game might be won?

Solution:

This is not a difficult problem and it yields to a straightforward count. However, a brilliant solution (one of Leo Moser's many) is to consider a 10 x 10 x 10 cube which encases the given 8 x 8 x 8 cube with a shell of unit thickness. The two-way extension of a winning line in the inner 8 x 8 x 8 cube pierces two of the unit cubes in the shell. And each unit cube in the shell is pierced by only 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 simply one-half the number of unit cubes in the shell, namely

This approach is perfectly general. The number of winning lines for a cube of edge k in n-dimensional space is

References

1. Ross Honsberger, Mathematical Morsels, MAA, 1978

Copyright © 1996-2008 Alexander Bogomolny