0

Imagine you are on an (in)finite 2d-plane (and confined to walk on it). There's a straight line somewhere on the plane, but you don't know where it is and neither can you find it by looking from afar. You have to cross it! What's the best walking strategy to find the line in the least time possible?

Edited: As of @Brandon_J and @Adam answers which close the question for the infinite plane, please consider answering the best strategy for the finite plane case. (If it is not a good policy to edit the scope of the question this way, please edit it back.)

My attempt

  1. Choose a random direction and walk for a distance of $r$
  2. Walk now along the circle of radius $r$
  3. If after the full circle you haven't met the line, increase the distance from the starting point by another amount of $r$
  4. Walk along the circle of radius $2r$
  5. Repeat the procedure until you cross the line
Community
  • 1
Carlos
  • 101
  • 3
  • 1
    Is the straight line infinite in length? – Adam Feb 12 '19 at 15:35
  • @Adam Yes, it is! – Carlos Feb 12 '19 at 15:43
  • New concern. You clearly brought up an issue of starting position however you haven't included any information on this matter in the question. Can you clarify if it is random or from the centre etc. – Adam Feb 12 '19 at 16:42
  • @Adam We start on a random position, and the line is in a random position. You can even be "close" to the line, but you don't know where it is unless you walk past it. – Carlos Feb 12 '19 at 16:45
  • I edited the question to "least time possible" to avoid answers where one walks till the boundary of the plane (which might be really really far away) and then goes along the perimeter (as per @Adam solution). – Carlos Feb 12 '19 at 16:59
  • It is impossible to get a better solution than walking on the perimeter @Carlos. The reason why is that for a full solution (with probability 1 of finding the line) you eventually have to cover the area around the perimeter. Thus it is better to walk directly to the perimeter than to waste time covering the area that the perimeter already covers – Adam Feb 12 '19 at 17:07
  • @Adam Okay I see your point. But if I were to walk on this plane, since I wouldn't know if I would get alive before reaching the boundary and then walk on it, maybe I would set on straight line on a random direction and hope for the best. But that's a different problem: with a time constraint. – Carlos Feb 12 '19 at 17:16
  • even with a time restraint, the only way to definitely find the line would be to walk to - then cover the perimeter. Randomness wouldn't help if the plane was very large either because it would most likely take a longer amount of time to find the line in most cases. Why? This is because you would still be searching for the line on the way to the perimeter. Yes, when you get to the perimeter you would cover that area again at some point but that is way better than randomly retracing steps or randomly missing the line and it is already certain to find the line – Adam Feb 12 '19 at 17:43
  • Anyway @Carlos if this relates to a real problem you should consider asking a new question with the full details of the problem – Adam Feb 12 '19 at 17:56
  • With a time constraint you might never find the line with your approach, that is, if the boundary is too far away you might run out of time before reaching it (plus you still have to walk along it). While if you choose, for instance, the procedure I've outlined above (or the spiral way) you have a better change of finding the line before the time is up. Of course this last procedure is better if the line is reasonably close to you. – Carlos Feb 12 '19 at 17:56
  • Didn't we have a similar puzzle before? Something to do with an astronaut and a space station? – Dr Xorile Feb 13 '19 at 15:44
  • @DrXorile Can you be more specific or add a reference? I'd like to hear about it. – Carlos Feb 13 '19 at 15:50
  • Oh, yes. I found it. I was the one who asked it. LOL. I had completely forgotten that. Disoriented near a space station. It was inspired by a 2D version. – Dr Xorile Feb 13 '19 at 16:18
  • Here's the original Disoriented near the great wall of china – Dr Xorile Feb 13 '19 at 16:20
  • Yep, this seems about right. With the constraint of knowing the line/wall is a given distance away, the problem becomes better posed. Thank you @DrXorile. – Carlos Feb 13 '19 at 19:23

2 Answers2

3

I would recommend walking in a

spiral shape, somewhat like so: Spiral

This way you won't miss the line, and you'll eventually cover the entire plane if

You're given infinite time. You're not, and in searching an infinite plane for a line the odds are infinitely against you.

While my solution is possibly better than your solution, both of your solutions will likely

NEVER WORK. Ever. It's an infinite plane. Walk a million miles and you haven't begun to cover one-millionth of the plane in your search. Walk a billion miles and you haven't covered a billionth of the plane. Walk a trillion miles and you haven't even covered a trillionth of the plane - you aren't ever making actual progress.

Brandon_J
  • 9,307
  • 1
  • 16
  • 67
  • Indeed, infinite plane was definitely too much to ask for! There's no optimal solution, of course. I had thought about the spiral solution, but depending on how you choose the spiral parameters you might end up walking more distance to obtain the same information, isn't it? – Carlos Feb 12 '19 at 15:49
  • spoiler. If you follow an exponential spiral, the distance you will have to travel is proportional to the distance from your starting point to the line. If you follow a linear spiral, the distance you'd have to travel is proportional to the square of the distance to the line. – user3294068 Feb 13 '19 at 20:04
2

For the finite plane

A great solution is

Walk along the perimeter of the plane

Why?

The line you are looking for is infinite in length however it must pass through a finite plane so it must cross the perimeter!

Adam
  • 2,907
  • 1
  • 13
  • 36
  • This is certainly not an optimal solution, as the boundary of the plane might be very far away from your starting point. Can we do better? – Carlos Feb 12 '19 at 16:17
  • You litterally can't walk on the perimeter of the plan because it's infinite. – Rémi Henry Feb 12 '19 at 16:19
  • He added a finite plane problem. Also @Carlos I think that Adam's answer here (for the finite plane, not the infinite plane) is optimal, or at least is the only way to guarantee that you find the line. – Brandon_J Feb 12 '19 at 16:31
  • @Brandon_J It is indeed a way with probability 1 of finding the line; but maybe there's another way with probability as close to 1 to find the line with less travelled distance. Would random walk work? – Carlos Feb 12 '19 at 16:41
  • Could you define "random"? @Carlos – Brandon_J Feb 12 '19 at 16:58
  • @Brandon_J At any point you choose randomly out of 360 possible angle directions (with equal probability of 1/360) and walk for a certain distance. This is what random in "random walk" means. In a simpler manner, one could just consider 4 equally likely random direction (North, South, East, West). – Carlos Feb 12 '19 at 17:05
  • Random walk is guaranteed to have a solution, but it's definitely not optimal. – Carlos Feb 12 '19 at 17:06
  • 1
    That's not going to cover very much ground at all...and it isn't guaranteed to find a solution. – Brandon_J Feb 12 '19 at 17:06
  • Im now convinced that this is the best possible solution to this case. Any better solution would have to presume that you can "walk on air". Random solutions won't work at all since you eventually have to cover the perimeter to 'hit' every possible line. – Adam Feb 12 '19 at 17:13
  • rot13(vs gur svavgr cynar vf na a-tba, lbh bayl unir gb jnyx nybat a-1 fvqrf bs gur crevzrgre... naq pubbfr gur ybatrfg fvqr gb abg jnyx. Vs vgf pvephyne, lbh'er bhg bs yhpx, jnyx gur jubyr pvephzsrerapr. ) – SteveV Feb 12 '19 at 18:25
  • @SteveV rot13(url, lbh ner evtug! Ubjrire guvf qrcraqf ba jurer lbh vavgvnyyl raq hc ba gur crevzrgre naq rira gura lbh znl abg trg gur pubvpr gb fxvc gur ybatrfg fvqr nf jr pnaabg onpxgenpx. Guvf fbyhgvba raqf jura gur yvar vf sbhaq fb jr pna fnsryl nffhzr gung ng yrnfg bar fvqr yratgu jvyy or fxvccrq naljnl! Vyy or tynq gb vapbecbengr guvf vagb zl nafjre vs lbh jnag fb gung jr unir n pbzcyrgr fbyhgvba) – Adam Feb 12 '19 at 18:43