# Can you eat a 4-dimensional Rubik's Cube?

• Start by eating any piece except the central one
• Next, eat a piece orthogonally adjacent to the previously eaten piece
• (repeat)
• The last piece to get eaten in this way must be the centre piece

can you eat all the 81 pieces of a 3x3x3x3 Rubik's Hypercube?

To make the task at least a little easier to visualise, here's an animated schematic showing what might happen to the stickers (which are actually 3d cubes glued to all the outwards-facing sides of the 4-dimensional cubelets) if you start by eating a corner piece:

Original image (public domain) from Wikimedia Commons.

(Due to the inadequacies of our low-dimensional universe, only 7 sides have their stickers shown in the picture: the eighth side is adjacent (on the "outside") to all the other sides except the blue one, so it would look pretty weird.)

• Reading this question without a context feels very weird. I think "eat" word can be explained a little to not shock people like me :) Dec 13, 2022 at 20:25
• @Minot Well, it's my best attempt at conveying the concept of "find a Hamiltonian path on a 4-dimensional grid" without ever mentioning graphs, lattices, or "you can only visit each (hyper)cubelet once", AND it makes for a lovely question title; what's not to like :-)
– Bass
Dec 13, 2022 at 22:33

Yes.

In fact we can say something much more general. First, for any simple graphs $$G = (\mathcal{V}_G, \mathcal{E}_G)$$ and $$H = (\mathcal{V}_H, \mathcal{E}_H)$$, define the Cartesian product $$G \operatorname{\square} H$$ of $$G$$ and $$H$$ to be the (simple) graph with

• vertex set $$\mathcal{V}_{G \times H} := \mathcal{V}_G \times \mathcal{V}_H$$, and
• an edge between vertices $$(v,w), (v', w') \in \mathcal{V}_{G \times H}$$ if and only if
• $$v = v'$$ and there is an edge in $$\mathcal{E}_H$$ from $$w$$ to $$w'$$, or
• $$w = w'$$ and there is an edge in $$\mathcal{E}_G$$ from $$v$$ to $$v'$$.

If we denote by $$P$$ the path graph

T   0   1
o---o---o


on three vertices, then the graph $$\Gamma$$

• whose vertex set is the set of pieces in the 4D Rubik's cube, and
• for which two vertices share an edge if and only if the pieces are adjacent, is just $$P^{\square 4} = P \operatorname{\square} P \operatorname{\square} P \operatorname{\square} P .$$ In this language, the problem is whether you can find a path in $$\Gamma$$ that visits every vertex exactly once, i.e., a Hamiltonian path, that ends (equivalently, starts) at the middle piece, $$(0, 0, 0, 0)$$.

Consider any Hamiltonian path $$(v_1, \ldots, v_9)$$ of $$P \operatorname{\square} P$$, e.g., $$((1, 1), (0, 1), (T, 1), (T, 0), (T, T), (0, T), (1, T), (1, 0), (0, 0)).$$ Then, the path $$((v_1, v_1), \ldots, (v_1, v_9), (v_2, v_9), \ldots (v_2, v_1), (v_3, v_1), \ldots, (v_9, v_9))$$ is a Hamiltonian path for $$(P \operatorname{\square} P) \operatorname{\square} (P \operatorname{\square} P) = \Gamma$$, and if $$v_9 = (0, 0)$$, then the path in $$\Gamma$$ at $$(v_9, v_9) = (0, 0, 0, 0)$$, i.e., the center piece. (Remark: Deusovi's solution is not of this form for any Hamiltonian path on $$P \operatorname{\square} P$$.) If we identify $$(a, b, c, d)$$ with the integer whose balanced ternary representation is $$abcd_{\operatorname{bal}\!3}$$, the Hamiltonian path of $$\Gamma$$ determined by the above Hamiltonian path on $$P \operatorname{\square} P$$ is $$$$40, 37, 34, 33, 32, 35, 38, 39, 36,\\ 9, 12, 11, 8, 5, 6, 7, 10, 13,\\ -14, -17, -20, -21, -22, -19, -16, -15, -18,\\ -27, -24, -25, -28, -31, -30, -29, -26, -23,\\ -32, -35, -38, -39, -40, -37, -34, -33, -36,\\ -9, -6, -7, -10, -13, -12, -11, -8, -5,\\ 22, 19, 16, 15, 14, 17, 20, 21, 18,\\ 27, 30, 29, 26, 23, 24, 25, 28, 31, \\ 4, 1, -2, -3, -4, -1, 2, 3, 0 .$$$$ In this notation, pieces $$A$$ and $$B$$ are adjacent iff $$|A - B|$$ is a power of $$3$$, and the center piece is $$0$$.

More generally:

If $$G$$ and $$H$$ are simple graphs with respective Hamiltonian paths $$(v_1, \ldots, v_k)$$ and $$(w_1, \ldots, w_\ell)$$, then $$((v_1, w_1), \ldots, (v_1, w_\ell), (v_2, w_\ell), \ldots (v_2, w_1), (w_3, v_1), \ldots, (v_k, w_\bullet)$$ is a Hamiltonian path on $$G \operatorname{\square} H$$ starting (equivalently, by reversing the path, ending) at $$(v_1, w_1)$$. The path ends at $$(v_k, w_1)$$ if $$k$$ is even and $$(v_k, w_\ell)$$ if $$k$$ is odd.

Example

More generally, the analogous graph for the $$n$$D Rubik's cube is $$P^{\square n}$$. The $$2$$D Rubik's cube is plainly edible (via a path ending at the center), so induction shows that so is any even-dimensional Rubik's cube. An analogue of the usual negative solution for the $$3$$D case shows that any odd-dimensional Rubik's cube cannot be eating ending at the center, i.e., precisely the even-dimensional Rubik's cubes are edible via a path ending at the center.

• That interesting dimension parity factoid in the final spoiler block was actually my original motivation for posting this puzzle, glad you caught it! I realised only later I had unintentionally sacrificed generality on the altar of readability: by my wording of the rules, the 0-dimensional case doesn't follow the pattern anymore, because the center piece is the only piece, and therefore starting is impossible. Oh well. :-)
– Bass
Dec 9, 2022 at 23:54