The Assassin Puzzle

[MUSIC PLAYING] Imagine you have a square shaped room, and inside there is an assassin and a target.

And suppose that any shot that the assassin takes can ricochet off the walls of the room just like a ball on a billiard table.

Is it possible to position a finite number of security guards inside the square so that they block every possible shot from the assassin to the target?

Let's walk through this puzzle a little more precisely.

First, instead of thinking of a physical room with actual people inside, I really want you to think of a square in the xy plane.

Pick any two points in the square.

And let's call one of those points A for Assassin and the other point T for Target.

Now, a shot from the assassin is really just a ray emanating out of the point A, which can, like a ball on a billiard table, bounce back and forth between the size of the square.

But, unlike an actual game of pool, let's assume the trajectory has constant speed, and that it can bounce back and forth for forever.

We'll also assume that the law of reflection holds.

In other words, the angle of incidence and the angle of reflection are always equal.

And if the trajectory ends up in one of the four vertices, then we'll just say it stops.

That's the end of it.

Now, if one of these billiard trajectories intersects with the point T, then that means the assassin has hit the target.

Of course, an obvious hit is just a straight line shot from a 2T.

But don't forget, the assassin can also aim away from the target and still hit it.

Like this.

So the puzzle is, can you block all possible hits?

But what do I mean by block?

If we can place another point in the square, call it B, so that one of those trajectories from A to T actually passes through B first, then we'll say that the point B has blocked the assassin's shot.

OK. That's the puzzle.

Let's recap.

Start with a square in the xy plane whose sides you can think of as like the size of a billiard table.

Pick any two points in the square.

Call them A and T. Is it possible to place a finite number of points in the square so that they will block any possible shot from A to T?

What do you think?

I won't reveal the solution just yet.

I'm going to leave it as a challenge.

However, in the rest of the episode I will tell you about some mathematics that could help you arrive at a solution.

By the way, this puzzle is sometimes called the secure polygon problem, because you can ask this same question for other polygons, not just squares.

It's closely related to the illumination problem that was featured on Numberphile a while ago.

They're both examples of billiard problems, which fall under the mathematical study of dynamical systems.

In fact, here's a little backstory that I think you'll enjoy.

On August 13, 2014, the late Maryam Mirzakhani became the first woman and the first Iranian to win the Fields Medal.

Later in that same year, she gave a talk at Harvard University in which she described her research.

In fact, it's right here on YouTube.

If you pause me and go watch this video, then you can listen to an explanation of the secure polygon problem around 25 minutes and 50 seconds in.

Now, as it turns out, Emily Riehl, a category theorist and professor of mathematics at Johns Hopkins University, was in the audience during Maryam's talk.

She thought about the puzzle and came up with a wonderful solution.

And in the next few minutes, I'll present a couple of mathematical ideas that we'll need to understand that particular solution.

At first they may not seem related to the puzzle at all.

But finding the connection is all part of the fun.

OK. What are those ideas?

We'll start with the torus.

In particular, I want to talk about the flat torus.

Both Gabe and I have talked about this in previous episodes.

In fact, now's a great time, if you haven't already, to go watch Gabe's episode, "Telling Time On a Torus."

There he showed how a torus can be viewed as a quotient space, obtained by identifying opposite sides of a square.

For the sake of illustration, I'm going to use green and blue to denote that these two sides are identified, and these two sides are identified.

So if we have a path going this way on a torus, once it reaches the right edge, it will reappear at that same spot, but coming through on the left edge.

And similarly when the path moves between top and bottom edges.

But all that's been covered in a previous episode.

Now, I want to expand on that idea just a little by sharing with you a common technique that mathematicians use.

Namely, if you want to understand a path on a torus, like this one, well, it can be tricky.

Even though it's just one path, we have to chop it up into six smaller pieces, and then remember to keep track of which ends are glued together.

And that's fine, but it can get messy.

So to make things easier, we'd like to represent that path as one single line.

How so?

By tiling the plane with square tori.

We've actually done this before in a previous episode, "The Geometry of the Card Game SET."

But let's recap again.

How can we see that a path on the tours is really a straight line in the plane?

Start at the beginning of the path.

As it moves upwards, you can imagine it re-entering the bottom edge of an identical copy of a flat torus on top.

Then, as the path continues towards the right edge, it'll pass through the left edge of another identical copy of the torus, and so on.

Keep doing this until the path ends, and you end up with a straight line in the plane.

So this path on the torus is exactly the same as this line segment in the xy plane, because we can think of the plane as a tiling of infinitely many flat tori.

And let me re-emphasize.

Each of these squares is an identical copy of the original one.

That means, for example, that this point is the same as, or equivalent to, this point, which is the same as this point, which is the same as this point, and all of these other points.

And, for the sake of simplicity, if we assume that our original square is just a one by one tile, then each of these points are separated by exactly one unit in the x direction, and one unit in the y direction.

So if this point has coordinates A, B, then this point is A plus 1, B, this point is A, B minus 1, this point is A plus 2, B plus 3, and so on.

The collection of dots that you get is called a lattice.

And you might find that using one or more lattices may be helpful when trying to solve the puzzle.

Anyways, the upshot is that any path on a torus corresponds to a line in the plane.

And any point on the torus gives rise to a lattice in the plane.

So let's think back to the puzzle.

Is the square billiard table actually a flat torus?

Well, no.

It's not.

Suppose if the assassin is here.

If this trajectory moves up towards the top edge, then it does not re-enter through the bottom.

Instead, it reflects back.

So unlike the opposite sides of a square torus, which are identified, the sides of our square billiard table are all different.

No two of them are identified.

All right.

So the square billiard table is not a flat torus.

But can you use one or more of them to make a torus?

And if so, can you solve the puzzle by using the fact that paths on a torus correspond to lines in a plane, and points on a torus give rise to lattices?

Here's the puzzle again.

Is it possible to block any shot from the assassin to the target, two arbitrary but fixed points in the square, using only a finite number of carefully plotted points?

And if it is possible, then, and this is really the key, what is that finite number?

Lots to think about.

I'll let you work out a solution.

Feel free to discuss in the comments.

And after you've thought long and hard about the answer, you can find Doctor Emily Riehl's solution in a link in the description below.

There I've tied up a full solution to this secure polygon problem using the ideas we've discussed in today's episode.

So enjoy the mathematics.

And see you soon.