10
$\begingroup$

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:

Animation of stickers getting eaten

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

$\endgroup$
2
  • $\begingroup$ Reading this question without a context feels very weird. I think "eat" word can be explained a little to not shock people like me :) $\endgroup$
    – Minot
    Dec 13, 2022 at 20:25
  • $\begingroup$ @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 :-) $\endgroup$
    – Bass
    Dec 13, 2022 at 22:33

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. :-) $\endgroup$
    – Bass
    Dec 9, 2022 at 23:54
11
$\begingroup$

The answer is

yes

and here's why:

image of three 3×3 grids, arranged themselves in a 3×3 grid

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.

$\endgroup$
2
  • 2
    $\begingroup$ Even if you start at the beginning rather than at the end, pretty much the only thing that can go wrong is if you start at one of the 40 even-parity positions instead of the 40 odd-parity positions. $\endgroup$ Dec 9, 2022 at 12:05
  • $\begingroup$ What about eating a different colour at each step? $\endgroup$ Dec 13, 2022 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.