12
$\begingroup$

This puzzle takes place on the surface of the following gridded, beveled cube:

gridded, beveled cube with an ant on it

The surface of this cube is divided into 3458 small regions separated by black lines. Of these regions, 3450 of them are squares, and 8 of them are triangles. Of the squares, 3174 are on the flat faces of the cube (23 × 23 = 529 per face, × 6 faces = 3174), and 276 of them are on the beveled edges (23 per edge, × 12 edges = 276). The 8 triangles are at the corners.

If you look very closely, you will notice that this cube has an ant crawling on it. This is no ordinary ant. It is a magical, immortal ant born* to pursue a single goal. The ant's goal is to find a single, continuous path that will take the ant through all of the 3458 regions on the cube, each exactly once. The ant has been trying to find a way to do this for a long, long time, and has so far never succeded.

Can it be done? Your task is to either prove this is possible, or prove it is not.

Some rules, caveats, and clarifications:

  1. The path must visit each of the 3458 regions (all 3450 squares, and all 8 triangles) exactly once.
  2. The path may start in any region, and may end in any region.
  3. The ant may only move between regions that share a border. (The regions can't just touch at the corners.)
  4. Assume that the cube is magically suspended in the air, and that the ant can walk equally well on any surface in any orientation without risk of falling off.
  5. The ant never gets tired, hungry, bored, will never die of old age, be eaten by a lizard etc., etc. This is not a lateral thinking puzzle. The solution is based on a simple mathematical insight.

* OK, fine. Hatched to pursue a single goal.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
16
$\begingroup$

The answer is that it

cannot be done.

because

the surface of the cube can be given a checkerboard colouring, and there are two more of one colour than the other. A checkerboard colouring means that every square/triangle region is coloured either black or white, such that adjacent regions always differ in colour. Any path that the ant takes will have to alternate colours all the way, so at best there can be one more of one colour than the other, but not two.
Specifically, colour the 23x23 faces so that the corner squares are black. Each face has 265 black squares and 264 white ones. The bevelled edges must then be coloured starting and ending in white, so they each have 12 white and 11 black. The triangles must be coloured black. This gives 1730 black and 1728 white regions.
This is closely related to Euler's characteristic: V-E+F=2. The faces and vertices have one more black than white, the edges one fewer black than white, so the net difference is 2.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Well done! Your explanation can also be extended to cubes/boxes with other dimensions, as long as rot13(rirel syng snpr unf n pragre fdhner, juvpu bayl unccraf vs nyy qvzrafvbaf (va grezf bs ahzore bs havg phorf ba gur syng snprf) ner bqq. Vs whfg bar qvzrafvba vf na rira ahzore, gura lbh jbhyq or noyr gb qvivqr gur funcr vagb gjb unyirf gung ner vqragvpny rkprcg jvgu gur purpxreobneq pbybevat erirefrq, juvpu jbhyq thnenagrr rdhny ahzoref bs oynpx naq juvgr ertvbaf.) $\endgroup$
    – plasticinsect
    Commented Jul 17, 2023 at 16:42
  • 2
    $\begingroup$ @plasticinsect With the last sentences of my answer I was thinking of another generalisation, namely to the Platonic solids with triangular faces, which can also be beveled and have their faces split into $n^2$ regions with odd $n$. $\endgroup$
    – Jaap Scherphuis
    Commented Jul 17, 2023 at 20:17
1
$\begingroup$

Unless I am missing something (edit: I was missing something :) see Jaap Scherphuis' answer/comment, or try to find the mistake in my answer)

such a path exists. Actually it is also not too complicated, scales to bigger sizes, and is not too hard to find.

The basic idea is to

view the cube as a kind of four-sided tube with a square on top and bottom. The sides of the tube can be traversed layer by layer as such:

Partial path on the cube

The only thing that is left is

To find a path for the top that ends in the square from which the path depicted starts, and a path for the bottom region. That's straight forward as we can just zig-zag through the sqaure, changing direction half way to ensure we land in the middle and not some corner:

Path through square

Note that the first line on the left is necessary for odd sized squares only to ensure we actually land in the middle and not the corner. For the bottom we can then use the same pattern. Also since the path through the sides translates one sqaure to the side on each layer, we have that the path on the sides also ends somewhere in the middle, so we don't have to take care of the triangles in any special way as they are always handled by the first and last layer on the path on the sides.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ When you traverse the sides layer by layer, how do you know that you will end up in the middle of the side of the bottom face? $\endgroup$
    – Jaap Scherphuis
    Commented Jul 17, 2023 at 9:10
  • $\begingroup$ See the last paragraph: If you start the first layer in the middle on some side, you will end up in the middle of the side to the left of the side you started with as the starting point in each layer moves to the left by 1 square. In the general case where we don't necessarily have a cube but arbitrary side lengths you can almost always modify the path on the top square to shift around at which point you go onto the first layer. For large enough side lengths (I think 3 or 4 suffices) you can always find a path s.t. neither the first nor the last layer start/end at a corner. $\endgroup$
    – PattuX
    Commented Jul 17, 2023 at 9:17
  • 3
    $\begingroup$ Your path that fills the square uses a zig-zag pattern along the top to fill the area above the entrance/exit at the side of the square. That means that this pattern only works for an entrance/exit that is an even distance from the corners. Unfortunately, the 23 layers shift an odd distance, so your face-filling pattern only works on one side. $\endgroup$
    – Jaap Scherphuis
    Commented Jul 17, 2023 at 9:19
  • 2
    $\begingroup$ Oh, you're right. I guess I was too hand-wavy then when it comes to the bottom side. Now I see how your answer contradicts mine, thanks! $\endgroup$
    – PattuX
    Commented Jul 17, 2023 at 9:26
  • 1
    $\begingroup$ Not correct, (as @JaapScherphuis explains well) but an understandable mistake. It really looks like this approach should work. Even knowing the answer, I find my intuition trying to fight back. (That's one of the things I like about this class of puzzle, honestly.) $\endgroup$
    – plasticinsect
    Commented Jul 17, 2023 at 16:27
-2
$\begingroup$

Another approach:

First, draw the cube as a connected graph. Each region is a node, and is joined to the regions it shares a border with by a line. The question is thus asking "given such a graph, does an Eulerian path/trail exist?" Undirected graphs have an Eulerian trail if and only if exactly zero or two nodes have odd degree; here, we have eight nodes with odd degree (our eight triangular regions are all connected to three other regions), so there is no Eulerian trail and the ant's task is impossible.

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ The question asks for a Hamiltonian path (visits all nodes exactly once) rather than a Eulerian path (traverses all edges exactly once). The (non)existence of a Hamiltonian path is in general much harder to prove. $\endgroup$
    – Jaap Scherphuis
    Commented Jul 18, 2023 at 14:37
  • 4
    $\begingroup$ No, sorry, the conclusion is correct, but the reasoning is not. If you change the puzzle so the faces have an even dimension (say, 2×2) the puzzle becomes easily solvable. However, there are still eight corner nodes that have an odd degree. $\endgroup$
    – plasticinsect
    Commented Jul 18, 2023 at 16:41

Your Answer

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

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