A mouse intends to eat a 3 times 3 times 3 cube of cheese It

A mouse intends to eat a 3 times 3 times 3 cube of cheese. It begins at a corner and eats the whole of a 1 times 1 times 1 cube before going to an adjacent one. Can the mouse end in the center?

Solution

Solution:

Partition the nodes into four sets: corner cubes (C), edge cubes (E), face cubes (F), and the center cube (CC).

The sizes of the sets are 8, 6, 12 and 1 respectively.

Nodes in C connect only to nodes in E. Nodes in E connect only to nodes in C and nodes in F.

Nodes in F connect only to nodes in E and to the CC.

We know we have to visit each node, starting with a corner and ending with the center.

Since we don\'t end on a corner, and C-nodes only connect to E-cubes, we know that after visiting a C-node, we must visit an E-node.

We know that the second last node to be visited must be in F, since nothing else connects to CC.

So, after visiting the last node in F, we\'d need to visit CC.

After visiting each of the other five nodes in F, we\'d need to visit a node in E.

Hence, visiting each node in C and F means we must make 8 + 5 = 13 visits to nodes in E.

Since |E| = 12, this is impossible. Hence, no Hamiltonian path exists from a corner to the center.