# 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!*

*My sincerest thanks go to Emily Riehl for today's episode and blog post!*

## The Answer (SPOILER ALERT)...

**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.**

*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.

*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").

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!**

*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.

*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)$.)

*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.)

*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.

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.

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.

*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.

*new*coordinate plane - one where the original assassin lies at the origin, like this:

*Where exactly*? How about the midpoint! It's the easiest thing we can try. Plus, we can write down exact coordinates for the agents!

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!**

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})$.

**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$).

*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

*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.

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!*