[ GraphTraversal ]  $[$ Chess Coloring ]

Imagine a large cube made up of 27 smaller cubes. A termite sits on the center of one face of one of the outer cubes and starts to gnaw its way through. Once the termite has visited a cube, it does not return to it. It always moves parallel to one of the edges of the large cube. Can the termite gnaw through all 26 outer cubes and end its journey in the central cube? If possible, show what the termite's path should be.

#
We will paint the cubes in a checkerboard pattern so that the corner cubes are black. This will result in 14 black and 13 white cubes. Since the termite alternates the colors of the cubes it visits, and the last cube is white by condition, the termite can visit no more than 13 black cubes on its way to it, meaning it must have missed at least one black cube.

## Answer

Cannot.

Problem