FMM6

Friday Morning Math Problem

The Termite and the Cube

Imagine a large cube formed by gluing together 27 smaller wooden cubes of uniform size.

A termite starts at the center of the face of any one of the outside cubes and bores a path that takes it once through every cube. Its movement is always parallel to a side of the large cube, never diagonal.

Is it possible for the termite to bore through each of the 26 outside cubes once and only once, then finish its trip by entering the central cube for the first time? If possible, show how it can be done; if impossible, prove it.

(Note: It is assumed that the termite, once it has bored into a small cube, follows a path entirely within the large cube. Otherwise, it could crawl out on the surface of the large cube and move along the surface to a new spot of entry. If this were permitted, there would be no problem.)

Solution

It is impossible for the termite to start its journey at the center of a face, and end its journey at the center of the cube. To demonstrate why it is impossible, imagine the cubes alternate in color, like the cells of a 3D checkerboard. The large cube consists of 13 cubes (including the small center cube) of one color (say, blue) and 14 cubes (including the centers of the faces of the cube) of the other color (say, yellow). The termite's path is always through cubes that will alternate in color along the way. Therefore, if the path includes all 27 cubes, it must begin and end with a cube belonging to the set of 14 (yellow). However, we can see that the set of 13 includes the small center cube. So, a traversal meeting the given conditions is impossible. To generalize the problem to cubes of order N: If the cube is of even order, has the same number of cells of one color as it has cells of the other color. There is no central cube, but complete paths may start on any cell and end on any cell of opposite color. A cube of odd order has one more cell of one color than the other, so a complete path must begin and end on the color that is used for the larger set. The central cell belongs to the samller set, so it cannot be the end of any complete path. No closed path, going through every unit cube, is possible on any odd-order cube because of the extra cube of one color. Analogous parity checks for 2D problems: It is not possible for a rook to start at one corner of a chessboard and follow a path that carries it once through every square and ends on the square at the diagonally opposite corner.