Maths Olympiad Prep

Library / /4 of 10

Geometry Difficulty 8.8 Shortlist Prove it United States

Divide the plane into an infinite square grid by drawing all the lines x=mx = m and y=ny = n for integers mm and nn. Next, if a square's upper-right corner has both coordinates even, color it black; otherwise, color it white (in this way, exactly 1/41/4 of the squares are black and no two black squares are adjacent). Let rr and ss be odd integers, and let (x,y)(x, y) be a point in the interior of any white square such that rxsyrx - sy is irrational. Shoot a laser out of this point with slope r/sr/s; lasers pass through white squares and reflect off black squares. Prove that the path of this laser will form a closed loop.

Solution

Classify the white squares into 3 groups in the following way: white squares of type A are vertically adjacent to black squares, white squares of type B are diagonally adjacent to black squares, and white squares of type C are horizontally adjacent to black squares. In addition to this, note that at any point in time the laser can be travelling in one of four directions; it can be travelling up and right (UR), up and left (UL), down and right (DR), or down and left (DL). We can therefore, at any time, classify the 'state' of the laser by specifying what type of white square it is in and what direction it is travelling in. This gives us 12 different states, which we will write as the letter type of the square followed by the two letters for the direction (so for example, BDR means in a square of type B and travelling down and right).

The state of our laser changes every single time it hits a horizontal or vertical gridline. Moreover, how it changes is completely determined by the state it was previously in and whether it just hit a horizontal line or a vertical line. Denoting hitting a horizontal gridline as 0 and a vertical gridline as 1, we can therefore draw the below state diagram. Some of these transitions correspond to the laser reflecting off of a black square; these are denoted in the above diagram by putting a bar over the above number. The rest instead involve the laser crossing over into a new unit square. If the transition involves moving leftward into a new square, we write this as +x+x (since the xx value of the square increases by 1); likewise, if the transition involves moving rightward, upward, or downward into a new square, we write this as x,+y-x, +y, or y-y respectively.

Consider a laser travelling along the line segment from (x,y)(x, y) to (x+r,y+s)(x+r, y+s), but this time passing through black squares instead of reflecting through them. Note that whenever this laser hits a horizontal gridline, our original laser hits a horizontal gridline; likewise, whenever this laser hits a vertical gridline, our original laser hits a vertical gridline. Moreover, it is easy to see that when the new laser is at a point (m+a,n+b)(m+a, n+b) inside of its unit square (where m,nm, n are integers and 0a,b<10 \le a, b < 1), then our original laser is at some point of the form (m±a,n±b)(m' \pm a, n' \pm b) (where the choice of signs depends only on the direction of our original laser at the time; in particular, if the original laser is moving up and right, then both are pluses).

Now, this segment hits rr vertical gridlines and ss horizontal gridlines. Note that since rr and ss are both odd, after rr 1s and ss 0s, we will be in either the state BDR, ADL, or CUR (this follows straightforwardly from parity considerations). By symmetry, in either case, after two more repetitions of this (i.e. by considering the segment from (x,y)(x, y) to (x+3r,y+3s)(x + 3r, y + 3s)), we will be in the state ADL. Now, the segment from (x+3r,y+3s)(x + 3r, y + 3s) to (x+6r,y+6s)(x + 6r, y + 6s) takes us from ADL back to AUR, and moreover (again by symmetry) every instance of a transition with ±x\pm x or ±y\pm y when we went from (x,y)(x, y) to (x+3r,y+3s)(x + 3r, y + 3s) now corresponds to an instance of a transition with x\mp x or y\mp y. It follows that all three requirements are satisfied, and thus the laser forms a closed cycle.

Figure 1

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.