In Randall Munroe's book *What If?*, the "Lost Immortals" question asks:

If two immortal people were placed on opposite sides of an uninhabited Earthlike planet, how long would it take them to find each other?

After an entertaining discussion in Munroe's usual inimitable style, he concludes with the following suggestion:

If you have no information, walk at random, leaving a trail of stone markers, each one pointing to the next. For every day that you walk, rest for three. Periodically mark the date alongside the cairn. It doesn't matter how you do this, as long as it's consistent. You could chisel the number of days into a rock, or lay out rocks to plot the number.

If you come across a trail that's newer than any you've seen before, start following it as fast as you can. If you lose the trail and can't recover it, resume leaving your own trail.

I find this algorithm very intriguing and I can almost—but not quite—recall seeing it before. Has this problem been studied before? In any case, my question is, can Munroe's algorithm be improved?

It may be helpful to lay down some ground rules. Munroe considers planets with terrain (oceans, deserts, coastlines, etc.) but for simplicity let's assume a uniform sphere and an unlimited ability to leave a trail behind. Let's also assume that there are no pre-existing markers on the sphere that allow the players to pre-arrange something like, "Let's meet at the North Pole." Although the original question seems to specify that the players are placed at antipodes, it seems to make more sense for their starting positions to be random. Both people have some maximum speed of travel but can choose to move more slowly than that. Finally, I'm not sure whether it makes a difference if the players are allowed to leave arbitrary messages along the trail for the other player to read; if this possibility complicates the problem too much, I'd be willing to simplify by declaring success as soon as one player intersects the other's trail.

9more comments