A $3 \times 3 \times 3$ cube has no Hamiltonian path starting at the corner.

Question

We have a $3\times3\times 3$ cube which has $27$ cubes each $1\times1\times1$ stuck together as usual. $2$ cubes are neighbours if they have a common face. The corner cubes are the $8$ cubes at the corners of the big cube. Can the worm start from a corner cube and eat its neighbour cube, continuing until at the end the last cube eaten is the one in the center of the big cube which has 6 neighbour cubes?

Answer 1

HINT: Color the small cubes alternately black and white, like a three-dimensional checkerboard. Say the eight corner cubes are black.

• How many ‘steps’ from one cube to a neighbor must the worm make in order to eat all of the cubes?
• What color cube must the worm eat last?
• What color is the centre cube?

(Note that I’m assuming that you want the worm to eat all of the cubes, though you didn’t say so. If I’m wrong, please clarify the statement of the problem.)

Answer 2

Let me give a graphic theoretical argument

Hamiltonian Path: A path that visits each vertex exactly once

The problem statement is equivalent to determining whether there exists a Hamiltonian path on the 3-cube starting from a corner and ending at the center. We can describe the 3-cube as 27 lattice points. Without loss of generality, let the corner in which the mouse starts be the point $(0,0,0)$. Note that every edge along a path in the 3-cube will change the parity of the coordinate the mouse is at. A Hamiltonian path that traverses 27 vertices must contain exactly 26 edges.Therefore the origin and terminus of any Hamiltonian path on a 3-cube will be of the same parity. Since the center point is at $(1,1,1)$,there is no Hamiltonian path that starts at a corner and ends at the center. Done.