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.
Answer
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 $\sqrt{5^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 $\sqrt{19^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 $\sqrt{x^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 $\sqrt{5^2 + 1^2 + 1^2} = \sqrt{27} = 3\sqrt{3}$.
Here is the solution for $N = 2008$:
To see where the three coordinates will roughly be we can estimate $\frac{2008 + 3}{3} = 670\frac{1}{3}$. 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 $\sqrt{671^2 + 673^2 + 667^2} = \sqrt{1348059} \approx 1161.059$.
Answer to comment:
Solution for $N = 6$:
The coordinates will be $\frac{6 + 3}{3} = 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 $\sqrt{1^2 + 3^2 + 5^2} = \sqrt{35} \approx 5.916$ while Brandon_J's approach gives $\sqrt{1^2 + 1^2 + 7^2} = \sqrt{51} \approx 7.141$.
In 3 dimensions the beam path looks like the following (in the extended and real space, respectively):
No comments:
Post a Comment