### Random Post

### Recent Posts

### Recent Comments

geoffrounce on Enigma 440: Three X | |

Jim Randell on Enigma 1588: As easy as 1… | |

Jim Randell on Enigma 440: Three X | |

geoffrounce on Enigma 1106: Not a square… | |

Jim Randell on Tantalizer 458: Knifemen |

### Archives

### Categories

- article (11)
- enigma (1,156)
- misc (2)
- project euler (2)
- puzzle (39)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 177,401 hits

Advertisements

I took the view that a space-fly positioned on a vertex of the cube would be able to nibble three faces and three edges without having to move.

Solution:Both Dotty and Potty walk 3√2 inches (approximately 4.243 inches).Here are diagrams showing example paths (Dotty in blue on the left, Potty in red on the right):

There are many possible minimal paths for Dotty, although I like the one depicted above for several reasons. Not only does it visit each face, but it crosses each face, and has an equal length of path on each face. If you were to balance the cube on one vertex (the “South Pole”) with its opposite (antipodal) point directly above it (the “North Pole”) then this path is the “equator” of the cube, and if you were to slice the cube along this path the cut face would be a regular hexagon.

In fact any slice through such a cube in a plane parallel to the equator between the “Tropic of Cancer” (a plane defined by the other ends of the three edges the meet at the North Pole) and the “Tropic of Capricorn” (defined by the vertices of the edges emanating from the “South Pole”) defines a minimal traversal of the cube that crosses each face.

There is essentially only one minimal path for Potty, which is to start at a pole, travel diagonally across a face to a vertex on a tropic, and then travel diagonally across two more faces to take in the remaining two points on that tropic.

Here are the paths drawn out as straight lines on the net of the cube (again, Dotty in blue on the left, Potty in red on the right):

I found this a tricky problem to attack programatically. The approach I finally used was to divide the edges of the cube into n segments and then consider paths composed of straight lines across faces between these points. So that dividing the edges into 1 segment means considering only paths that join vertices of the cubes. Dividing the edges into 2 segments considers the vertices of the cube and also the mid-points of edges, and so on.

Fortunately there are minimal solutions when the edges are 1-segments, and shorter paths are not found when we consider 2-, 3- or 4-segment edges. I think considering the cube made of 4-segment edges is most informative as it considers the vertices, mid-points of edges and also “quarter points” half-way between the mid-point of an edge and the vertex. Although it takes a while to run the algorithm for 4-segments (it should be possible to reduce the run time by eliminating symmetrical paths), it’s enough to satisfy me that there are no shorter solutions.

The program actually considers an

n×n×ncube (which keeps the co-ordinates of the points nice and simple), and scales the distances down to correspond to the unit cube.As written the code will find all minimal paths that start at points from a vertex to the mid-point of a selected edge. You can specify on the command line which path you which to find (“D”, “P” or “DP”) and how many segments to divide the edges into. The default values are: “DP 2”.

I’d be interested to see any more direct proofs (programmatic or non-programmatic) that show the paths are minimal.

I think you mean there is essentially only one path for Potty. Dotty is t’other one.