104
$\begingroup$

I was puzzled by a question my colleague asked me, and now seeking your help.

Suppose you and your friend* end up on a big sphere. There are no visual cues on where on the sphere you both are, and the sphere is way bigger than you two. There are no means of communication. You can determine your relative position and direction by navigating the stars**. You can move anywhere, and your friend too.

Upon inspecting the sphere, you see it is rock-solid, so you cannot create markings. To protect the environment, you are not allowed to leave other stuff, like a blood trace or breadcrumbs.

You have been put on the sphere without being able to communicate a plan.

How would you be able to find each other (come within a certain distance $\epsilon$?) What would be the optimal strategy to move?

*Since you are here, you must be a rational person. For this puzzle we assume your friend is rational too..Which makes it odd that you end up on that sphere anyway

**While you can determine your position relatively, you are on a sphere in a galaxy so far away that you cannot determine absolute 'north', 'south' etc. by the stars.

$\endgroup$
  • 5
    $\begingroup$ Presumably you consider that there is a distance $\epsilon$ such that you only need to come within $\epsilon$ of each other in order to find each other. Then one of you can stay put while the other chooses a path which comes within $\epsilon$ of every point on the sphere and starts walking. $\endgroup$ – MPW Mar 31 '15 at 7:24
  • 5
    $\begingroup$ Yes, there is a distance ϵ. But how to decide who stays put? $\endgroup$ – RobAu Mar 31 '15 at 7:26
  • 7
    $\begingroup$ Optimal in terms of what? Expected time, worst-case time or something else? $\endgroup$ – JiK Mar 31 '15 at 10:06
  • 6
    $\begingroup$ Something very similar is treated in Randall Munroe's book What If?, which I recommend to everyone. $\endgroup$ – Akiva Weinberger Mar 31 '15 at 15:45
  • 5
    $\begingroup$ Of possible interest: en.wikipedia.org/wiki/Rendezvous_problem $\endgroup$ – Barry Cipra Mar 31 '15 at 21:31

18 Answers 18

50
$\begingroup$

Move at random.

Any deterministic strategy you choose has a chance that your partner will choose the exactly opposite strategy, so you end up moving along more or less antipodal paths and never meet. So deterministic strategies have to be avoided.

You might make some adjustments to your random strategy. For example, you could prefer to walk longer distances in a straight line as opposed to choosing a completely new direction after every centimeter of movement. Depending on what your partner does, some of that might improve things. But to accurately judge whether it does, you'd need some probabilistic model of what plan your partner is likely to choose, and getting that right would pretty much amount to a pre-agreed plan. So you can't even know the probability distribution of plans for your partner, hence you can't quantitatively compare strategies against one another.

$\endgroup$
  • 5
    $\begingroup$ You definitely don't want to choose a new direction after each centimeter or even each kilometer. A random walk tends to stay close to its starting point, but you want to cover as much ground as possible. I'd start by choosing a random direction, then circumnavigating the sphere once to discover its size (without wasting any walking - you might meet your friend). $\endgroup$ – Hugh Allen Mar 31 '15 at 11:43
  • 6
    $\begingroup$ @HughAllen: If your friend decides to systematically cover the sphere in a grid-like fashion, then staying close to your starting point is a good thing to do. So while I agree that some strategies appear more reasonable than others, you can't quantify that without making an assumption on the distribution of strategies your friend might choose. $\endgroup$ – MvG Mar 31 '15 at 11:56
  • 2
    $\begingroup$ @MvG: you can use the classic cheat's way out of the Prisoner Dilemma: "I am rational, my friend is rational, therefore by symmetry we'll do the same thing, therefore (in Prisoner's dilemma) we should co-operate since we get better payoff given the constraint we make the same move. Likewise (on the sphere) we will follow a random walk with identical parameters". By "can use" of course I mean "can't use" ;-) $\endgroup$ – Steve Jessop Mar 31 '15 at 12:07
  • 4
    $\begingroup$ @SteveJessop If only you and your friend were superrational... $\endgroup$ – KSmarts Mar 31 '15 at 19:06
  • 2
    $\begingroup$ Can we get some results from this? i.e. what is the expected amount of time in order for the two to become within minimum viewing distance of each other? Given a sphere of radius $R$, walking speeds of $s_1$ and $s_2$, walking distances before turning randomly $d_1$ and $d_2$. Starting from random positions on the sphere etc. From this you could seek to minimise the time by tweaking the speeds and walking distances. $\endgroup$ – Ali Caglayan Apr 2 '15 at 12:54
38
$\begingroup$

As per "You have been put on the sphere without being able to communicate a plan." I'm going to assume you cannot even assume what plan your partner may come up with and there is no prior collaboration.

Given the potential symmetric nature of the problem, there must be a random element to break that symmetry, should you both accidentally choose mirror strategies. The problem is there's no guarantee that your friend will select an optimal strategy, however, if your friend is smart and/or exhaustive, they will realise two things:

  1. If you are both moving, the chances of running into each other can be nil given non-overlapping patterns.
  2. If one of you stays still, the other can eventually find you with an exhaustive search.

So the first thing to do is to calculate the size of the sphere (by picking a direction and walking until you arrive back at the start point or some other, more efficient technique). At that point, you can work out an exhaustive search pattern and the duration to perform one (a spiral pattern is close to optimal but difficult for a human to perform). That duration becomes your frequency of decision making.

Once per period, you flip a coin. Heads, you do an exhaustive search. Tails, you stay put. Each of the longer period (e.g. the less efficient search pattern), you have a 50/50 chance of doing the opposite of your partner and thus discovering each other in the course of the exhaustive search.

There's two extreme cases that are covered by this approach. If you partner decides to never move, obviously they will be found on your first exhaustive search. If they decide to permanently move, either randomly, or according to some pattern, there's always the chance of happening upon them accidentally during your search sweeps, which you have to rely on if they're not being exhaustive and their movement does not cover your 'stay put' spot. Otherwise, when you stay put you guarantee they'll eventually find you.

$\endgroup$
  • 1
    $\begingroup$ "calculate the size of the sphere, by picking a direction and walking until you arrive back at the start point" -- as I commented on another answer, you can measure the size of the sphere simply by observing the rate at which the stars fall below the horizon as you walk. The distance you have to travel depends on your accuracy of measurement. $\endgroup$ – Steve Jessop Mar 31 '15 at 17:21
  • 5
    $\begingroup$ weberprobability.blogspot.co.uk/2014/01/… suggests that it's probably a good idea to toss two coins and only go on a search if both land heads, 3/4 of the time staying still for the duration of the period. $\endgroup$ – Danikov Apr 1 '15 at 10:24
15
$\begingroup$

move on spirals like this:

rotating sphere with a spiral path on it

spiral path on a sphere
(source: forum.cad.de)

where the distance between spiral arms is $2\epsilon$.

I assume you have a measure of distance on your sphere, or else you couldn't determine the winning condition.

$\endgroup$
  • 1
    $\begingroup$ I don't think this will work if you friend goes spiralling as well? $\endgroup$ – RobAu Apr 1 '15 at 6:46
  • 3
    $\begingroup$ This is probably the optimal exhaustive search pattern, for which your partner is guaranteed to be located as long as they opted not to move before they were found. $\endgroup$ – Danikov Apr 1 '15 at 9:51
  • $\begingroup$ @Danikov yeah as soon as they move this wont really work. Not moving is not a sensible general strategy as there are many strategies the other could take which would mean they would never meet\ $\endgroup$ – Luke McGregor Apr 1 '15 at 10:01
  • 4
    $\begingroup$ Combine this with not moving: do the spiral once and if you don't find your friend sitting still, assume the friend is spiraling and sit still for the length of time it took you to spiral. Then If your friend doesn't show up you have to assume they started sitting still. That's the worst case first iteration. Now injecting some random element into whether you spiral or stay is probably your best bet. It's like the reverse of collision avoidance in Ethernet. $\endgroup$ – Todd Wilcox Apr 1 '15 at 10:29
  • 1
    $\begingroup$ It works just fine if your friend goes spiralling as well. There are two $\endgroup$ – gnasher729 Apr 1 '15 at 11:45
7
$\begingroup$

Here there are some points.

  1. Here it seems a bit redundant to me to talk about strategies, because it is more of a static game with complete information than a dynamic game.

    First of all, I assume that for you this is a game with complete information. To do so more explicitly, we – roughly – simply have to add to your sentence "There are no visual cues on where on the sphere you both are, and the sphere is way bigger that you two. There is no means of communication. You can determine your position and direction by navigating the stars. You can move anywhere, and your friend too." the words "you both know this, you both know that you both know this, and so on."

    Then, the game is static because the temporal element is not really relevant. You choose an action, your friend another, and that's pretty much it, because you cannot really change what you are doing given what your friend is doing, considering that you have no access to that information. Hence, we can get rid of the term "strategy", that in static games with complete information collapses to the term "action".

  2. Now, is any of your actions dominated (i.e. you could take an action that gives you a higher payoff, no matter what your friend does)? Not really. Hence, basically all your actions can be rationalized by some conjecture of your friend. Of course, due to the symmetric nature of the game, the same applies to you.

  3. Does the game have a solution? Well, it does depend on the solution criterion you think of, and also on how you conceive it. For example, IMO the game has an obvious Nash Equilibrium (please, note that I am not a rocket astronomer...): you and your friend go north, until you both can roughly find with some rough estimation that you are at the north pole of your sphere, and then you wait that the other shows up. You should end up in some $\varepsilon$ distance to each other. Note that here I am assuming the interpretation of Nash Equilibrium as a self-enforcing agreement. Note also, that this action profile should correspond in an objective correlated equilibrium, where the objective device is roughly the pole star.

PS: Of course, the all point behind points (2) and (3) is in order to define exactly what you think "optimal" means here (something that is always problematic). An additional point is that I am assuming that in order to coordinate, the players need to have some objective reference point (north pole - pole star).

$\endgroup$
  • 10
    $\begingroup$ While "north" is forbidden, you could perhaps argue that "directly under the brightest object in the sky (if there is one)" is a Schelling point (en.wikipedia.org/wiki/Focal_point_%28game_theory%29). Then your strategy could be (1) follow half a great circle in order to observe the whole sky (2) go to the meeting point. But this results in an argument as to whether Schelling points count as a form of pre-planning, and if not a game of whack-a-mole defining the sky in such a way there isn't one (so, all stars equally bright would deal with this example). $\endgroup$ – Steve Jessop Mar 31 '15 at 11:57
  • $\begingroup$ @SteveJessop: Thanks for your comment. Indeed, you are right regarding focal points (that are a standard informal tool to talk about coordination games such the one here). The fact that I did not mention focal points, and I rather talked – quite improperly! – about objective correlating devices, is that, while I am sure that focal points cannot really be formalized (even if they have a strong intuitive appeal), objective correlating devices can be, and there has to be some way in which I think my – very informal! – argument can be made more proper. $\endgroup$ – Kolmin Mar 31 '15 at 13:25
  • $\begingroup$ Regarding focal points as a form of pre-planning, they are not really an example in my opinion. They are more like something that arises from the background of a culture (i.e. different cultures can have different focal points). Indeed, they look a lot like some concepts from Wittgenstein's notes on certainty. Maybe, that's also one of the reason they are so difficult to formalize. Indeed, Wittgenstein was really skeptical about formalizations, and I am not surprised that a concept that closely resembles one of his is so difficult to capture. $\endgroup$ – Kolmin Mar 31 '15 at 13:29
  • $\begingroup$ I'm not sure why we would necessarily agree to go to North pole rather than the South, or under the brightest star rather than the dimmest, or the stars that are the closest together... $\endgroup$ – Samuel Edwin Ward Apr 6 '15 at 20:23
  • $\begingroup$ @SamuelEdwinWard: Indeed, it is not necessary. I was simply pointing out that this is an option. The all point behind the answer (that – note – was written before the OP edited to stress that you cannot determine your position "absolutely") is that the one I described is an equilibrium. Hence, I took a different stance to the problem, trying to see with a sort of top-down approach, if there can be some equilibrium. Otherwise, in my answer I simply hinted at the fact that you cannot really compare strategies, thus there is not a "bottom-up" solution. $\endgroup$ – Kolmin Apr 7 '15 at 10:28
6
$\begingroup$

Since you've included stars such that can be navigated from in the problem statement, this means that at least one unique "configuration" of star positions is visible from any given point on the sphere.

From this, I would posit that a better-than-random solution would include finding the most "interesting" such configuration (so first you have to map them all by traveling the sphere methodically) and heading there as a Schelling point. If one's confidence level in a given configuration acting as a Schelling point for the other player is insufficient, a strategy that randomizes a distribution of time spent at each point of interest could be worked out depending on the size of the sphere, ϵ, and confidence level in the "interesting"-ness of each point.

For example, a "default" Schelling point for two players who think like I do would be to seek the unique star configuration with the least component stars. Or, to rephrase it for an Earth-like sky, the recognizable constellation made up of the least amount of stars -- or possibly the brightest star in the sky, if there is one sufficiently brighter than the others.

$\endgroup$
  • $\begingroup$ "this means that at least one unique "configuration" of star positions is visible from any given point on the sphere." Only true if the sphere is rotating. If it is rotating the 'best' Schelling point would be the smallest group of stars that do not set. It then remains for each person to determine which hemisphere (north or south) one is in. $\endgroup$ – Nate Lockwood Mar 31 '15 at 17:07
  • $\begingroup$ Rotation (around the axis and around the sun) can be factored out if you have enough computational resources. This is the strategy I would choose if I was writing a story (or if it should actually happen to me): Go stand directly below the brightest fixed star (i.e. not planet on moon) in the firmament. $\endgroup$ – alexis Apr 1 '15 at 9:01
5
$\begingroup$

I think completely random movement is sub optimal.

I think a better strategy is to pick a direction (any will do), stick to it and randomise your speed.

If both parties do this their paths will cross twice each orbit (unless they are on the same orbit in which case they will meet sooner due to randomised speed)

if you go full random changing direction as well as velocity you aren't guaranteed to ever cross the path of the other. (although as t gets large it becomes increasingly likely that your paths will cross at least once.)

Speed randomisation is necessary to avoid never meeting because of resonance.

Convergence will be quickest if both parties adopt the same strategy. If the other party adopts any other rational strategy that doesn't involve being stationary they will meet eventually.

$\endgroup$
  • $\begingroup$ The two could be on non-intersecting orbits like northern and southern polar circles. $\endgroup$ – Rasmus Apr 4 '15 at 20:37
  • $\begingroup$ @rasmus any set direction on a sphere will take you on a circumference you actually don't travel straight going around a polar circle. $\endgroup$ – Luke McGregor Apr 4 '15 at 21:43
  • $\begingroup$ You are right. $ $ $\endgroup$ – Rasmus Apr 5 '15 at 6:25
3
$\begingroup$

Are you allowed to leave your 'footsteps'? I believe it makes the problem more interesting (otherwise the solution of MvG seems to be correct).

My solution is based on the fact that 2 great circles must intersect on two points (or be the same circle). So I suggest that both persons will start walking in a great circle. Eventually, each one will reach an intersection (or his own starting point, which can be treated in a similar fashion)

In average, it will happen after walking half a circle. we'll call this time $t$

  • It might be the same intersection, but on different times
  • It might be exact opposite points on the sphere

In the latter case, the situation might be symmetrical (consider the case of two persons landing on the exact opposite points and walking at the same speed on different great circles), so there is no way to decide (without pre-arrangement) who will wait to the other.

This means that the next step should be to randomly decide if you wait for a period of time $\alpha t$ (I'm not sure what is the ideal $\alpha$ is, it's below $2$ if both persons walk at the same speed, and maybe should be randomized as well) (they should be able to know what is $t$ by now) or go to the opposite point. After each period of time you should randomly decide again.

To give a rough estimate of the time it will take, we can assume that the chance to meet at the $n$-th period is $P(n) = \frac{1}{2^n}$, so $E[t_{meeting}] \propto 2 \alpha t$

$\endgroup$
2
$\begingroup$

Dig a hole directly vertically downwards towards the centre of the sphere using a plumb line. Both parties holes will intersect at the centre of the sphere.

$\endgroup$
  • 3
    $\begingroup$ "You can move anywhere" $\endgroup$ – Andy Apr 1 '15 at 3:23
  • 1
    $\begingroup$ I wonder if this would be the fastest way, though ;) $\endgroup$ – RobAu Apr 1 '15 at 14:54
  • 2
    $\begingroup$ Even better: fly vertically up until you can see half the sphere, then start orbiting. If your friend does the same, you should pass in each others line of sight soon. $\endgroup$ – gerrit Apr 1 '15 at 15:31
  • 1
    $\begingroup$ @gerrit Being able to see half the sphere would require infinite altitude. It is better to go to a height corresponding to ten radii of the sphere, or some other arbitrary altitude. $\endgroup$ – Jeppe Stig Nielsen Apr 1 '15 at 16:52
  • 2
    $\begingroup$ @JeppeStigNielsen True, seeing 45% of the surface is a good compromise. And you can see the friend more easily than you can see the surface of the sphere. Actually, you can just both fly up until the sphere below you is vanishingly small and then you're almost 100% sure to have a free line of sight to each other. But I suppose the rules require both users to stay at the surface. $\endgroup$ – gerrit Apr 1 '15 at 17:13
1
$\begingroup$
  • Step 1: Walk in a great circle until the sky is the same, count your footsteps along the way.
  • Step 2: I'm assuming you can translate footsteps to units of $\epsilon$. Call the circumference C. Turn $\frac{2\pi \epsilon}{C}$ radians anticlockwise.
  • Step 3: Walk in a great circle until the sky is the same.
  • Go to step 2

Stop this procedure if at any point you are within $\epsilon$ of your partner.

Since your partner is rational they've assumed the same strategy. Between you and your partner's starting point is a great circle of equidistant locations. Since you and your partner are always walking at the same time, you are always the same distance from your relative starting points.

For each greater circle walked you visit the equidistant circle twice (not necessarily at the same time as your partner). As you explore the equidistant circle in one direction your partner explores it in the opposite direction since she is on the opposite side.

You will meet your partner on the equidistant circle within $\lfloor\frac{C}{\epsilon}\rfloor$ iterations.

$\endgroup$
  • $\begingroup$ This solution assumes that the players will both choose the anticlockwise rotation. However if the strategy is to choose at random, they have 50% of choosing wrong, if they decide before landing, it's equivalent to choosing who will wait and who will search. $\endgroup$ – j0ker5 Mar 31 '15 at 18:32
  • $\begingroup$ @j0ker5 yes is does. Its common for these problems to assume identical rational agents. This is not the same as two individuals adopting entirely different strategies. $\endgroup$ – Steve Cox Mar 31 '15 at 18:36
  • 3
    $\begingroup$ Since your partner is rational they've assumed the same strategy. I disagree: there is no reason why both would have chosen this strategy. $\endgroup$ – punctured dusk Apr 2 '15 at 9:47
1
$\begingroup$

I couldn't find my answer by zigzagging the comments/ answers, so here it is

Create breadcrumbs towards your location.

Move a certain distance from your "home" (origin point) and write down an arrow on the ground (or other marker) pointing to your home. Repeat that all around your location so within say 10 ϵ your crumbs can guide someone to the center. By doing this further and further away (then coming back to the center !) you make it easier to find you.

Either your friend will look around exhaustively, or he can do the same thing, and eventually one of you will stumble on an arrow.

If you do find one and your friend isn't at the center, either wait for him, or leave a mark at the center saying you passed here and tried to find him, so you can come back at some point and meet (having a meeting point)

Not really a math answer but a practical one =)

$\endgroup$
  • 1
    $\begingroup$ This assumes that both persons have a lot of breadcrumbs with them (or any other way to leave marks on the sphere), which isn't part of the hypotheses of the problem. $\endgroup$ – A.P. Apr 1 '15 at 11:42
  • 1
    $\begingroup$ Hmm I guess you're right (I meant of course move around rocks and such to make pretty arrows. anything against using blood ? =p ). That's what I get for answering a math question with a practical answer) $\endgroup$ – Jiby Apr 1 '15 at 13:08
  • $\begingroup$ @Jiby Well, the problem with practical solutions is that they assume much more than math problems, just as A.P. pointed out. Of course you can solve problems with (relative) ease given appropriate tools. That is how humans as species survived, despite not being sophisticated mathematicians. But, how to solve a problem with no tools at all, that is the question. $\endgroup$ – Ennar Apr 3 '15 at 18:04
0
$\begingroup$

Since the stated problem states that one can navigate by the stars I assume that the sphere is rotating, if not there is meaningful stellar navigation is not possible, IMHO*.

Then, both rational persons, can find 'north' by facing the direction from which the stars appear to rise the fasted, mentally label it 'easterly', face 90 degrees (should i use radians here?) to the left, and label that direction 'northerly.

Then watch the both the northerly and southerly directions looking for stars that don't 'set'. If that group of stars is southerly one is in the southern hemisphere, else in the northern hemisphere.

Memorize the configuration. The two persons can reduce the distance between them by both walking north.

A . If in the northern hemisphere walk toward the target stars each night. One can estimate the latitude and progress by subtracting the estimated elevation from 90 degrees. When the stars are directly overhead stop and start a search.

For instance at regular intervals try a random walk for a distance much greater than ϵ and at every stop do a random walk for a distance a bit larger than ϵ perhaps resting for a few days. (Some animals have a search pattern if this sort - without the rest - but I have forgotten the name of the pattern.) Don't stray too far from the north pole.

B If in the southern hemisphere walk away from it at night until the target stars are setting. At this point notice the stars to the north that only rise a little bit before setting; this will be north and proceed as above (A).

  • If the sphere is not rotating there is no way of each person finding 'north'. Walking in a great circle, as has been suggested, by walking toward a specific star breaks down when the star disappears at the horizon or when the star approaches zenith unless one can find a set of stars that are in a line.

I'm assuming that a line cannot be scratched on the sphere that the other might come across and follow.

$\endgroup$
  • 3
    $\begingroup$ Imagine a non-rotating planet, with 4 stars of different colours falling on a circle whose centre is the centre of the planet. Then each point on the planet is uniquely determined by which stars you can see, their heights above the horizon, and (to distinguish hemispheres) the order of colours counting clockwise. Stellar navigation is possible, but the planet doesn't move. Now make the pattern of stars less regular, so that it's not "obvious" that two special points on the surface are the poles of any sensible navigation system. $\endgroup$ – Steve Jessop Mar 31 '15 at 17:33
0
$\begingroup$

You can't have an optimal solution for this problem.

Let's assume one possible scenario of this system:

"That whatever you do the other person would do the opposite."

So this becomes a case similar to Quantum Entanglement. You can never find out the present state of both particles. In this case the position.

Second problem is that at any givem time your destination is assumed to be every point on the sphare -distance in sight. So if you destination isn't a set point you can't plot an optimal course. (given the information and no loopholes)

$\endgroup$
  • $\begingroup$ There are definitely sub-optimal solutions to the problem (for example standing still) so there must be an 'optimal' solution, that is one that performs at least as well as any other solution. $\endgroup$ – Luke McGregor Apr 1 '15 at 3:55
  • $\begingroup$ But there is always a chance whatever you choose would get countered by the other person either by doing the same thing or the opposite. So any Optimal Strategy have to inlcude both of them which you can't do. $\endgroup$ – Ahmad Apr 1 '15 at 9:53
  • $\begingroup$ I think there are some strategies which cant really be countered by a sensible strategy from the other person. Perhaps those are the set of optimal strategies. $\endgroup$ – Luke McGregor Apr 1 '15 at 9:57
  • $\begingroup$ The answer by the Marcel Köpke (above) going in helix type pattern is a guarantee to find the other person but if the other person moves in front or back from the 1st person on a distance more than "absilon", they would find each other but after covering the whole sphare. Not an optimal solution $\endgroup$ – Ahmad Apr 1 '15 at 10:06
  • $\begingroup$ What i want to say that any strategy can be countered or made non-optimal $\endgroup$ – Ahmad Apr 1 '15 at 10:10
0
$\begingroup$

Assuming this sphere is like an exercise ball... and that there is no wind, no animals, and somehow the two of you need no food for the time being.

Take off one shoe. Point it in a direction of your choosing, and walk in that direction - straight. If (you should) return to that point, modify your angle (do not change the direction of the shoe) so that you circumnavigate in a different direction. You'll eventually traverse "most" of the surface area, and your walking speed will be different than your friend. You will eventually come within some distance of each other, such that you can see each other. That's the solution.

2nd solution. If you really could discern straight lines/curves, then your goal would be to find the path such that you are walking the full circumference. You can do this by counting your steps. If you know that your circular path is now the full circumference (and your friend does the same), your different walking speeds would lead to to be within some range of each other eventually that you see each other.

$\endgroup$
  • 1
    $\begingroup$ If you are going to be continually traversing this sphere, one of your shoes should probably be the last thing you leave behind. Also it might be difficult to walk in a straight line if you are only wearing one shoe. $\endgroup$ – Roger Apr 1 '15 at 15:06
0
$\begingroup$

solution of Steve Cox. Once you cover all sphere and back to lending point, choose random turn at step 2. You friend does exactly the same and even if you move from opposite poles doing exactly the same with same walking speed - you will meet.

$\endgroup$
  • $\begingroup$ by the way - if both guys always move forward - they both are doing great circles, which cross in two points ( or match each other ) where they will meet if they randomly change frequency of circulation. $\endgroup$ – user2167003 Apr 1 '15 at 0:03
0
$\begingroup$

Suppose there is any way to identify special points on the sphere [see below], the optimal strategy would be to identify the maximally "prominent" special point or points, and spend a randomized amount of time at each one. This reduces the dimensionality of the problem from meeting on a sphere to meeting on a finite number of points. As @gerrit pointed out in a comment under the question, this is a difficult problem even with three locations; but certainly it will admit more efficient solutions than meeting on a sphere with no features.

But what special points? Even though the sphere itself has no features (and we cannot leave any marks), you don't need a familiar sky to identify the poles. So if we're allowed to use the planet's rotation as information, I'd identify the two poles and then spend a random amount of time in each pole, then move to the other. If my counterpart adopts a similar strategy (and by symmetry we can expect him/her to do so), the odds that we remain at opposite poles approach zero over time. I can name the poles "North" and "South" according to the direction of rotation (as pointed out by @Kundor), but I wouldn't be 100% confident that if I choose North, the other person will too. Still, narrowing it down to two points is not bad at all.

Even if the planet does not rotate, I can still look for the brightest star and go hang out directly below it for a while (moving along as the planet rotates). In fact, even if the planet rotates there are moving special points, e.g. "the point that is currently directly under the brightest star [or under the sun]".

All that said, I'm pretty sure the point of the question is to optimize a scan of the sphere's entire surface with maximum probability of intersection, so any "special points" are considered off-topic. Perhaps the planet is covered by clouds, but the participants have some sort of inertial device that measures displacement but cannot determine the axis of rotation. Or they are actually not on a planet's surface but in the stomach of a spherical cow, and it's dark...

$\endgroup$
  • 2
    $\begingroup$ If the planet is rotating, North and South are determined for you (by the right-hand rule)! $\endgroup$ – Kundor Apr 2 '15 at 3:54
0
$\begingroup$

Perform the following steps until you find your friend:

  1. Figure out a path (based on the stars) that checks the entire sphere and walk it, returning to your starting point. The time it takes you to walk this is t.
  2. Flip a coin (or a your shoe, or whatever...).
    • If Heads: Goto step 1
    • If Tails: Wait t and then repeat step 2

Notes:

  1. If both you and your friend accept this strategy
    • You might luckily meet on your first trip around the sphere
    • If you don't meet the first trip and t is approximately the same for both of you, you'll likely meet the first time you and your partner get a different value for your coin flip (one of you will be resting when the other is moving)
    • If you don't meet the first trip and t is quite different for both of you, each time you unknowingly pass your friend's "home base" after the first trip, the odds of finding them resting are 1 in 2. You also may cross paths while both traveling.
  2. If your friend picked a different strategy
    • If they rest until you find them: You'll find them on the first trip
    • If not: They will have a 1 in 2 chance of finding you each time they pass your home base after your first trip. Otherwise, you will have a chance at finding them during each trip you take around the sphere based on whatever strategy they chose and their starting location
$\endgroup$
0
$\begingroup$

MvG got it half right.

He is correct that your strategy must be random to avoid mirror image problems. He even correctly concludes that a random walk is not a good strategy--but then fails to make the final step:

Figure out a coordinate system for the sphere.

Walk to a random point on the sphere, repeat until you find your friend.

If you have the means to do so getting higher up is of value so long as you don't get so high that you fail to spot your friend due to distance rather than him being below the horizon. From the problem description I think it unlikely that you have access to spacecraft but for spheres with a diameter of no more than a dozen or so miles just your legs will be of benefit.

There have been requests for an estimate of the duration. Since this is random any estimate by it's nature is also random. As you move you observe a new area equal to a stripe your sight distance wide (it's actually a crescent but the area is the same--look at the area of a racetrack to see this.) Thus the odds of finding your friend is your sight distance * your movement speed / the area of the sphere. All distances must be in the same unit, the odds are per the time unit used in the movement speed.

Note how this is linear on sight distance, if you can increase your sight distance with jumping more than you lose in speed by jumping instead of just walking do so. Since our natural movement in low-g appears to be kangarooing anyway one should go with this.

$\endgroup$
0
$\begingroup$

In examples of this in 2D that I've heard, if I recall the answer is:

  • Mark the spot you landed and remember it. Leaving the parachute you used behind will suffice.

  • Travel back and forth in increasingly large distances away from your landing site. (IE: 1 yard west of site, 2 yards east of site, 3 yards west, etc.)

  • If you encounter a second parachute, stop and wait.

  • Assuming you don't run out of fuel, you will eventually either encounter the other robot, or its landing site.

In 3D, that becomes a lot trickier. Rather than back and forth, as someone else mentioned, you could use spirals. You would then eventually encounter the second landing site. But then, what do you do when you find it? If the rule is "wait at the second landing site", the other robot may never return.

Either you need to return to your own landing site at regular intervals (like once every 360 degrees) and check to see if the other robot is waiting there, or once you find the second landing site, start traveling between it and your own landing site. In each of these, you should eventually encounter the other robot.

Thinking a little more about it, returning to your own landing site as you search may not work, since you might both find the other site at the same time and stop, so you would have to start going back and forth from one site to the other once you found the second site.

I have no idea if this is optimal, though.

$\endgroup$
  • $\begingroup$ I am not sure how to interpret you dimensions; I suppose the 2D case involves a circle and the 3D case a sphere. In any case the proposed 2D solution does not solve the problem of the question: you may find the other landing site, and the other finds yours, and there you both wait forever. $\endgroup$ – Marc van Leeuwen Apr 4 '15 at 9:45
  • 1
    $\begingroup$ In the 2D version that I saw, it was considered fail if you both walked away from each other (so we can assume east and west extend forever). In 2D, the ground is 1D (in 3D the ground is 2D), and along 1D ground, you can't pass by each other without meeting. $\endgroup$ – Dave Cousineau Apr 4 '15 at 17:22

protected by Asaf Karagila Apr 1 '15 at 12:15

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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