7
$\begingroup$

A cube of dimension $3×3×3$ is made of sugar and consists of $27$ small cubical sugar pieces arranged in the $3×3×3$ pattern. An ant is eating the sugar in such a way that it starts at one of the corners and eats smaller pieces one by one. After the ant finishes one piece, it moves to the adjacent piece (pieces are adjacent if they share a face). Is it possible that the last piece the ant has eaten is the central one?

Remark: Pieces don‘t fall down if a piece underneath is eaten first.

After many attempts to find a route for the ant to follow so that the last piece it eats is the central one, it seems like it is impossible.

Now to try and explain why is where I need help, I tried to work backwards and see where the ant needs to end up in order to be in a position where it is adjacent to the central piece but I just do not know how to prove that this is impossible.

Improve this question
$\endgroup$
7
  • 7
    $\begingroup$ Please forgive me for asking this, but is this homework? $\endgroup$
    – Gareth McCaughan ♦
    Nov 30, 2016 at 1:33
  • 2
    $\begingroup$ Have you learned about this question in a graph theory course? Then it might be a good idea to represent your sugarcube by a graph. And then, the ant's path could be a very special one. Perhaps you learnt about that too? Perhaps you have learnt about certain theorems guaranteeing that no solution (= no "special" path) exist? $\endgroup$
    – Matsmath
    Nov 30, 2016 at 6:52
  • $\begingroup$ Possible duplicate of Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph $\endgroup$
    – Peregrine Rook
    Nov 30, 2016 at 7:17
  • $\begingroup$ @matsmath I haven't taken graph theory, my combinatorics professor gave this problem to us to figure out on our own, I guess since it's more graph theory than combinatorics (he's not teaching us any graph theory). I have a textbook in applied combinatorics that also has a huge section on graph theory, what can I read up on to get more knowledge for these types of questions? $\endgroup$
    – idknuttin
    Nov 30, 2016 at 12:30
  • $\begingroup$ @PeregrineRook Technically it is not a duplicate as the path in the original is restricted to a 2D square grid and the goal is slightly different. Nevertheless you are right that the same method applies. $\endgroup$
    – kaine
    Nov 30, 2016 at 16:59

5 Answers 5

Reset to default
7
$\begingroup$

A cube of dimension $3×3×3$ is made of sugar and consists of 27 small cubical sugar pieces arranged in the $3×3×3$ pattern. An ant is eating the sugar in such a way that it starts at one of the corners and eats smaller pieces one by one. After the ant finishes one piece, it moves to the adjacent piece (pieces are adjacent if they share a face). Is it possible that the last piece the ant has eaten is the central one?

Since the way you've phrased the problem doesn't require the ant to have eaten all the 27 sub-cubes when it stops, it can be solved as stated. For example, assume that the ant starts at the bottom front left corner of the cube, and follows the path:

right, up, up, back, back, down, left, front, down, right, right, up, left

At the end of this path, the ant ends up at the central piece, and cannot continue further: all the adjacent pieces have already been eaten. Of course, there are still 13 uneaten pieces left, but the ant cannot reach any of them without moving through a piece that it has previously visited.

Of course, if the ant must eat all the 27 pieces, then it cannot finish at the center. To see why,

color the pieces alternately black and white (like a 3-dimensional analogue of a chessboard, so that all the pieces adjacent to a black piece are white and vice versa), and consider what the color of the last piece consumed by the ant must be.

In fact, this argument is even sufficient to show that, regardless of where the ant starts, it cannot eat all 27 pieces in the specified manner and end up at the center!

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ thank you for your answers, but based on your first answer I wanted to ask you if you are a lawyer, or if you like law? $\endgroup$
    – idknuttin
    Dec 1, 2016 at 1:02
  • 1
    $\begingroup$ if I color the 8 corner pieces black then the central piece will end up being white and we will have 14 black pieces and 13 white pieces, since we have one more black piece than white piece, the ant must consume a black piece as the last piece, is this a correct way of thinking about it? $\endgroup$
    – idknuttin
    Dec 1, 2016 at 1:13
  • 1
    $\begingroup$ @idknuttin: Yes, exactly. $\endgroup$
    – Ilmari Karonen
    Dec 1, 2016 at 1:14
22
$\begingroup$

I will give you a hint rather than an answer (because I think you will enjoy this more by solving it yourself):

Parity.

I would encourage others not to post an outright solution, at least for a few days; aside from anything else, this will give idknuttin the satisfaction of answering his own question when he figures it out :-).

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ yes this is homework, a hint that will help me figure out the answer is much better, I was not looking for a solution $\endgroup$
    – idknuttin
    Nov 30, 2016 at 1:45
  • 2
    $\begingroup$ @idknuttin You should say that and request a hint not an answer specifically in your question. $\endgroup$
    – boboquack
    Nov 30, 2016 at 2:02
  • $\begingroup$ @idknuttin Let's hope my hint is helpful but not too helpful, then :-). $\endgroup$
    – Gareth McCaughan ♦
    Nov 30, 2016 at 2:05
  • 4
    $\begingroup$ +1 for "this will give idknuttin the satisfaction of answering his own question when he figures it out". It's all about that satisfaction :) $\endgroup$
    – Netham
    Nov 30, 2016 at 13:12
5
$\begingroup$

This can be done with various approaches, I have tried using a very simple logical approach here without any previous knowledge required (only a pencil & paper)

If you try seeing what are the possible moves you will get something like this in the end, which represents all the possible paths the ant can take (this can be deduced)

Corner Cube (8) <--> Edge Cube (12) <--> Face Center Cube (6) <--> Central Cube (1)

The bi-directional arrow suggests ant can move in either direction if a cube is there. So from Edge Cube ant can move to a face center cube and back or a corner cube and back, but it cannot move from corner to face center cube or corner to central cube. Let's label the paths: path1, path2 and path3. No matter in what order the ant moves path1 will be traversed 16 times because there are 8 corner cubes (If you don't get it use a pen and paper to visualize). Understand this step as this will lead to the answer of your why, you will be able to see it :) Now I will leave you here as suggested by @Gareth.
p.s. Will update with the complete solution later.

Improve this answer
$\endgroup$
3
$\begingroup$

Naive solution:

Consider an integer grid indexing. i.e. $X$, $Y$ and $Z$ axes with the sub cubes indexed 1,2 or 3 along each axis.

So the sub cubes can be referred to as $(x,y,z)$ with $1<=x,y,z<=3$

Without loss of generality, let's assume the ant starts from $(1,1,1)$. The center cube will be $(2,2,2)$.

Now every move along a face only changes one coordinate by $+1$ or $-1$. If the sum of the coordinates of any one position $x+y+z$ is called $s$ then any given move will change $s$ by $±1$.

So if $s_n$ is odd the then next position $s_{n+1}$ is even and vice versa.

To go from the start to the end one must exhaust all $27$ sub-cubes so $26$ moves are needed. The starting point's $s$ is $1+1+1 = 3$ is odd.

Hence the last sub-cube must also be an odd $s$ sub-cube. But $2+2+2=6$ is even. Therefore, the ant cannot end on the center cube.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Can someone edit this to add a spoiler tag for me? I couldn't figure out how to! Thanks. $\endgroup$
    – curious_cat
    Nov 30, 2016 at 16:23
  • $\begingroup$ This is the answer Garth meant and decided not to post because it was homework. $\endgroup$
    – kaine
    Nov 30, 2016 at 16:55
  • $\begingroup$ @kaine Ah! Should I delete my post? $\endgroup$
    – curious_cat
    Nov 30, 2016 at 16:56
  • $\begingroup$ I don't know the policy on that. $\endgroup$
    – kaine
    Nov 30, 2016 at 17:01
  • 1
    $\begingroup$ @curious_cat No, you should not.... $\endgroup$
    – user14478
    Nov 30, 2016 at 20:17
2
$\begingroup$

There is a trick that can be used to see this, very similar to the one outlined here. That problem is equivalent to a knight's tour on a chess board missing two corners on a diagonal, which is easier to relate to your problem.

If you can't figure out how they relate, let me know and I will post more.

EDIT: Here is the solution.

Colour the cubes starting with black in a corner. Use the rules that cubes that share a face must be different colours. You will end up with alternating coloured cubes. The 3 layers of 9 will look like this:

Top   Middle Bottom
BWB    WBW    BWB  
WBW    BWB    WBW  
BWB    WBW    BWB

Notice that the central cube is white and the corners are black. Also note that in order to eat all 27 cubes, the rat must move 26 times. An even number of moves will take it back to the same colour that it started on. Thus, after 26 moves, the rat must be on black, not white. Therefore, the rat cannot eat the central cube last.

Some other observations:

There are more black cubes (14) than white (13). Thus, any tour must start and finish on black. $B->W->B-> ... ->W->B$. This gives a tour of exactly one more black than white which is required for this setup.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I think I know how to solve that knight's tour on chess board with missing two corners on a diagonal, since there are 30 black squares and 32 white squares and the 2x1 piece can cover only one black and one white square it would be impossible to cover the chessboard because you will have 2 white squares left after placing 30 2x1 pieces on the chessboard and the 2x1 piece cannot cover two white squares. However I am not sure how this relates to the original problem? I don't think it's similar to the solution I figured out with llmari's help. $\endgroup$
    – idknuttin
    Dec 1, 2016 at 1:20
  • 1
    $\begingroup$ @idknuttin " I am not sure how this relates to the original problem?" - if the knight is on a white square, what color squares can it move to? $\endgroup$
    – alephzero
    Dec 1, 2016 at 5:37
  • 1
    $\begingroup$ @idknuttin Try colouring the squares of the cube in a checker board like pattern. what do you notice about how the ants move? What do you notice about the central cube and corner cubes? $\endgroup$
    – Trenin
    Dec 1, 2016 at 13:11
  • 1
    $\begingroup$ @idknuttin It may be a different solution than the one you already know, buti it is a good parity exercise. I will post the full solution in comments since you already have a working solution. $\endgroup$
    – Trenin
    Dec 1, 2016 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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