Maths Olympiad Prep

Library / /15 of 18

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:
A 3×3×33 \times 3 \times 3 cube is made out of 27 subcubes. On every face shared by two subcubes, there is a door allowing you to move from one cube to the other. Is it possible to visit every subcube exactly once if
(a) You may start and end wherever you like
(b) You must start at the center subcube?

Solution

Solution:
(a) It is possible. Here is one of many possible routes.
Figure 1
Level 1
Level 2
Level 3

(b) It is impossible. Color the subcubes black and white alternately as shown:
Figure 2
Level 1
Figure 3
Level 2
Figure 4
Level 3
Every door connects a black subcube to a white subcube. Since the central subcube is white, the route must begin
White→Black→White→Black→⋯ . \text{White} \rightarrow \text{Black} \rightarrow \text{White} \rightarrow \text{Black} \rightarrow \cdots.
Examining the first 27 subcubes visited, we see that 14 are white and 13 are black, a contradiction since the actual cube has 14 black and 13 white subcubes.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.