11
$\begingroup$

Despite strong objections by many here at StackExchange, the mad scientist continues to use ethically questionable methods to study the spatial cognition of ants.

Last time, he left ant Juliet at a corner of a cubic box and placed ant Romeo at the opposite corner. Much to the mad scientist's surprise, without hesitation Romeo followed the shortest path over the sides of the box that brought him straight to Juliet.

Now the mad scientists has worked out a much bigger challenge for Romeo. Again he leaves Juliette at a corner of a box, but this time it is a 7-dimensional hypercubic box. Out of the 127 remaining corners, he selects the one that is furthest from Juliet. With a big grin the mad scientist places Romeo at this very corner.

Romeo is confused. He knows how to handle a box with 6 sides. But now as many as 672 square sides are available on the box. How should he optimize the journey to his beloved Juliet?

Can you help Romeo? How long is the shortest path (expressed in box edge lengths) to Juliet?

[Inspired by this recent puzzle.]

$\endgroup$
  • $\begingroup$ Am I right that this puzzle is exactly the same as the linked one except that instead of 98 dimensions you have 7? $\endgroup$ – Ivo Beckers Oct 4 '15 at 16:13
  • 2
    $\begingroup$ Now the ant is constrained to two-dimensional faces (In mine it was 97-dimensional, leaving many degrees of freedom for it to walk) $\endgroup$ – MathET Oct 4 '15 at 16:20
  • $\begingroup$ He was surprised because he thought Juliet would make the move first? $\endgroup$ – Florian F Oct 5 '15 at 13:35
9
$\begingroup$

$$ \begin{array}{l} (0,0,0,0,0,0,0)\\ (1,\frac{3}{4},0,0,0,0,0):\frac{5}{4}u\\ (1,1,\frac{1}{3},0,0,0,0):\frac{5}{12}u\\ (1,1,1,\frac{1}{2},0,0,0):\frac{5}{6}u\\ (1,1,1,1,\frac{2}{3},0,0):\frac{5}{6}u\\ (1,1,1,1,1,\frac{1}{4},0):\frac{5}{12}u\\ (1,1,1,1,1,1,1):\frac{5}{4}u. \end{array} $$

Total distance traveled: $5$ units. This corresponds to the shortest path through six squares arranged in a zigzag fashion: $\sqrt{3^2+4^2}$.

$\endgroup$
4
$\begingroup$

Romeo picks a square face having his starting position as a vertex, and travels along its diagonal. Romeo then picks another square that has his current position as a vertex but does not share a side with the first square, and travels along its diagonal. So far Romeo has travelled $2\sqrt{2}$ side lengths. Now Romeo can find a cube with him and Juliet at opposite vertices, and he will have to travel $\sqrt{5}$ side lengths more to reach Juliet, for a total distance $2\sqrt{2}+\sqrt{5}\approx 5.06$ side lengths.

If ours is the standard unit hypercube $[0,1]^7$ in $7$-space, then Romeo's path is piecewise linear, with vertices $$ \begin{array}{l} (0,0,0,0,0,0,0)\\ (1,1,0,0,0,0,0)\\ (1,1,1,1,0,0,0)\\ (1,1,1,1,1,0,1/2)\\ (1,1,1,1,1,1,1). \end{array} $$

$\endgroup$
  • 1
    $\begingroup$ Why is this optimal? (Is it?) $\endgroup$ – MathET Oct 4 '15 at 18:06
  • 1
    $\begingroup$ My intuition is that unfolding it would yield a zigzag path through 4 faces, but some kind of straighter path passing through small sections of other faces could result in a shorter one $\endgroup$ – MathET Oct 4 '15 at 18:13
  • 1
    $\begingroup$ It's definitely not clear that the path I describe is optimal $\endgroup$ – Julian Rosen Oct 4 '15 at 18:14
4
$\begingroup$

No paths can do better than an analogous to

f''

's diagonal path, for hypercubes of any dimension. Without loss of generality, let's assume the side length equals one.

To make the diagonal path, you select one edge, find an adjacent (touching) edge perpendicular to the previous one, and another one perpendicular to both, and the fourth one perpendicular to the first three, and so on, until an edge is reached which contains the endpoint. Every edge changes one coordinate from zero to one, or one to zero, and since they are all perpendicular, it's a different one each time, so no coordinates are changed back to zero, and we're guaranteed to reach the opposite vertex.

In this way, there are $n$ of them, where $n$ is the number of dimensions. In an isometric map, each edge shares one face with the previous one, and no three edges are on the same face. This is enough to show that they form a zig-zag line, and the optimal path is obtained by linking the two extremities (proven later): Optimal

Moreover, for even $n$ we have a chart with equal number of horizontal and vertical edge intersections (or displacements), while for odd $n$ they differ by $1$.

We also see that any path, in its chart, intercepts the vertical and horizontal edges at least $n$ times, one for each coordinate changed to $1$ (same could be said about those increasing from $0$).

Now take a isometric chart and consider the dimensions, $dx$ and $dy$, of the bounding rectangle. Consider those with $dx+dy$ equal to $n$.

The squared length of a straight line from one corner to another of the rectangle ($dy^2 + dx^2$) is minimum when $dx$ is closest to $dy$, since it is equal to the square of their sum (a constant) minus twice their product (maximum when they're closest):

$$dx^2 + dy^2 = (dx+dy)^2 - 2dxdy$$

An optimal solution is $dx=dy$ if $n$ is even and $dx=dy+1$ otherwise. Our diagonal is the shortest curve bounded by a rectangle*, so it is optimal between every curve bounded by a rectangle of equal $dx+dy$:

Proof without words Since the line must touch the four edges, we can reflect its pieces over the intersections to show that it is greater than the diagonal*

Rectangles with $dx+dy$ greater than $n$ have also greater diagonals, since by decreasing $dx$ or $dy$ we can make a shorter path which has a sum of $n$, and, thus, is greater than or equal to our diagonal.

So our diagonal solution, presented above, is the shortest in any rectangle that has $dx+dy$ no less than $n$. Now it only remains to show that smaller rectangles don't lead to optimal paths.

Every optimal path in a rectangle with semiperimeter ($dx+dy$) smaller than $n$ has to cross at least $n$ edges, moving one unit vertically or horizontally (or both) each time.

However, if this was done monotonically, $dx+dy$ would be greater than or equal to $n$. So it eventually runs in the opposite direction. Since the path is straight inside squares, the change happens at an edge or corner.

But if all turns were in the corners, then the paths after the turning points could be reflected vertically or horizontally in the chart one at a time while preserving length, until there is a monotonic path.

This path would then lie in a rectangle of semiperimeter $n$ or more, so would need to be greater or equal in path length to our diagonal solution. If any turn is at an edge, then the path is also not optimal. So there is no such optimal path.

$\endgroup$
3
$\begingroup$

My guess it's:

$\sqrt{6^2+1^2} = \sqrt{37}$

I believe that you can fold every two-dimensional side in such a way so you get a 6x1 rectangle and then you just take the diagonal. Just like you can get a 2x1 rectangle with a regular 3d cube.

To illustrate this take these as the vertices of our 6 by 1 rectangle (sorry. I'm not familiar with mathematical drawing tools):

ABCDEFG  
HIJKLMN

Then you have these 7-dimensional coordinates for these vertices.

A = (0,0,0,0,0,0,0)  
B = (0,1,0,0,0,0,0)  
C = (0,1,1,0,0,0,0)  
D = (0,1,1,1,0,0,0)  
E = (0,1,1,1,1,0,0)  
F = (0,1,1,1,1,1,0)  
G = (0,1,1,1,1,1,1)  
H = (1,0,0,0,0,0,0)  
I = (1,1,0,0,0,0,0)  
J = (1,1,1,0,0,0,0)  
K = (1,1,1,1,0,0,0)  
L = (1,1,1,1,1,0,0)  
M = (1,1,1,1,1,1,0)  
N = (1,1,1,1,1,1,1) 
$\endgroup$
  • $\begingroup$ I think that, when folded down, the six faces you walk across won't line up in a 6 by 1 rectangle, but will instead zigzag. $\endgroup$ – Mike Earnest Oct 4 '15 at 18:53
  • $\begingroup$ Since my previous answer was a bit too confusing, let me try again. They line up because the edges are parallel to each other, only translated one coordinate at a time. For example, the difference from edge BI to CJ is that the third coordinate is zero in the former and one in the latter. The weirdness is because, in three dimensions, one edge links two faces together, one ingoing and one outgoing. But, in higher dimensions, edges take the role of vertices, and any number of faces may meet, allowing one to go "in straight line" and yet be heading into a new perpendicular direction each time. $\endgroup$ – MathET Oct 6 '15 at 0:05
  • $\begingroup$ @MikeEarnest Here is the unfolding in four dimensions: i.stack.imgur.com/x5vjr.png $\endgroup$ – MathET Oct 6 '15 at 0:34

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.