5
$\begingroup$

Fictional Background Story (The Experiment):

Two extremely fast and intelligent alien snails are randomly placed on two different points on an infinite plane, as an experiment by the cruel ruler of their planet. Their goal is to meet each other. When they move they leave a trail behind them. It's almost completely dark (they can only see what's just infront of them) so they have to rely on their intelligence to find each other. Once they find each other they'll be rewarded and returned to their planet. They will be carefully observed from above by their ruler and his team so that no rules are broken and they will have exactly 24 hours to find each other. Luckily both of them has an exceptional ability to keep track of time. If they don't find each other they'll be stuck there for a very very long time until the next opportunity to escape is given by the ruler.

Rule:

  • Only one of them is allowed to move in at most two different straight directions, the other one can only move in one straight direction. They don't know how many moves the other snail has made so they have to come up with a good strategy beforehand not to make more moves than allowed (3 in total).

enter image description here

Question:

If they use the best strategy possible, what's the probability of them meeting each other?

$\endgroup$
6
  • 2
    $\begingroup$ What is a “move”? Are they on an infinite checkerboard or something? And one of the snails can move in only one direction? I feel like I’m misunderstanding some important detail of this. Edit: never mind I think I understand. They can only make three straight-line moves total, two for one snail and one for the other. The moves can be arbitrarily long. $\endgroup$
    – SQLnoob
    Mar 16 at 19:42
  • 1
    $\begingroup$ @SQLnoob Exactly so, yes. $\endgroup$ Mar 16 at 20:11
  • 3
    $\begingroup$ Can you clarify what you mean by "randomly placed" for an "infinite plane" (I assume two arbitrary positions a (finite) distance apart)? Also, does traveling in reverse in the same direction count as a separate move? $\endgroup$
    – geometrian
    Mar 17 at 4:45
  • 1
    $\begingroup$ @geometrian Yes, just placed at two different arbitrary positions. Finite distance. Travelling in reverse count as a different move. $\endgroup$ Mar 17 at 7:13
  • 2
    $\begingroup$ Is a snail aware of were north is ? $\endgroup$ Mar 19 at 8:10

4 Answers 4

6
$\begingroup$

Answer

The answer is:

A measly 12.5%.


Solution

We are told that the snails start an arbitrary finite distance $R$ apart, and it seems they can travel at any arbitrary finite speed. It seems that they don't know their orientation either.

If one snail doesn't move, then the chance of the other snail encountering them is 0% with any strategy. Thus, any other strategy is potentially better and we can conclude that both snails must move.

The only way the snails can meet up is if their paths cross and they arrive at the same instant. This happening by the snails arriving at the same time has probability 0%, so the only viable way is for one snail to find the trail of the other.

If one snail finds the other's trail, it could wait for the other to double back. However, there's no way for the still-moving snail to know that it should turn back. If the moving snail turns back after a certain amount of time (using its excellent time-sense), then the finite distance it travels before then implies an upper-bound on the furthest $R$ the snails will be able to solve. Since $R$ can be arbitrarily large, the probability will be 0% for some (in fact almost all) configurations. This strategy is therefore bad.

It turns out that the only remaining way is the best: for one snail to find the path of the other, turn along it, and race after them, hoping it picked the right direction and that they'll meet up some time later.

This requires a remaining allowed turn and for both snails to have moved. Thus, the only viable strategy is for both snails to pick a direction, walk in it, hope they encounter the other's trail, and then pick a direction and race along it.

---

The snails' paths are rays. Notice that the strategy is symmetric in that it doesn't matter who gets to the intersection first. If snail A gets there first, it doesn't know it's the intersection because it hasn't happened yet, so A continues on. Snail B arrives later and finds A's trail, thus it picks the direction to turn. Similarly, if B gets there first, B continues on; when A arrives, A has to pick.

WLOG, we can suppose that A finds B's trail instead of the other way around, and that A starts at the origin walking along the $+x$-axis while B starts somewhere else and goes in a random direction.

B starts either above or below the $\pm x$-axis. In both cases, 50% of B's directions point away from the $\pm x$-axis, and 50% of the remaining time the direction intersects $-x$ instead of $+x$. Thus, A finds B's trail only 25% of the time.

A then has to choose a direction to turn and follow. There's a 50% chance of choosing correctly, so 12.5% chance in total.

Assuming A picked the right direction, A can ensure it meets up with B. So that the snails can cover any arbitrary distance, they have to move at speed (say) $1/t$, where $t$ is the remaining time before the deadline. Thus, if one snail finds the trail of the other, it can race along afterward at $2/t$, which will produce an intersection before the deadline.

(For example, suppose A finds B's trail with just 1s left, A picks the correct direction, and B is 10m away. B is traveling at 1/t = 1m/s, while A races after at 2/t = 2m/s. After 0.9999546s, they meet. B is traveling at 22026m/s and has traveled 10m, while A is traveling at 44056m/s and has traveled 20m, making up the difference. This is always possible, regardless of how far apart the snails start.)


Extended Example

(Note: there are a couple links to some calculations, but a full simulation for this example, at the used precision, can be found here.)

Let's say snail A (Anne) and snail B (Bill) are plonked down one billion kilometers away from each other. "Ha ha!", says the evil ruler, "they'll never find each other now!"

Under the above scheme, Anne and Bill both start oozing in random directions. In Anne's frame of reference, she is at $\left<0,0\right>$ heading east (i.e., $\left<1,0\right>$), while Bill is at (say), $\left<9.135\!\times\!10^{11},-4.067\!\times\!10^{11}\right>$—a billion kilometers away and $24^\circ$ to what she calls south—and (fortuitously for them) has randomly chosen direction $\left<0.3256,0.9455\right>$ (bearing $71^\circ$).

Anne and Bill both travel at rate $1/t$, where $t$ is the remaining time. So, they start out at $1/86400≈11.57\text{ μm/s}$—pretty slow! In fact, after 23 hours 59 minutes, with just 60 seconds left, each snail has only traveled $7.272\text{ m}$.

"Look at these pathetic fools! They've given up completely!" exclaims the evil ruler, and he moves to end the experiment early.
"Wait!" shouts his top advisor. "We need to be fair! Let the clock run out entirely."
The evil ruler pulls a lever, dropping his advisor into a crocodile tank, but pouts because the advisor was right. The snails really do deserve all their allotted time.

When there's only 10 seconds left, the snails have each still only traveled $9.064\text{ m}$. With just 1 second left, only $11.37\text{ m}$. Anne and Bill have barely even moved from their starting points and are still nearly a billion kilometers apart. Surely, all is lost!

But in that last beautiful second, the mathematical nature of their speed comes into play, and their true strategy is revealed.

With just 1 millisecond left, they have each traveled $18.27\text{ m}$. With just $1\!\times\!10^{-100}\text{ s}$ left, they have each traveled $241.6\text{ m}$. With $1\!\times\!10^{-100000}\text{ s}$ left, they have each traveled $230270\text{ m}$ and each is traveling at $10^{100000}\text{ m/s}$.

With $1.472\!\times\!10^{-1.868\times10^{11}}\text{ s}$ on the clock, Bill blazes across the $+x$-axis of Anne's frame at location $\left<1.054\!\times\!10^{12},0\right>$, where their paths will eventually intersect. He doesn't know it, though, since Anne hasn't been there yet, and he continues on his merry way.

With just $1.170\!\times\!10^{-4.576\times10^{11}}\text{ s}$ remaining, Anne arrives, crossing Bill's trail! By this point, Bill is at position $\left<1.257\!\times\!10^{12},5.895\!\times\!10^{11}\right>$—still $6.234\!\times\!10^{11}\text{ m}$ away.

Anne now chooses one of the two directions. She happens to correctly guess northeast, and races after Bill, changing her speed to $2/t = 1.709\!\times\!10^{4.575\times10^{11}}\text{ m/s}$. (Yes; that's a speed with a half-trillion digits. Luckily, Anne did track+field in high school, so this sort of pace is no problem for her.)

The evil ruler has barely had time to blink.

Anne now must catch up with Bill. Bill keeps going at his $1/t$ pace, getting faster and faster as the remaining fraction of an instant dwindles closer and closer to zero. But, even as fast as he goes, Anne is chasing him at $2/t$—twice his speed at every moment, gaining ground. With $9.306\!\times\!10^{-7.283\times10^{11}}\text{ s}$ left on the clock—a very small, but still positive time!—Anne catches up, ramming into Bill at a relative speed of $3.585\!\times\!10^{728320160648}\times$ the speed of light, but they're happy about it because they are reunited!


Reversing

It is a testament to the cruelty of the ruler that going backward counts as a separate move. Otherwise:

The snails could each pick a random direction and walk back and forth along it with a position $x(t)=\sin(1/t)/t$, where $t$ is the remaining time. The lines are guaranteed to intersect (the chance of the snails randomly choosing the same line direction has measure 0), and so the snails can just wait at the intersection. Only two moves required, and 100% chance of success.

At the very least, with even only one reverse allowed, the snails could double their chance of success in the above analysis: if the intersecting snail picks the wrong direction, it will come to the other snail's origin, at which point it could shift into reverse and catch up by going the right way.

$\endgroup$
8
  • 1
    $\begingroup$ You don't need the sine. Just follow the line segment until you get to one end and then (if necessary) turn back. $\endgroup$
    – msh210
    Mar 18 at 4:40
  • 1
    $\begingroup$ @msh210 Sure; there are other ways to do it, but I modified the Topologist's Sine Curve because that seemed elegant to me. It's moot anyway since reversing counts as a turn; I only mentioned it at all for interest. $\endgroup$
    – geometrian
    Mar 18 at 6:47
  • 2
    $\begingroup$ @Prim3numbah We could assume that . . . but it could also just mean that the snails were placed very far apart—which is surely the case when the evil ruler plonks them on an infinite plane! The strategy must handle the snails starting an arbitrarily far distance apart, or else we're just guaranteeing they fail if it's more than a certain distance.¶ (Also see edit: I added a worked example with actual numbers!) $\endgroup$
    – geometrian
    Mar 18 at 22:34
  • 2
    $\begingroup$ Ok it makes sense now, so even if they were let's say 10¹⁰⁰ metres away from each other from the start and we use the same type of setting you chose this would just mean that Anne would find the trail of Bill within an even smaller t (still positive) and then accelerate at 2/t in hopefully the correct direction and guaranteed to catch up Bill. The numbers are ridiculously large (speed) and small (t) :D, but this method will always work since there is always some positive t left. $\endgroup$ Mar 19 at 14:30
  • 1
    $\begingroup$ I'm gonna give you the checkmark for this since it proves that we can treat the paths as rays (due to the acceleration) and not just line segments as suggested by the other good answer given by @NoeS. $\endgroup$ Mar 19 at 14:31
7
$\begingroup$

The problem seems a bit under-specified, but as written, it seems the only possible valid answer would be

Zero!

First, given the wording, it seems reasonable to make the assumption that "extremely fast" is not "infinitely fast". If we allow infinitely fast, it's a different discussion and we would need to have Mr. Einstein weigh in.

So if they are only "extremely fast" and located at random locations on an infinite plane, then even if they were crawling (very quickly) straight towards each other, they will almost certainly be too far away from each other to meet up in a finite amount of time.

Furthermore:

While the chances of two random rays intersecting is 25%, "extremely fast" crawling will only produce line segments, not rays. The chance of two finite line segment intersecting on an infinite plain is basically zero.

$\endgroup$
4
  • $\begingroup$ Your reasoning is good but it's only applicable if we know their max speed. If we call the finite distance between them d, then nothing is stopping us from letting them have a max speed of (let's say) d/hour. That's why I was vague and said "extremely fast", not a given max speed. $\endgroup$ Mar 18 at 14:19
  • 1
    $\begingroup$ But we don't know the value of d and neither do the snails, so I don't see how there is any discrete value of d that they can choose that has any meaning in an infinite plane. $\endgroup$
    – Amoz
    Mar 19 at 3:23
  • 3
    $\begingroup$ @Prim3numbah Think of it this way; let the maximum distance they can travel in 24 hours be D. Draw a disk of radius 2D around the first snail. If the second snail is outside this disk, then it is impossible for them to reach each other within the time limit. Therefore the probability they find each other is less than or equal to the probability the second snail is inside the disk. Since the area inside the disk is finite and the area outside the disk is infinite, then this probability is 0. $\endgroup$ Mar 19 at 4:26
  • $\begingroup$ @2012rcampion I like the way you explained it, but user 'Geometrian' has shown that there is no maximum distance D due to them always accelerating (using 1/t), so we can treat the paths as rays instead of line segments. $\endgroup$ Mar 19 at 14:55
6
$\begingroup$

First thoughts, almost certainly not optimal and please let me know if this is way off track:

Call them Snail 1 and Snail 2, with the numbers representing how many directions they can move in. A very simple strategy would be to have Snail 1 just start moving right away in a direction (let's call it east, for ease of reference) at some speed W, leaving a long straight trail of slime. After waiting for a certain amount of time X, Snail 2 takes off in a straight line at some speed Y, hoping to run into Snail 1's trail. If he does, he chooses to turn and follow the trail in one direction (at possibly some other speed) hoping he chose correctly and is going fast enough to catch up.

Naively, it seems that when Snail 2 starts moving, his probability of running into the slime trail is related to the angle at which he was positioned relative to Snail 1 at the start, e.g. if Snail 2 was southeast of Snail 1 and chooses to start moving north, he'll run into the trail; if he chooses to start moving south, he never will. And if he does run into the trail, there's a 50% probability he'll correctly guess which direction to follow it in. Geometry puzzles aren't my strong suit, I'd have to do more thinking/math than I'm prepared to at the moment but hypothetically say there's a 50% chance that Snail 2 chooses an initial path angle that will cross Snail 1's path, then overall there'd be a 25% chance of them meeting (I don't actually think that's the right answer, just illustrating my thought process).

That's very hand-wavy, I don't know how specific we need to get about their speeds and travel times, or if we can just assume they're sufficiently fast to essentially be a ray emanating from a point, which in my mind reduces the problem to "what is the probability that two rays drawn at random directions from two randomly placed points in the plane will cross?"

$\endgroup$
9
  • $\begingroup$ The chance of two rays crossing is exactly 25%. $\endgroup$
    – mathlander
    Mar 16 at 20:40
  • $\begingroup$ Therefore, the chance of them meeting is 12.5%. $\endgroup$
    – mathlander
    Mar 16 at 20:42
  • 1
    $\begingroup$ Another idea would be to have the first snail double back on his own trail, resulting in a 25% probability of meeting. $\endgroup$
    – mathlander
    Mar 16 at 20:44
  • 1
    $\begingroup$ @mathlander is that minus-the-same-direction or two directions? $\endgroup$ Mar 16 at 20:56
  • $\begingroup$ Good job so far, just need to be more specific calculation wise. Check @mathlander comments. They're allowed to travel in the opposite direction aswell. $\endgroup$ Mar 17 at 7:38
-1
$\begingroup$

It is

undefined
Assume snail 1 moves infinitely fast to the west; then snail 2 moves until he crosses snail1's path (if ever); then either snail 1 moves east or snail 2 west.
This seems to give 25% chance (both going towards the point where their lines meet, i.e. 50%x50%.
However, going with an infinite speed in some direction of an infinite plain does not reach its end (since there is none). Or formulated otherwise: the infinite failing part and infinite succeeding part cannot simply be divided.
In addition, one can reason differently to demonstrate this: Assume snail 2 moves north-west. With the starting position of snail 1 defined as 0.0 This would mean it crosses snail1's path 3/8th of the time. With the direction nearing west, this fraction would increase to half.
However, a designation like northeast is depending on the choice of coordinate system. Also here the reasoning cannot be used with infinities.

$\endgroup$
2
  • $\begingroup$ OP does not say "moves infinitely fast" (it would be impossible to meet) but "extremely fast". $\endgroup$ Mar 17 at 19:26
  • $\begingroup$ Ok if they are "a finite distance away" at start, and "The moves can be arbitrarily long" as mentioned in comments, the 3rd pargraph applies: rot13(Frpbaq fanvy pna gnxr 2aq zbir va nyzbfg gur fnzr qverpgvba sbe nyzbfg svsgl creprag punapr.) $\endgroup$
    – Retudin
    Mar 17 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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