Symmetry is hard - the plight of the paratroopers

Posted February 25, 2018

This week's puzzle from FiveThirtyEight's Riddler was about paratroopers crash-landed in the desert, and came from Keith Wynroe. Here's the puzzle:

During their descent, three paratroopers were blown off course and crash-landed in the desert - an infinite, uniform, two-dimensional plane. They come to at a random time after the crash and must find a way to meet up. The only tool they each have is a device that displays a snapshot of the positions (but not the velocities) of all three of them in the desert. They can each use this tool only once. To make things more annoying, they’ve all been nearly blinded by sandstorms and won’t be able to physically see the others until they’ve all arrived at the same point.

Can you devise a strategy that they can agree upon beforehand and that will guarantee they will meet up? (Note that the snapshot does not indicate the specific identities of the other paratroopers, so a strategy like "let's agree that A stands still and B and C walk to him" will not work.)

Extra credit: Is there a strategy that would work for any number of paratroopers?

My interpretation of the rules is that the paratroopers are so disoriented that even when a pair of them run into each other, they don't know the other is there; they won't know they've found each other until all three of them are in the same place. Also, the random time that the paratroopers comes to might be different for each paratrooper; they don't know who woke up before, after or the same time as them. We'll start off with some unsatisfactory answers, and wind our way towards a better answer.

Some early attempts

First, some solutions that might technically work, but which I think are morally shouldn't quite count for reasons that we will see. The paratroopers land at three unknown points in the desert:

Suppose that the two-dimensional plane is a coordinate plane (so that each point is described by a pair of coordinates \((x, y)\)). Then the paratroopers can agree ahead of time to meet up at the origin, \((0, 0)\).

This solves the problem as long as the plane is labeled with axes, but the problem says that the desert is an "infinite, uniform, two-dimensional plane," which suggests that there is no origin or other special point that they can all identify.

For another attempt, let's suppose the GPS-like device labels the map with a compass rose. The paratroopers can agree ahead of time that the northern-most person will stay in place, and the other two paratroopers will walk to all meet up at that location. If there's a tie for the person who is northernmost, then break the tie with whomever is westernmost.

Again, this solves the problem. Even if the paratroopers wake up at different times, if they all walk in straight lines, then there will be no ambiguity which person is the meeting point. But this only works if the device says which way is north. It's possible that the device gives the location of the other paratroopers without needing to label a direction as north.

Let's try again. We assume that the paratroopers wear watches. When the first paratrooper comes to, that paratrooper just sits around until 8 am (waiting until the next day if necessary), and then uses the device. After looking at the map, if they are already in the same spot as another paratrooper, they stay put. Otherwise, they walk to the location of one of the other paratroopers, making sure to arrive within 8 hours. The other two paratroopers do the same thing, except with 8 am replaced with 4 pm or midnight, respectively. That way, no two paratroopers check their devices at the same time, and no paratrooper is in transit while another checks their device.

When the first paratrooper checks their device, they walk to another paratrooper, so that two paratroopers end up in the same spot.

If the first paratrooper's new partner wakes up and checks the device, they realize they have company, and stay put.

When the yet-lonely paratrooper checks the device, they walk to join the first two paratroopers.

This strategy works, but relies on the paratroopers not checking the device or moving at the same time. That, in turn, requires the paratroopers to wear watches (and those watches need to be calibrated to each other). We're also assuming that the paratroopers can walk arbitrary distances within eight hours. But perhaps the paratroopers don't have watches (or perhaps they land more than an eight hour walk apart). We're also allowing the different paratroopers to follow different instruction sets: one paratrooper only checks the device at 8 am, while another is assigned to 4 pm.

What all the above solutions have in common is that they assume a lack of symmetry in once sense or another, and use that lack of symmetry to make the problem easier. The problem is easier if we assume that the coordinate plane has an origin we can identify. It's harder if we assume all points look alike. The problem is easier if we assume that the device reveals which way is north. It's harder if every direction is like every other. The problem is easier if we have a watch and can tell time. It's harder if every moment in time is indistinguishable from every other.

The general principle is that the more symmetry we introduce into the problem, the harder the problem becomes. This is true not only of this problem with the paratroopers, but with many other problems in math as well. Going forward, we'll assume as much symmetry as we can and see if we can try to solve the problem anyway. We'll assume that the plane doesn't come with a coordinate axis nor a direction labeled north. We'll assume that the paratroopers don't wear watches. We'll even try to have all three paratroopers follow the same set of instructions. We'll see if we can beat symmetry.

Can we beat symmetry? An attempt using circumcircles

The paratroopers could decide to pick a meeting point ahead of time, and then when they each come to, they head straight for the meeting point. Without a frame of reference like the coordinate axes, they can't choose an exact meeting point ahead of time, but instead they can agree on a method for a calculating the meeting point.

For instance, they can agree that they will meet at the centroid of the triangle formed by the three of them. If you cut the triangle out of a piece of cardboard, it's the point where you can balance the triangle on your finger. You can construct the centroid by drawing the three medians of the triangle (a median is a line segment from a vertex of the triangle to the midpoint of the opposite side). The three medians all intersect in one point, the centroid.

As the paratroopers come to, they use the device, calculate the centroid, and start walking straight toward it.

But wait, what if a paratrooper comes to after one or two of the other paratroopers have already started walking? That paratrooper computes a different location for the centroid based on the updated locations.

So, that paratrooper walks to a different spot, and never meets up with the others.

This is a pretty fundamental problem. As soon as a paratrooper starts walking - no matter which direction they walk - the centroid changes. So meeting at the centroid doesn't work. Let's instead look at a different point. There is a unique circle that passes through any three points in the plane (unless those points are colinear). That circle is called the circumcircle of the three points, and its center is called the circumcenter. The paratroopers could agree to meet at their circumcenter.

But this has the same problem as before. As the paratroopers start moving, their circumcenter does too. A paratrooper who checks the device later will calculate a different circumcenter and go to the wrong point.

The circumcircle seems not be much help here, and the problem is that as the paratroopers move, the circumcircle changes. But there is one thing about the circumcircle that is nicer than the centroid. It may be true that the circumcircle changes if a paratrooper start walking toward the circumcenter. But if the paratroopers instead walk while staying on the original circumcircle, the circumcircle stays the same.

Here's a solution based on this idea. When the paratroopers check the map, they draw in the circumcircle. The circle is partitioned into three arcs, with the paratroopers serving as the endpoints. Erase the longest of the those three arcs. The meeting point is set to be the location of the middle paratrooper of the three, along the portion of the circle that remains.

The middle paratrooper does not need to move, while the two side paratroopers walk to the meeting location not along a straight line, but along the circle.

That way, if another paratrooper uses the device later, the circumcircle is the same. And, since any motion only increases the length of the longest arc, they all agree on which arc to erase (and where to meet).

If the paratroopers happen to all start out on the same line, the strategy still works, but with a slight modification: The meeting point is the location of the middle paratrooper, and the other paratroopers must walk along the line to get there. This is basically the same idea as before if you think of a line as a circle of infinite radius.

This strategy breaks down, however, if there's a tie for which arc is the longest. This can happen if the triangle formed by the three paratroopers is isosceles, or in particular when it is equilateral.

If it's isosceles but not equilateral, we can fix it; we just declare that in the case of a tie, the more counterclockwise of the two tied arcs shall be declared to be bigger, and the rest of the strategy can stay the same.

If, however, the triangle is equilateral, we are in trouble. There's no good way to break the tie, and in particular if two paratroopers check the device at the same time, they may head off for different meeting points as each other. This is another instance where more symmetry makes the problem more difficult. This case has 120-degree rotational symmetry; if you rotate the whole map 120 degrees around the circumcenter, you get the same picture back. So, if one paratrooper thinks that some particular point on the circumcircle should be the meeting point, the next paratrooper over may use the same logic to decide that the meeting point should be a different location 120 degreees away.

The only point on the whole map that all three paratroopers can pick out unambiguously is the circumcenter. But since that's not on the circumcircle, they have no way to get to it without wreaking havoc. So, the strategy potentially fails when the paratroopers start out arranged in an equilateral triangle.

We have found a strategy that almost solves the problem, but once again, we see that the problem is harder in cases where there is more symmetry. An equilateral triangle has mirror symmetry and 120 degree rotational symmetry, and we weren't able to completely solve the problem in that case

An isosceles triangle (that is not equilateral) has mirror symmetry. We were still able to solve the problem in that case, but we actually had to give up some symmetry somewhere else: For non-isosceles triangles, the paratroopers didn't need to know up from down (something that, one imagines, could get confusing in a sandstorm) to carry out the strategy. In the isosceles case, the tie is broken by calling the more-counterclockwise arc "bigger," by which we mean the arc that is more counterclockwise when viewed from above. But to figure this out, the paratroopers do need to know which way is up! Our solution required us to give up this symmetry.

Symmetry has once again spoiled the day in this solution attempt. In the next section, we will finally see a solution that holds up against all attacks by symmetry.

A solution resistant to symmetry: being lazy

Symmetry makes the problem hard, so it would be most interesting to find a solution that works in the most symmetric interpretation of the problem. We now assume that infinite plane is not labeled with coordinates so that every point is like every other, that there is no notion of north so that every direction looks like every other, that there are no clocks so that every moment in time seems like every other, still that the paratroopers are not labeled on the device so that each paratrooper appears the same as the others, and even that the paratroopers cannot tell up from down, so that those two vertical directions are indistinguishable from each other.

For this strategy, the paratroopers agree ahead of time on how to calculate the meeting point: They try to be as lazy as possible, and choose the point that minimizes the total distance walked by all three of them combined.

If the paratroopers are collinear, the optimal meeting point turns out to be the location of the middle paratrooper.

If they form a triangle where the angle at one of the vertices measures 120 degrees or more, the optimal meeting point is that vertex.

And, if they form a triangle where all degree measures are less than 120 degrees, then the optimal meeting point has the property that if you stand there and look outwards, the paratroopers will each be 120 degrees apart in your field of vision.

There are some beautiful short proofs that for any three points there is a unique optimal meeting point, and that point is as described above. I will skip proving this for now.

My favorite way to find this special point is to draw a map on a sturdy piece of cardboard, cut holes where each of the paratroopers is, and put a string through each hole. Below the cardboard, attach an identical weight to each of the three strings. Above the cardboard, tie the three loose ends of string together. Hold the cardboard level, and let the strings go. The knot will settle on the point that shall be their meeting point, with the strings showing the path that each should walk.

What makes this strategy work is that it doesn't matter if a paratrooper uses their device after another paratrooper starts moving. As long as each paratrooper stays on a straight-line path to their meeting place, the optimal meeting location, as calculated above, does not change. This sort of makes sense; if the optimal meeting location were to change when you started moving, it means that you probably have not been moving in a very optimal way. We can formally prove this.

Theorem. Let \(P_1, P_2, P_3\) be the locations of the three paratroopers at some point in time. Let \(O\) be the unique optimal meeting point such that minimizes the sum of the distances \(P_1 O + P_2 O + P_3 O\). Let \(P_1', P_2', P_3'\) be the locations of the paratroopers some time later, after some or all of them have started walking toward \(O\). Then \(O\) is still the unique optimal meeting point based on their new locations.

Proof. Let \(O'\) be any point in the plane that minimizes the distance \(P_1' + P_2' + P_3'\). We will show that \(O' = O\).

We are basically about to show that \(O'\) would have been a good point to have chosen the first time around; by the triangle inequality, \[\begin{align*} P_1 O' + P_2 O' + P_3 O' &\leq (P_1 P_1' + P_1' O') + (P_2 P_2' + P_2' O') + (P_1 P_2' + P_2' O') \\ &= (P_1 P_1' + P_2 P_2' + P_3 P_3') + (P_1' O' + P_2' O' + P_3' O') \\ &\leq (P_1 P_1' + P_2 P_2' + P_3 P_3') + (P_1' O + P_2' O + P_3' O) \\ &= P_1 O + P_2 O + P_3 O. \end{align*}\] For the last equality, we used that \(P_1', P_2', P_3'\) are points on the line segments \(\overline{P_1 O}, \overline{P_2 O}, \overline{P_3 O}\), respectively.

This inequality says that choosing \(O'\) as the meeting point would have been just as good as \(O\) (in terms of total distance walked). But, since \(O\) was the unique point that minimized the total distance walked, this can only happen if \(O = O'\). \(\square\)

This strategy works in many cases even when there are more than three paratroopers. When there are four paratroopers, it works except when the four paratroopers have the misfortune of starting out all colinear.