42
$\begingroup$

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.

Improve this question
$\endgroup$
14
  • 2
    $\begingroup$ This reminds me of stuff I saw on "stochastic rendezvous problems", see wikipedia.org/wiki/Rendezvous_problem - although the versions I've seen don't allow one to leave markers $\endgroup$
    – Yemon Choi
    Oct 14, 2014 at 15:34
  • 7
    $\begingroup$ If they are allowed to talk before hand, just "follow a geodesic" will give a win. Any two geodesics must intersect. $\endgroup$
    – Steven Gubkin
    Oct 14, 2014 at 15:34
  • 10
    $\begingroup$ @StevenGubkin: I think they need to agree on speeds that are linearly independent over $\mathbb{Q}$ to ensure a close encounter. $\endgroup$
    – François G. Dorais
    Oct 14, 2014 at 15:50
  • 1
    $\begingroup$ @FrançoisG.Dorais, that depends on the rules. If person A stops when his geodesic meets the other one and person B keeps going forever, they will meet relatively quickly. I assume that the players can agree on a strategy before being thrown to the planet, but if the two players have to make their strategies independently, the problem is harder. $\endgroup$
    – Joonas Ilmavirta
    Oct 14, 2014 at 15:58
  • 2
    $\begingroup$ I think the most fun question is when the strategies must be symmetric (otherwise it is like they agree beforehand to synchronize) and they must meet as quickly as possible, in expectation, subject to an upper bound on travel speed $v$. So, when both players follow the same strategy, what is the optimal strategy and how long will it take them to meet on the unit sphere? $\endgroup$
    – usul
    Oct 14, 2014 at 16:12

2 Answers 2

Reset to default
15
$\begingroup$

Four observations:

  1. In the case that they are allowed to plan beforehand, person A and B could both agree to follow a random geodesic, leaving a trail. Any two geodesics are guaranteed to intersect in two points. Person A stops and waits as soon as he returns to his starting position. Person B starts following A's geodesic as soon as he intersects it. The time to completion of this solution is bounded above by $\frac{3 \times \textrm{Circumference of planet}}{\textrm{Speed of players}}$.

  2. If you are not allowed to plan beforehand, but you can see a finite distance away, you could use the following strategy. From where you start, make a bunch of circles by slicing planes through the circle perpendicular to the radius pointing at you. Make the distance between the circles small enough that you can see from one circle to the next. Walk each circle twice, leaving the message "do not cross this circle" along each path. You should eventually trap the other player between two circles, and you will find them on the second pass around the circle. This also works even if you are blind, as long as you can reach out a finite distance with your arms (you are not a point mass).

  3. If you are not allowed to plan beforehand, you are blind, and you are a point mass, then you really have no hope. In the worst case scenario, the other player just stays absolutely still, and you have probability zero of ever bumping into them, no matter what path you take. Although if you are immortal I guess you could still try to approximate a space filling curve, just for fun. Note that solution 1 works even if you are blind point masses, you just need to be able to talk beforehand.

  4. If you cannot write messages, or plan beforehand, I think you are also out of luck, since you could theoretically stay antipodal to each other for all time.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ Re: #3 and #4, it depends what you think of as "planning beforehand". We could ask "what is a strategy that succeeds if both players follow it?" We could consider this a sort of equilibrium strategy and it might be reasonable for both players to follow such a strategy even if they have never met or spoken. (Selection among all such strategies is a further problem...) $\endgroup$
    – usul
    Oct 14, 2014 at 23:58
  • 1
    $\begingroup$ Given that the surface of the Earth is 2-dimensional, isn't the probability of an infinite random walk hitting any given point actually 1? In particular, then, if the other person stays still, you're almost certain to hit them, not almost certain not to. $\endgroup$
    – cpast
    Oct 15, 2014 at 4:36
  • 2
    $\begingroup$ @cpast I have not thought a lot about random walks. At a finite time $T$, is your path not a measure zero subspace? If so, do you not have a zero probability of winning at any finite time? Maybe I am thinking about this incorrectly. $\endgroup$
    – Steven Gubkin
    Oct 15, 2014 at 12:42
  • $\begingroup$ I think Steven is correct if people really are idealized points, but the finite horizon assumption seems to me to be the right one for this problem. Also, I don't think that #4 is correct, because a randomized strategy can be used to break out of any such trap with probability approaching 1. $\endgroup$
    – Timothy Chow
    Oct 15, 2014 at 15:36
  • $\begingroup$ @TimothyChow re: #4, my remark was about the existence of a strategy guaranteeing a win. 2 shows that if you are not a pointmass, you can guarantee a win by writing messages to trap the other player. 4 claims that, without the other person knowing they cannot cross your lines somehow, they could theoretically stay antipodal, so you do not get a guaranteed win. I agree that, just by following a random walk, two players with finite extent will run into each other with probability $1$. $\endgroup$
    – Steven Gubkin
    Oct 15, 2014 at 15:42
11
$\begingroup$

Munroe's algorithm runs into trouble if one immortal (say, Charles) comes across the trail of the other (say, Marie) while Marie has already ran into and is following Charles' trail. If the two have the same maximum speed, they'll chase each other forever. You'd have to establish some rule, like one person reversing direction after a full loop, or have the strategy involve gradually cutting into and closing the circle.

I think the optimal symmetric strategy, assuming full trail and marker capability but no significant radius of sight, is to walk a random geodesic, leaving markers indicating the time since the start of the walk. After intersection, an immortal will be able to determine who will intersect the other's geodesic first; the first to cross the other's path follows it forward, and the second turns around and meets him. This strategy gives a worst-case end time of 1.25*(circumference of planet)/(speed of immortals).

Improve this answer
$\endgroup$
3
  • $\begingroup$ I don't think that's true, because after one full loop the If you come across a trail that's newer than any you've seen before rule prevents going in circles and allows Marie to catch up. $\endgroup$
    – Twinkles
    Oct 15, 2014 at 14:57
  • 1
    $\begingroup$ Munroe's next paragraph says, "You don't have to come across the other player's current location; you simply have to come across a location where they've been. You can still chase one another in circles, but as long as you move more quickly when you're following a trail than when you're leaving one, you'll find each other in a matter of years or decades." I don't think that this fully addresses the objection, because I can imagine symmetric scenarios that run forever, regardless of what deterministic rule is used. But you should be able to break out of a cycle by using a randomized algorithm. $\endgroup$
    – Timothy Chow
    Oct 15, 2014 at 15:23
  • 2
    $\begingroup$ Can someone please make a wikipedia page titled "Munroe's Algorithm" $\endgroup$
    – rghthndsd
    Oct 15, 2014 at 21:32

Not the answer you're looking for? Browse other questions tagged or ask your own question.