From this week’s FiveThirtyEight.com Riddler column, slightly reworded for clarity:

“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. (Two out of three is not good enough; all three must be at the same point in order to see each other.)

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 any of the paratroopers, so a strategy like “let’s agree that A stands still and B and C walk to him” will not work. The paratroopers do not know which of the three points corresponds to their own location.)

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

—

Additional assumptions:

1. The paratroopers have perfect dead-reckoning ability to know where they are at any time (relative to their initial position) and to navigate to any point.
2. They have some sort of watch/stopwatch that tells accurate relative time.

Solution:

Each paratrooper is preassigned a distinct prime number. (E.g. { 2, 3, 5 } for the three paratroopers.) They each use their tool as soon as they wake up, which shows each of them three points, though it may not be the same set of three points for each paratrooper.

Define the starting point of the last paratrooper to wake up as point Z. Note that this point will be shown by the tools of all three paratroopers.

So each paratrooper can independently perform the following steps:

1. Upon waking, immediately use the tool to obtain points A, B, C, one of which is this paratrooper’s initial location P, and one of which (possibly also P) is point Z.
2. Compute seven candidate locations for Point Z relative to Point P: { P, P + (A – B), P + (B – A), P + (A – C), P + (C – A), P + (B – C), P + (C – B) }.
3. Compute a Traveling Salesman path that cycles between these seven points. (It doesn’t have to be optimal.)
4. Walk along this path, stopping for exactly one hour at each candidate point, and eventually returning and waiting an hour at Point P.
5. Wait additional time at point P until the total elapsed time for the cycle is of the form [assigned prime]^k hours for some integer k. For instance, the paratrooper assigned the prime 5 might wait til their total cycle time is 25, 125, or 625 hours.
6. Start the cycle again, and keep repeating steps 4 and 5.

Using this scheme, each paratrooper is guaranteed to visit Point Z for at least one hour, on a regular interval of [assigned prime]^k hours. Since the cycle times for the three paratroopers are relatively prime, eventually all three cycles will coincide and the paratroopers will find themselves at Point Z at the same time.

Note that this solution generalizes trivially to N paratroopers, where each computes (1 + N(N-1)) candidate points for Z, and walks their corresponding TS cycles, each with relatively prime periods. Eventually they will all coincide at point Z simultaneously.

An alternate interpretation of the puzzle is that the paratroopers DO know which dot represents themselves, but do NOT have timepieces, and also do NOT have a common idea of true North. (In other words, the tool shows the direction and distance of the other paratroopers, but there is no sense of absolute north-south.) With these assumptions, the trivial solution of e.g. “head to the northwest corner of the axis-aligned bounding box” doesn’t work, and neither does the timed-cycle approach (because if the three cycle periods are not relatively prime, they could perpetually miss each other. Mathematically, for any finite amount of time, there is a nonzero probability that they won’t find each other in that time.)

For three paratroopers, the solution then becomes to find the “Fermat Point” of the three dots, and head there. (The Fermat Point is the single point at which lines drawn to the three dots are mutually off by exactly 60°/120° from each other, and is invariant to the distances of the three dots from the Fermat Point.)

For more than three paratroopers, it gets more complicated. My intuition is that the case of N paratroopers can be approached as follows:

1: Compute the Fermat Point of every triple of dots.

2: If no two Fermat Points coincide (100% probability for the initial random arrangement), choose the most compact one; i.e. the one with the smallest sum of distances from the point to its three dots. If two or more Fermat Points do coincide, choose the ones that coincide. (The chance that multiple Fermat Points coincide at distinct locations, e.g. two at point A and two at point B, is probabilistically zero.) Walk to one of the lines corresponding to the chosen Fermat Point, being careful to stay further away than its corresponding dot (and also being sure not to incidentally create a second smaller Fermat Point with two other paratroopers along the way*) then follow the line inward to the center.

*Herein lies the tricky part. I’m not sure exactly how to ensure this in the general case. For four paratroopers it’s straightforward: the “odd man out” just walks directly away from the center target far enough that he can’t create a more compact target at that radius, then walks circumferentially until reaching one of the Fermat lines, then walks inward to the target. I believe this exact approach also works in the case of five paratroopers, but can fail for six or more.