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

Question

If you follow the traditional Rubik's cube eating conventions,

• 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.)

Answer 1

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 \begin{equation}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 . \end{equation} 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.

Answer 2

The answer is

yes

and here's why:

It's actually pretty easy to do - if you start from the center and go in reverse, you'll probably succeed as long as you do it somewhat systematically.