Is the Square a Secure Polygon?
In this week's episode of PBS Infinite Series, I shared the following puzzle:
Consider a square in the xy-plane, and let A (an "assassin") and T (a "target") be two arbitrary-but-fixed points within the square. Suppose that the square behaves like a billiard table, so that any ray (a.k.a "shot") from the assassin will bounce off the sides of the square, with the angle of incidence equaling the angle of reflection. Puzzle: Is it possible to block any possible shot from A to T by placing a finite number of points in the square?
As I mention in the video, this is one of a number of billiard problems that folks studying dynamical systems have asked. It was mentioned in a 2014 lecture given by Maryam Mirzakhani, which you can watch in the video on the left! Maryam describes the puzzle but leaves the audience to think about the solution. And in that audience was category theorist Emily Riehl, who did indeed think about a solution on and off for a few weeks.
(You can read Emily's reflection on her experience in this AMS tribute to Maryam.)
Fast forward to last fall, when I ran into Emily at a Women in Topology workshop at MSRI. During a bus ride up the hill to the MSRI campus, Emily suggested that the puzzle might be a good fit for Infinite Series. I couldn't agree more! The solution she shared with me is delightfully simple for what seems to be an incredibly complicated puzzle. It's the solution she believes Maryam intended the audience to find, and it's what I want to share with you today! In the video above, I set up some of the mathematics needed to work through the solution, so if you haven't watched it already, now would be a good time. In any case, I'll assume you're comfortable with the notions of flat tori, a tiling of the xy-plane with flat tori, and a lattice in the xy-plane.
Alright, let's get to it!
My sincerest thanks go to Emily Riehl for today's episode and blog post!
The Answer (SPOILER ALERT)...
The answer is YES. It is possible to place a finite number of points in the square that will block any possible shot from $A$ to $T$. Moreover, 16 points will suffice!
The Solution
Step #1: Transfer the problem to the xy-plane.
Billiard trajectories (i.e. zig-zags on a square) can be tricky to analyze, so to make things easier, we want to find a way to replace any biliard trajectory by a line in the plane. (Why? Because zig-zags are hard. Lines are easy!) Now anytime a mathematician mentions the words "square" and "trajectory" and "line" in the same sentence, there's a 99.2% chance that flat torus is involved! So the goal for the first step in the solution is to somehow (we'll see how in a bit) use a flat torus to transfer the puzzle from the billiard table to the $xy$-plane.
To start, I'll pick up where we left off in the video — let's draw the billiard table as a square whose edges are each a different color. This will remind us that unlike a flat torus, none of the sides of this square are identified. I'll also pick two arbitrary-but-fixed points in the square, labeled $A$ (assassin) and $T$ (target). To distinguish the points visually, I've drawn the assassin as a white dot and the target as a black dot.
Now even though this square billiard table is not a flat torus, we can make a flat torus by sticking four of these billiard tables together! How? First notice that the square can be reflected in four different ways (including the "empty reflection").
Square #1 represents the original square (with no reflection), and I've labeled its edges by north, south, east, and west. Square #2 is obtained by reflecting square #1 across a horizontal axis, so that the north and south sides get swapped. Square #3 is obtained by reflecting square #1 across a vertical axis, so that the east and west sides get swapped. We can also perform these two reflections in succession to swap both north/south and east/west. That's square #4. To get a torus, simply assemble these four squares as shown below!
Now we can tile the plane with that torus. (In math lingo one says, "We can pass to the universal cover of the torus.")
In what follows, I'll refer to that yellow square that you see (labeled with 1) as the "original square." We'll think of it as the original billiard table, while the other squares are the copies/reflected copies.
Okay, we’ve transferred our target/assassin problem from a square to the plane. So any trajectory on the billiard table will correspond to a line segment in the plane! For example, the trajectory from the assassin to the target on the left-hand side below IS the line segment on the right-hand side! (Verify this for a good mental check!)
So we've successfully moved the puzzle from a square to the plane. That was the first step.
Step #2: Observe that the problem involves lattices!
Until now I've omitted a detail, but now's a good time to point it out. In the very first graphic above, you see that I plopped two points $A$ and $T$ (white and black) on the original square. Since those points lie on the original square, they must lie on the reflected copies, too!
Therefore they also appear in the tiling of the plane!
While this may look pretty, it'll be more helpful if we focus on the assassin and the target in their respective squares, rather than all jumbled together. I've drawn this below.
For the moment, let's only focus on what's happening with the copies of square #1. We've got a bunch of repeating black and white dots! The technical word for repeating dots is a lattice.
More formally: Given a point $(x,y)\in\mathbb{R}\times \mathbb{R}$, the lattice generated by $(x,y)$ is the set of points $\{(x,y)+(n,m)\;\vert\;n,m\in\mathbb{Z}\}$. In other words, start at $(x,y)$ and move $m$ units left/right and $n$ units up/down, where $m$ and $n$ range over all possible integers. The resulting collection of points is called a lattice, which is really just a translated copy of $\mathbb{Z}\times\mathbb{Z}$. (You can think of $\mathbb{Z}\times\mathbb{Z}$ as the lattice generated by $(0,0)$.)
In the previous graphic, we observed that the target in the original square generates a lattice, which we'll call Lattice #1. In the graphic below, I've done a little rescaling so that the set of black dots really is like $\mathbb{Z}\times\mathbb{Z}$, rather than $2\mathbb{Z}\times2\mathbb{Z}$. (i.e. so that the black dots really are spaced out by a factor of one, rather than a factor of two. This is what I'm referring to in the "small technicality alert" in the graphic below.)
Of course, a similar story holds for the assassin $A$ — it generates its own lattice, though I won't draw it because we won't need it! It'll suffice to consider the original assassin (the assassin in the original square) and not its copies. Also remember — we've only focused on square #1! We actually get more lattices because of the three other squares, and we'll focus on those generated by the target. So in addition to Lattice #1, let's call Lattice #2 the lattice generated by the target in square #2; Lattice #3 the lattice generated by the target in square #3; Lattice #4 the lattice generated by the target in square #4. Here are the pictures.
Woo! That's a lot of dots. At this point, you might wonder why we're not worrying about the lattices generated by the assassin. Why represent the assassin as a single dot rather than as lattices, as we did with the target? The answer lies in the following observation: The original problem consists of two points $A$ and $T$ on a square billiard table, and so when we tile the plane with those cleverly-crafted flat tori,
This is the key! In fact, it bears repeating:
Any shot from the assassin to the target in the original billiard table can be represented by a line segment in the plane that goes from the assassin in the original square to a copy of the target in one of the four lattices.
So to solve the puzzle, let's make the following strategy.
Strategy: To block any shot from the assassin to the target, we need to block any shot that can occur in each of the four lattices.
Let's call this process protecting the lattice. To solve the puzzle, then, we first need to protect Lattice #1, then we need to protect Lattice #2, then we need to protect Lattice #3, and finally we need to protect Lattice #4.
Fortunately, this isn't as complicated as it seems! As we'll see below, once we figure out a way to protect Lattice #1, we'll be able to apply similar arguments to protect the remaining three lattices. In other words, if we can protect Lattice #1 using $k$ "security agents," then we may conclude that a total of $4k$ security agents are needed protect the full plane. That is, it will take a total of $4k$ security agents to block any shot from the assassin to the target! So what is this special integer $k$? Let's find out in the next steps.
Step 3: Protect Lattice #1
Here's a picture of Lattice #1 again. I've plotted the original assassin in the original square, circled below.
.jpg)
To make things easier to visualize, let's introduce a new coordinate plane - one where the original assassin lies at the origin, like this:
.jpg)
I've drawn the new axes in dark blue to emphasize that this really is a new grid! Now suppose that the original target has coordinates $(a,b)$ in this plane. (I realize it looks like $(a,b)=(\frac{1}{2},\frac{1}{2})$, but that's only due to poor artistic planning. The target needn't be in the center of the blue squares!) Then the coordinates of the target in the other three squares nearest the origin are as shown below.
And now we're getting really close! Remember, our goal is to block any shot from the assassin (the origin) to the target (the dots). So naturally, we want block those four closest shots, right? So let’s place a "security agent" — indicated by a red dot and labled with $B_1, B_2, B_3,$ and $B_4$ — in between the assassin and the target in each of the four closest squares. Where exactly? How about the midpoint! It's the easiest thing we can try. Plus, we can write down exact coordinates for the agents!
Moreover, each point $B_1,B_2,B_3,B_4$ generates its OWN lattice! And the idea is that $B_1$ (and its copies), for instance, could potentially block other shots, too — those that come from all angles that might have bounced off the walls several times, but haven’t yet hit the target. I won't draw the pictures for these lattices, but the idea comes in handy soon, so be sure to keep it in mind!
In any case, we've certainly blocked the four closest shots from the assassin to the target. But what about ANY shot? How many more agents do we need? I claim the answer is zero. ZERO! In other words — and this is really amazing — the claim is that $B_1,B_2,B_3,B_4$ will block any shot from the assassin to the target, not just the four closest shots! It only takes FOUR agents to protect Lattice #1!
Observing why this is true is the final step.
Step #4: Make the final observation!
The goal in this step is to show that ANY trajectory from the assassin (origin) to the target (one of the dots) in Lattice #1 must intersect one of the points in the lattice generated by either $B_1$, $B_2$, $B_3$, or $B_4$.
Here's the proof of that claim.
Consider an arbitrary shot from the assassin to the target. On the plane, this corresponds to a straight line segment from the origin to a point of the form $(a+m,b+n)$ for some integers $m$ and $n$. To block this shot, let's place a new point $B$ at the midpoint of that line segment. Thus $B$ has coordinates $(\frac{a+m}{2} , \frac{b+n}{2})$.
.jpg)
Now here's the punchline! Depending on the parity of $m$ and $n$, the point $B$ is REALLY a copy of either $B_1$ or $B_2$ or $B_3$ or $B_4$!! In other words, this new security agent $B$ isn't so new after all! It lies in the lattice generated by one of the four blockers already chosen! Indeed:
For example, $m=1$ and $n=2$ in the illustration above. This puts us in case 4, so that $B=(\frac{a-1}{2},\frac{b+2}{2})$ is a point in the lattice generated by $B_2$. And this agent blocks that particular trajectory that we saw earlier! Indeed, notice that in the middle graphic below, the target is in one of the squares labeled 1, which guarantees it's a point in Lattice #1. Moreover, we can get to that square by starting at the original square, then moving up by two squares labeled 1 (this corresponds to $n=2$) and then moving right by one square labeled 1 (this corresponds to $m=1$).
BINGO! Once we place the first four security agents down, we automatically block any other shot in the first lattice. It takes just four agents to protect Lattice #1! (So that special integer $k$ we were looking for earlier is $k=4$.) And what's great is that the argument we used to protect Lattice #1 works for any lattice! In particular, this means we can protect Lattice #2, Lattice #3, and Lattice #4 using just four agents each! Therefore we need a total of $$4\times 4 = 16$$ agents to secure the square!
Conclusion? The square is a secure polygon!
Food for thought
I didn't draw the lattices generated by the agents, but you might have a bit of fun doing this — see where they lie on the original plane (the one with all the colors) and convince yourself that every shot the assassin takes really is blocked! Also, we showed that 16 points will suffice, but could fewer than 16 work, depending on where the assassin and target are located? (For example, if the target is in the center of the billiard table, then you only get one lattice rather than four.)
You might also wonder about other (regular) polygons. Today we saw that the square is secure. But what about triangles? Pentagons? Hexagons? For which $n$ is an $n$-gon a secure polygon? I'll leave you to ponder the answers.
Until next time!
An interactive demo! (added 7/23/18)
As if this puzzle weren't cool enough, Jeremy Kun of Math ∩ Programming recently made an interactive demo to go along with it! The gray dot represents the assassin, the green dot represents the target, and the 16 red dots are the security agents. If you hover your mouse over the grid, you'll see the trajectory of the assassin's shot. Below is a GIF of the demo. Check out the real thing here!
Notice how the trajectory never reaches the target? EVER. How cool (and totally unintuitive) is that? Even better, this holds no matter where the assassin and target are located. To see this, just refresh your browser window! The assassin and target will randomly change positions, and the guards will adjust accordingly. (You can also click and drag the green dot around. The agents shift position!) And they still block every possible shot, just as we predicted in our proof above.
Thanks so much for coding this, Jeremy!! It's really neat to see the dynamics in action.
If you're interested in Jeremy's code, check out his blog post, Visualizing an Assassin Puzzle!