Path of a “thesterious light” ray that bounces off both edges of equilateral triangle and the path itself

geometry

From the AtCoder Grand Contest (problem and solution (page 10) (PDF)):

Snuke is conducting an optical experiment using mirrors and his new invention, the rifle of Mysterious Light.

Three mirrors of length 'N' are set so that they form an equilateral triangle. Let the vertices of the triangle be $a$, $b$, and $c$.

Inside the triangle, the rifle is placed at the point $p$ on segment $(a,b)$ such that $(a,p)=x$. (The size of the rifle is negligible.)

Now, the rifle is about to fire a ray of Mysterious Light in the direction of $(b,c)$.

The ray of Mysterious Light will travel in a straight line, and will be reflected by mirrors, in the same ways as "ordinary" light. There is one major difference, though: it will be also reflected by its own trajectory as if it is a mirror! When the ray comes back to the rifle, the ray will be absorbed.

The following image shows the ray's trajectory where $N=5$ and $X=2$.

enter image description here

It can be shown that the ray eventually comes back to the rifle and is absorbed, regardless of the values of $N$ and $X$. Find the total length of the ray's trajectory.

For the above case, total length of the trajectory is :
$$2+3+2+2+1+1+1=12\ .$$

I am not able to understand how the author arrived at the formula for the solution.

Best Answer

The first two rays will together with parts of the sides $ab$ and $bc$ create a parallelogram where we start in the lower right corner, and we want to get to the upper left corner. The two sides of the parallelogram are $X$ and $N-X$ (and we have already travelled $X + (N-X) = N$).

Let $f(s, t)$ be the length we have to travel to get from the lower left to the upper right in a parallelogram with horizontal side length $s$ and oblique side length $t$. (The solution uses $a$ and $b$, but those are already names of corners of the triangle, so I changed. Also, the drawing in the solution shows the beam starting in the opposite corner of what would actually happen. So I switched that too.) We have

  • $s = t$: $f(s, t) = s$, as the beam just travels directly along the diagonal into the correct corner.
  • $s<t$: $f(s, t) = 2s + f(s, t-s)$, as the beam travels $s$ units up, hits the left wall, then travels $s$ units back to the right wall, giving us a new parallelogram with side lengths $s$ and $t-s$.
  • $s>t$: $f(s, t) = f(t, s)$, as we can mirror the entire parallelogram about a $60^\circ$ up-left, down-right diagonal (the direction of the initial beam into the parallelogram) and in effect swap the side lengths.

This is the recursion that the solution says will give 300 points. It is correct, but it performs terribly if $N$ is large and $X$ is close to either $1$ or $N$. To get the full 500 points, you need to calculate how many times you can do step 2 before the right argument becomes smaller than the left argument, and do them all in one go using the floor function and modulo operator. This will perform rather well no matter what $X$ and $N$ are. (Worst case: $N$ and $X$ are consecutive Fibonacci numbers, in which case the algorithm takes roughly $\log(N)/\log(\phi)$ steps, where $\phi$ is the golden ratio.)

As for how to find the formula $3(N-\gcd(N, X))$, note that in the given example, the total length of the horizontal beams is $4 = 5-1$, the total length of the up-left, down-right beams is $5-1 = 4$, and the total length of the up-right, down-left beams is $5-1 = 4$. This suggests an idea:

Proposition: If $\gcd(X, N) = 1$, then the total length of beams along any one direction is $N-1$. If $\gcd(X, N) = d\neq 1$, then we can scale down the entire triangle down by a factor of $d$, which would then have beam trajectory $\frac Nd - 1$ along each direction. This shows that the total length of beams along any one direction is $N-d$.

Now, we don't need to prove this full result (although that can be done), as we don't need the length in each direction. We only need the sum of the three directions. But we can use this this proposition to form a corollary. The total trajectory is proposed to be $3N-3\gcd(N, X)$, and since the total trajectory is known to be $N + f(N-X, X)$, this gives rise to:

Corollary: $$f(s, t) = \cases{s & if $s = t$\\2(t + s)-3\gcd(s, t) & otherwise}$$

This corollary is proven by just inserting this candidate for $f$ into the recursion and checking. Since the first and third recursion properties are easily seen to be satisfied, it remains to check the second resursion property, for $s<t$. We divide into cases depending on whether applying the recursion once changes which case of our definition of $f$ we have to apply:

  • $s \neq 2t$: In this case, applying the recursion once won't make the arguments equal. We insert into the recursion and get $$ f(s, t) = 2(t + s) - 3\gcd(s, t) = 2s + \Big[2(s + t-s) - \gcd(s, t-s)\Big] = 2s + f(s, t-s) $$ which is correct.
  • $s = 2t$: In this case, applying the recursion once will put us into the "equal arguments" case. We insert and get $$ f(s, 2s) = 2(s + 2s) - 3\gcd(s, 2s) = 3s = 2s + f(s, s) $$ which is also correct.

So the proposed $f$ fulfills our recursion, and we are done.

Related Question