5
$\begingroup$

There is a $3 \times 3 \times 3$ cube block, starting at the corner, you are allowed to take 1 block each time, and the next one must share a face with the last one. Can it be finished in the center?

This is a question about graph theory (I think), and obviously it is impossible to finished in the center. I start to consider about the Hamiltonian path and the degree of each vertex , but it is different because you have to start and end with a specific vertex. Can anyone tell me the reason why it is impossible?

$\endgroup$
  • $\begingroup$ By "finish" do you mean that we finish when all blocks have been removed? $\endgroup$ – Banach Tarski Mar 11 '16 at 9:40
  • $\begingroup$ Is this the Bridges of Königsberg problem? $\endgroup$ – Wouter Mar 11 '16 at 9:46
  • $\begingroup$ @Wouter Not exactly. If you want a Königsberg comparison, we are not asking if there is a way to use all bridges exactly once, but rather visit each island and both riverbanks exactly once without using any bridge more than once. $\endgroup$ – Arthur Mar 11 '16 at 9:53
  • $\begingroup$ This question appears to be asking for a Hamiltonian path on the dual graph. $\endgroup$ – Michael Burr Mar 11 '16 at 11:17
13
$\begingroup$

An approach coloring the cubies.

Let's color the individual cubes red and blue. We paint them in a "checker" (the 3D version, that is) pattern, so that the corners are red and the middles of each sides are blue, the centers of each face red, and the center of the cube blue, like this (created with POV-Ray):

Colored cube

Now let's say we have a path that starts at a red piece (at a corner), and ends in the center, a blue piece. Let's count the number of red and blue pieces we need to go through. There are $14$ red pieces and $13$ blue pieces. Since we start at a red, and end at a blue, and we need a "Red, Blue, Red, Blue, ..., Red, Blue" pattern (since each color only has neigbours of another color), this is never going to work: since, for such pattern, and $14$ "Red"s we need $14$ "Blue"s, but we only have $13$! So this is not possible.


A (possibly equivalent) approach using graph theory.

Since you mentioned graph theory, let's look at it that way, too. We make a graph with $27$ points (one for each cube) and two points are connected if and only if the cubes they represent share a face. Note that this graph is bipartite, since it only contains even cycles. An image of the graph we get (created with GeoGebra):

Bipartite cube graph

Now note that on the left side (that's the side where the corners of the original cubes are) we have $14$ points, while on the other side we have only $13$ points. Now we need to find a path that starts on the left side and ends on the right side. But we have to go back an forth between the left and right side, so when we've reached all $13$ points on the right side, we still have one left on the left side. Thus, such path does not exist.

$\endgroup$
7
$\begingroup$

Set a coordinates system, where every block corresponds to a triplet $(a,b,c)$, for example, the starting cornere will be $(1,1,1)$ and the center ($2,2,2)$. Every time you move from a block to another who shares a face with the previous you add or subtract $1$ from the previous triplet. You start from $(1,1,1)$ and you want to finish in $(2,2,2)$ with $26$ steps. Call $a$ the number of $+1$ and $b$ the number of $-1$, you must have $$a+b=26$$ and $$a-b=2+2+2-1-1-1=3$$ and this is not possible.

$\endgroup$

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.