Divide the plane into an infinite square grid by drawing all the lines $x=m$ and $y=n$ for $m,n \in \mathbb Z$. Next, if a square's upper-right corner has both coordinates even, color it black; otherwise, color it white (in this way, exactly $1/4$ of the squares are black and no two black squares are adjacent). Let $r$ and $s$ be odd integers, and let $(x,y)$ be a point in the interior of any white square such that $rx-sy$ is irrational. Shoot a laser out of this point with slope $r/s$; lasers pass through white squares and reflect off black squares. Prove that the path of this laser will form a closed loop.
Problem
Source: USA TSTST 2013, Problem 3
Tags: analytic geometry, graphing lines, slope, geometric transformation, reflection, floor function
antimonyarsenide
13.08.2013 14:31
I thought this was a really nice problem.
WLOG let $(r,s)=1$ and let the speed of light in the plane be $c=\sqrt{r^2+s^2}$ units/second. Call an event where the laser crosses or reflects off of a horizontal lattice line an $h$ event, and $v$ event for a vertical line. Notice that exactly $r$ $h$ events and $s$ $v$ events occur per second, at regular intervals. The $rx-sy$ condition guarantees no corners are hit, so no two events occur simultaneously. Also, after every $1/r$ seconds, $\{y\}$ either stays the same or becomes $1-\{y\}$, depending on whether the laser was flipped vertically in that time, and similarly for $s,x$.
Color the non-black squares of the grid with colors $1$ (for squares below a black square), $3$ (for squares to the right of a black square), and $2$ (for the rest of the squares). Notice that the laser has 4 possible directions, consisting of 2 possible horizontal and 2 possible vertical directions. An $h$ event either permutes between $2$ and $3$ (so changes $\lfloor \frac{y}{2}\rfloor$) or flips the vertical direction (and so changes $\{y\}$); a $v$ event either permutes between $1$ and $2$ (so changes $\lfloor \frac{x}{2}\rfloor$) or flips the horizontal direction (and so changes $\{x\}$).
Let's first consider the change in square color after the composition of all the events in a second. Any two consecutive $h$ or $v$ events cancel each other out, so we're left with $hvhvhv...$ or $vhvhvh...$. Since there are an odd number of $h$ and $v$ events each, we end up with $(hv)^i$ or $(vh)^i$ for some odd $i$. But since $hv$ is the cyclic permutation $(1 2 3)$, it has order dividing 3, and so square color is periodic in $3$ seconds. Since the resulting square then has the same color as the original, an even number of $h$ and $v$ events each resulted in changing of floor parity of corresponding coordinates, so an odd number resulted in flipping / changing fractional part of corresponding coordinates. Thus the direction is flipped from the original both horizontally and vertically, and the position relative to the square is flipped about the center of the square. Thus this configuration is symmetric with the original about the midpoint of the two positions - which, due to the parities, is the center of a square, and so the grid is symmetric as well. Then in 3 more seconds, by symmetry, the laser will be back at its original position in the same direction as before.
So the laser is periodic ( with period dividing $6$ seconds )
Also, I thought this was more combo than NT
v_Enhance
04.04.2019 16:18
Almost six years later I finally sat down yesterday night and worked most of the details in the solution of #2. So here they all are (but credit for the actual solution goes to antimonyarsenide): Fix the speed of light at $\sqrt{r^2+s^2}$ units per second. We prove periodicity every six seconds. We re-color the white squares as red, blue, or green according as to whether they have a black square directly to the left/right, above/below, or neither, as shown below. Finally, we fix time zero to be a moment just before the laser passes a horizontal (WLOG) lattice line (not necessarily a wall). Shown below is an example for $(r,s) = (3,5)$. The main idea is to keep track of every time the laser passes a lattice line (again, not necessarily a wall). There are four possible types of events: A horizontal $h$ event where the laser switches from red to green (or vice-versa); A horizontal $h$ event where the laser rebounds off a wall, remaining in a blue square, but flips the $x$-component of its velocity; A vertical $v$ event where the laser switches from blue to green (or vice-versa) A vertical $v$ event where the laser rebounds off a wall, remaining in a red square, but flips the $y$-component of its velocity. The first key observation is that: Claim: In the first second, the laser will encounter exactly $r$ horizontal events and $s$ vertical events. In every second after that, the same sequence of $r+s$ events occurs. Proof. Bouncing off a wall doesn't change this as opposed to if the laser had passed through the wall. $\blacksquare$ We let the key-word be the sequence $w$ of $r+s$ letters corresponding to the sequence. For example, the picture denotes an example with keyword $w = hvvhvvhv$; so no matter what, every second, the laser will encounter eight lattice lines, which are horizontal and vertical in that order. Claim: Color is periodic every $3$ seconds. Proof. The free group generated by $h$ and $v$ acts on the set $\{R,G,B\}$ of colors in an obvious way; consider this right action. First we consider the color of the square after each second. Note that with respect to color, each letter is an involution; so as far as color changes are concerned, it's enough to work with the reduced word $w'$ obtained by modding out by $h^2 = 1$ and $v^2 = 1$. (For example, $w' = hv$ in our example.) In general, $w' = (hv)^k$ or $w' = (vh)^k$, for some odd integer $k$ (since $k \equiv r \equiv s \equiv 1 \pmod 2$). Now we see that the action of $hv$ on the set of colors is $\text{red} \mapsto \text{blue} \mapsto \text{green} \mapsto \text{red}$, and similarly for $vh$ (being the inverse). This implies that the color is periodic every three seconds. $\blacksquare$ Now in a 3-second period, consider the $3r$ horizontal events and $3s$ vertical events (both are odd). In order for the color to remain the same (as the only color changes are $R \leftrightarrow G$ for $h$ and $B \leftrightarrow G$ for $v$) there must have been an even number of color swaps for each orientation. Therefore there was an odd number of wall collisions of each orientation. So, the laser is pointing in the opposite direction at the end of 3 seconds. Finally, let $x_t$ be the fractional part of the $x$ coordinate after $t$ seconds (the $y$-coordinate is always zero by our setup at these moments). Note that \[ x_{t+1} = \begin{cases} x_t & \text{even number of vertical wall collisions} \\ 1 - x_t & \text{odd numbers of vertical wall collisions} \end{cases} \]Since over the there seconds there were an odd number of vertical collisions; it follows $x_3 = 1 - x_0$. Thus at the end of three seconds, the laser is in a symmetric position from the start; and in $6$ seconds it will form a closed loop.
Attachments:
pandadude
13.07.2020 18:41
Here is a nice one liner If $r>s$, then we can reduce from $r,s$ to $r-2s,s$(Note that they are still odd non-0 integers) This is because everytime the y coordinate increases by 1, reducing r to r-2s basically shifts x coordinate by 2 which is ok(even with bouncing) Thus, we can no longer reduce when $r=s$ which is very easy to verify. Or $r=2s$ or $s=2r$ which are both impossible. Fun Note: r=1,s=2 is not periodic
CANBANKAN
23.05.2021 04:06
The key idea is to reduce this to a 2x2 grid by noting the complement position is always reachable. We use induction on $|x|+|y|$, with the base case $|x|=|y|=1$ being immediate. Suppose the light travels one horizontal unit per minute. I claim if $(r-2s,s)$ gets me to a complement position (from $(0,t)$ to $(1, 1-t)$ when $x,y$ are taken mod 2) then so will $x,y$. To prove this, notice at the first point, $y$ mod 2 are the same, and we can easily verify the two piecewise functions for $(r-2s,s), (r,s)$ that maps a point to the next are identical mod $2$. If $|r-2s|<|s|$, then we note we can "pair" the edges of the path in a way such that for any point $p$ touching an edge of a black square and its complement point $q$, $p\rightarrow q$ passes one edge from each pair. Recall the paths are "congruent" mod 2 after each minute, which completes the induction.
Leo.Euler
25.12.2023 02:46
Nice problem! The entire idea of this problem (at least for the purpose of this solution) is to prove that it is equivalent to solving the problem for a single $2 \times 2$ sub-grid, whence the job is workable by hand. Case 1: $\color{blue} r \not\in \{s/2, s, 2s\}$. Consider the linear transform $(r, s) \mapsto (r-2s, s)$, which is preserved modulo $2$. It is easy to see that the positions obtained under $(r-2s, s)$ are negated modulo $2$. Thus it suffices to prove the result inside a $2 \times 2$ grid. This result is obvious in this case. Case 2: $\color{blue} r \in \{s/2, s, 2s\}$. $r=2s$ and $s=s/2$ are absurd as $r$ and $s$ are odd, and $r=s$ is trivial as the slopes are $\pm 1$. We are done.
Yue-Zhang_3906
04.04.2024 19:59
In fact, by inducting on $(r,s)$ as $(r,s-2r)$ or $(r-2s,s)$, we can easily get that the length of the loop is $6\sqrt{r^2+s^2}$
YaoAOPS
21.10.2024 08:57
Another funny hurr durr induct down solution but here's the motivation I had. I think N3bula and sixoneeight were also there, thanks to the former specifically. Scale vertically by $s$ and horizontally by $r$. This has the result of making the slope $1$ and turning out $1 \times 1$ squares into those with width $r$ and height $s$. We can also WLOG that the laser hits the midpoint of each $1 \times 1$ without affecting its path other than by $O(1)$. We now induct on $(r, s)$. WLOG suppose $r > s$. Call the $r \times s$ rectangles with a rectangle above and below it the sandwiched squares, which individually form sandwiches. Call all other not sandwich squares nonsandwiched. We give our laser a counter which counts its displacement. We show this counter has looping behavior (as we will later induct down instead modifying our counter.) For clarity we show what happens going from $(r, s)$ to $(r, s - 2r)$ first for $s > 2r$. Take our sandwiched squares and a column of size $2s$ in them. Since no matter how our laser enters the sandwhich, its $y$ position at the start and end of the column are the same at the end of the column, we replace it with a verical toll booth line which adds a horizontal $2s$ when passed by laser in its horizontal direction. We can delete this column in all sandwiches. Likewise, for the nonsandwiched squares, we delete a $2s$ column and create a vertical toll booth adding $2s$ in both the horizontal and vertical direction. When $s < 2r$, the process is a bit more complicated, but it is equivalent to add our toll booths and replace our $s$ sandwiches / nonsandwiches with $2r - s$ sandwiches / nonsandwiches, and then invert the horizontal direction of the entire laser. We can then flip the entire grid horizontally. This induction holds regardless of the preexisting toll booths; just keep toll booths after deleting / replacing $2s$ columns. This means that in total, we have inducted down $(r, s) \mapsto (r, |s - 2r|)$. Since $r \ne 2s$ never holds, we eventually get down to $(r, s) = (1, 1)$, where all paths are a diamond. This diamond passes each toll booth twice with opposite slopes, so our toll booths have a net effect on every loop. As such, the original path also loops.