Paratroopers Riddler

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.

Advertisements
Posted in Uncategorized | Leave a comment

Frax!

Way back in 2010, I decided it was about time for me to learn how to write an iPhone app. The newest device was the iPhone 3gs, running iOS 3.0. I needed an idea, a seed to build a project around. Since childhood I had been fascinated by fractals, using the computer to draw mathematical / geometric images, and it occurred to me that while zooming into a fractal, one could use the device itself to steer, by tilting. Thus, “FraxFlyer” was born.

An early demo was shown to Benoit Mandelbrot himself at the TED 2010 conference, which provided further inspiration to develop the project. Countless revisions later, now in collaboration with interface and content designer Kai (Big Kai, for those who know) and  fellow fractal enthusiast and web magician Tom Beddard, we are on the brink of shipping our first-ever iPhone/iPad app, Frax!

I’ll be posting updates as we go about tidbits from the project, tech details, anecdotes, math nuggets, and the like. Setting up now to go to Apple’s WWDC, suitcase full of T-shirts and postcards. The first long phase is over, and the second, much more exciting phase is about to begin!

Posted in fractals | 1 Comment

How long can you hold your breath?

A new personal best: 150 meter swim on a single breath of air!

Posted in freediving | 1 Comment