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:

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

- 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.
- 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) }.
- Compute a Traveling Salesman path that cycles between these seven points. (It doesn’t have to be optimal.)
- Walk along this path, stopping for exactly one hour at each candidate point, and eventually returning and waiting an hour at Point P.
- 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.
- 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.