mjhjmtu

Here's a seemingly interesting puzzle that i currently can't solve. Any ideas are highly appreciated. I was told that it's a middle school level problem but it's definitely not the simple one. At least for me :)

There's a unit cube and from one of its vertices we emit a ray of light. The cube's faces are mirrors and the light reflects from the inner part of the face but not from edges. It is known that the ray reflected $N > 0$ times before entering the opposite vertex of a cube. What is the least possible distance the ray has traveled?

To be precise let's add a coordinate system so that cube's vertices have coordinates $(0, 0, 0)$, $(0, 0, 1), dots, (1, 1, 1)$. Then the ray starts at vertex $(0, 0, 0)$ and after $N$ reflections finishes at vertex $(1, 1, 1)$. It never touched the edge of the cube between its starting and ending points.

To be even more precise i've seen this problem with two particular values of $N$: $N = 4$ and $N = 2008$. Certainly i'd like to know the solution for general case but either of these two particular cases are welcome.

I would like to start with one dimension less: Instead of a cube we look at a square and the beam has to go from one corner to the opposite one. To find the shortest path with $N$ reflections easier

we can imagine what an observer inside the square sees.

Instead of seeing the $N = 4$ case like this:
(green = starting point, red = target point)

we imagine that the mirrors just extend the space. Then the simple square is mirrored over and over again and forms a grid:


In this grid the beam can just travel straight to one of the reflections of the target point, thereby crossing the lines $4$ times, which corresponds to the 4 reflections. It covers a path length of $sqrt5^2 + 1^2$.

This can easily be extended to longer paths.

Here for example is one way to undergo $28$ reflections with a path length of $sqrt19^2 + 11^2$.

But not all sorts of paths are doable in this way.

One restriction is that you are not allowed to hit the corners. So one illegal path would be:


To avoid this one needs to make sure that the lengths travelled in one dimension is prime relative to the length travelled in the other dimension. For example, to undergo $N = 6$ reflections the beam travels $x$ units horizontally and $y$ units vertically, such that $(x - 1) + (y - 1) = N$ and $x$ and $y$ are relative prime. This works for $(x = 5, y = 3)$, but not for $(x = 4, y = 4)$ or $(x = 6, y = 2)$.

Another constraint is that there are only solutions with even $N$. This can be seen from the fact that all the target point's reflections lie on odd cordinates. To reach these, both $x$ and $y$ must be odd, hence the number of reflections $(x - 1) + (y - 1)$ must be even.

Minimizing the path length works in the following way:

The general path travelled is $sqrtx^2 + y^2$. With $x + y$ being fixed (to $N + 2$) the length is minimal for $x = y$. Unfortunately this is never possible. Firstly, $x$ and $y$ must be integers. And secondly they wouldn't be prime if they are the same. So the general strategy is to find two relative primes for $x$ and $y$ that are as close together as possible.

How to extend this to 3 dimensions:

In 3 dimensions it is not much more complicated. The condition that $N$ needs to be even remains, because all 3 coordinates $x$, $y$ and $z$ must be odd, hence $N = (x - 1) + (y - 1) + (z - 1)$ is even. To avoid hitting any edges of the three-dimensional grid $x$, $y$ and $z$ need to be prime relative to each other.

Here is the solution for $N = 4$:

The only way to find 3 odd coordinates which are relatively prime and sum up to $N + 3 = 7$ is $(5, 1, 1)$ (or permutations hereof). This gives a path length of $sqrt5^2 + 1^2 + 1^2 = sqrt27 = 3sqrt3$.

Here is the solution for $N = 2008$:

To see where the three coordinates will roughly be we can estimate $frac2008 + 33 = 670frac13$. Picking $x = 671$ first, which has the prime factors $11$ and $61$ leaves $1340$ for the other two coordinates. They can't both be $670$, so they need to differ by at least $2$. But then one of them would be $671$, which is already taken. They also can't differ by $4$, because then they would share the prime factor $2$. But they can be $673$ and $667$. $673$ is a prime number and $667 = 23 cdot 29$, so it doesn't share a factor with the other coodinates.

So the path length of the beam is $sqrt671^2 + 673^2 + 667^2 = sqrt1348059 approx 1161.059$.

The coordinates will be $frac6 + 33 = 3$ on average. To make them relative primes, we can choose $(1, 3, 5)$. This is different to Brandon_J's answer, whose method suggests $(1, 1, 7)$ for this particular $N$. The length of this answer is $sqrt1^2 + 3^2 + 5^2 = sqrt35 approx 5.916$ while Brandon_J's approach gives $sqrt1^2 + 1^2 + 7^2 = sqrt51 approx 7.141$.

In 3 dimensions the beam path looks like the following (in the extended and real space, respectively):

Note: I'm finding the most direct way to do this for N > 0. The most direct way happens to occur when

N = 2, just to let you know. More on that at the end. Also, I think I have an idea for the general case of N as well. See the end.

Solution:

We can simplify this problem in the following way:

Looking at the picture below, we can see that light needs to travel from A to C' (blue dashed line) BUT not in a direct line. What appears to be the most direct solution (to me) comes from looking ONLY at the plane containing points A, C, A', and C'. This plane would intersect the cube along the dashed line.

We can then draw a rectangle

ACC'D' of width sqrt(2) and height 1 where the light can reflect off of the top and bottom of the rectangle on its way from A to C. The fastest way to do this is to reflect once off of the bottom side (one-third of the way between A' and C')and once off of the top side (two-thirds of the way between A and C).

Consequently, the

three rays of light are identical, and are also the hypotenuses of the right triangle with legs length 1 and sqrt(2)/3. Enter Pythagorean theorem: 1^2 plus (sqrt(2)/3)^2 equals 1 + 2/9 = 11/9 = c^2. Solving for c, we find that each ray is sqrt(11/9), or sqrt(11)/3. There are three rays, so...

the answer is...

The square root of eleven.

More thoughts on "N" (Now defunct because of deep's answer):

N cannot be 1. My reasoning for this is that for the first beam of light, it cannot reflect off of three of the available planes in the cube, since the intersect the point at which the light comes from. Light travels in a straight line, so it can't curve around and meet itself on those three planes. It also can't reflect off of the other three planes because then it can't land on the target point, C' for the same reason.

Broad Solution:

Based on my previous solution, the broad solution is $sqrt(N+1)^2+2$ but ONLY WHEN N is EVEN. As @deep thought points out in his answer, there is no solution for an odd N.

This expands my comment on @BrandonJ's answer. That answer is correct, when

$N=2$, the distance is $sqrt11$, and generally when $N$ is even, the distance is $sqrt(N+1)^2+2$

To complete the remaining cases,

when $N$ is odd, we can prove there is no solution.

Like so:

For the light ray leaving $(0,0,0)$, consider whether the three co-ordinates are increasing, decreasing, or constant, as the light ray advances.

It is clear that, at the start, none of them can be decreasing. Also, OP explicitly excludes reflecting off edges. If any co-ordinate was constant at the start, it would be confined to one face of the cube, and hit an edge. So they must all be increasing. And, the same thing is true for the light ray entering $(1,1,1)$. It is clear that, at the end, they are all increasing.

Now consider what happens when a light ray reflects. For example, suppose the third co-ordinate is 0 on top and 1 on the bottom. Suppose that the light ray reflects off the bottom surface. Therefore, the third co-ordinate changed from increasing to decreasing, but the first and second co-ordinates will have the same sign as before. And a similar thing will be true for the other five surfaces. So:

• All three co-ordinates are either increasing or decreasing

• At the start, all three co-ordinates are increasing

• At the end, all three co-ordinates are increasing

• At each reflection, one of the co-ordinates changes from increasing to decreasing, or from decreasing to increasing, while the other two keep the same sign.

So a 'parity' argument works now: after an even number (including zero) reflections, an even number (zero or two) of the co-ordinates are decreasing, and after an odd number of reflections, an odd number (one or three) of them are decreasing. So we can only end after an even number of reflections.

That would be approximately 3.3 units.
To hit the opposite corner of the cube, the least possible distance would be traversed after two reflections on the walls of the rectangle formed by diagonals of opposite faces of the original cube and opposing sides of the original cube. The longer side of this rectangle would be sqrt(2). The first reflection would happen at 1/3 the distance of the longer side and the next reflection at 2/3 distance on the opposite side and then the beam would hit the opposite corner. The beam would then have traversed 3 times sqrt(1+2/9) or 3*sqrt(11/9) or sqrt(11) or ~3.3.

I do realize Brandon submitted the answer (with a better explanation at that) before me (+1 for that). Just leaving this answer as I was working on it in parallel on similar lines.