1. ## Bear Problem

Hi - if anyone can help me with a particularly puzzling problem, I'd be eternally grateful...thanks...

***

You are out in a high grass, sparsely-treed, level wilderness, on an overcast summer's day, on a very important quest. Suddenly you startle a momma bear with cubs!!! HOLY MOLEY!!! She immediately attacks you! WHAM!!! WHAM!!!WHAM!!! Using current wisdom, you play dead, praying that it's not a rehearsal for the real thing. After an eternity of her beating and mauling you, she and her cubs disappear.

When you come to, all is quiet except your heart which is pounding like a mad drummer's tattoo. Bleeding profusely, you decide to clear out of there in a HURRY! The only thing you are certain of, is that just before you were attacked, you were beside that tree right there which is EXACTLY 1 kilometer from a perfectly STRAIGHT trail which will lead you to safety. You have no idea in which direction to start off. Fighting the very strong temptation to head off in all directions at once, you force yourself to calm down. You realize that you must get out as soon as possible, or bleed to death. The adrenelin coursing through your body makes your brain work at the speed of light and your thoughts become crystal clear.

You immediately devise an OPTIMAL geometric plan that will guarantee that you find the trail in the SHORTEST travelling distance from that tree compared to ANY other plan, even if you start off using the WORST possible choice of heading. There is no sun, or anything else, to guide you as to direction. You also know you won't see the trail until you are right on top of it.

As it happens, you DO choose the worst initial heading in following the optimal strategy, but your plan works and you manage to get to help just in time to save your life.

A further clue have been supplied:

- The geometry of the optimal path to follow is not an obvious one.The optimal path only requires you to travel along straight lines and along a portion of a circle. For any other plan, if your initial heading is the worst possible choice, then the travel distance to the trail will be greater than for the optimal plan.

***

Any ideas? Anyone recognize this problem from somewhere (Scientific American, for example), and can provide a link to a solution?

2. Originally Posted by capndaft
Hi - if anyone can help me with a particularly puzzling problem, I'd be eternally grateful...thanks...

***

You are out in a high grass, sparsely-treed, level wilderness, on an overcast summer's day, on a very important quest. Suddenly you startle a momma bear with cubs!!! HOLY MOLEY!!! She immediately attacks you! WHAM!!! WHAM!!!WHAM!!! Using current wisdom, you play dead, praying that it's not a rehearsal for the real thing. After an eternity of her beating and mauling you, she and her cubs disappear.

When you come to, all is quiet except your heart which is pounding like a mad drummer's tattoo. Bleeding profusely, you decide to clear out of there in a HURRY! The only thing you are certain of, is that just before you were attacked, you were beside that tree right there which is EXACTLY 1 kilometer from a perfectly STRAIGHT trail which will lead you to safety. You have no idea in which direction to start off. Fighting the very strong temptation to head off in all directions at once, you force yourself to calm down. You realize that you must get out as soon as possible, or bleed to death. The adrenelin coursing through your body makes your brain work at the speed of light and your thoughts become crystal clear.

You immediately devise an OPTIMAL geometric plan that will guarantee that you find the trail in the SHORTEST travelling distance from that tree compared to ANY other plan, even if you start off using the WORST possible choice of heading. There is no sun, or anything else, to guide you as to direction. You also know you won't see the trail until you are right on top of it.

As it happens, you DO choose the worst initial heading in following the optimal strategy, but your plan works and you manage to get to help just in time to save your life.

A further clue have been supplied:

- The geometry of the optimal path to follow is not an obvious one.The optimal path only requires you to travel along straight lines and along a portion of a circle. For any other plan, if your initial heading is the worst possible choice, then the travel distance to the trail will be greater than for the optimal plan.

***

Any ideas? Anyone recognize this problem from somewhere (Scientific American, for example), and can provide a link to a solution?
This is not a solution. Just a comment on the puzzle.

If I was mangled by Mama Bear that much, how come I can still estimate exactly 1 kilometer of distance in a field full of tall grasses and some trees?
How could I measure exactly the straight lines I'd travel and then add the accumulated distances that are effectively going outward, like radially, from where I was left for dead by Mama Bear?
Then how could I know how to travel along a portion of a circle that is supposed to be centered at the place where Mama Bear mauled me?
And due to the state I'm in, I cannot think for now many puzzling facts to add to those above.

One thing is sure though, Mama Bear did not like me. Whew, if she did, she could have hugged me! Then I wouldn't be asking these questions.

3. Originally Posted by capndaft
Hi - if anyone can help me with a particularly puzzling problem, I'd be eternally grateful...thanks...

***

You are out in a high grass, sparsely-treed, level wilderness, on an overcast summer's day, on a very important quest. Suddenly you startle a momma bear with cubs!!! HOLY MOLEY!!! She immediately attacks you! WHAM!!! WHAM!!!WHAM!!! Using current wisdom, you play dead, praying that it's not a rehearsal for the real thing. After an eternity of her beating and mauling you, she and her cubs disappear.

When you come to, all is quiet except your heart which is pounding like a mad drummer's tattoo. Bleeding profusely, you decide to clear out of there in a HURRY! The only thing you are certain of, is that just before you were attacked, you were beside that tree right there which is EXACTLY 1 kilometer from a perfectly STRAIGHT trail which will lead you to safety. You have no idea in which direction to start off. Fighting the very strong temptation to head off in all directions at once, you force yourself to calm down. You realize that you must get out as soon as possible, or bleed to death. The adrenelin coursing through your body makes your brain work at the speed of light and your thoughts become crystal clear.

You immediately devise an OPTIMAL geometric plan that will guarantee that you find the trail in the SHORTEST travelling distance from that tree compared to ANY other plan, even if you start off using the WORST possible choice of heading. There is no sun, or anything else, to guide you as to direction. You also know you won't see the trail until you are right on top of it.

As it happens, you DO choose the worst initial heading in following the optimal strategy, but your plan works and you manage to get to help just in time to save your life.

A further clue have been supplied:

- The geometry of the optimal path to follow is not an obvious one.The optimal path only requires you to travel along straight lines and along a portion of a circle. For any other plan, if your initial heading is the worst possible choice, then the travel distance to the trail will be greater than for the optimal plan.

***

Any ideas? Anyone recognize this problem from somewhere (Scientific American, for example), and can provide a link to a solution?
Well if we walk out radially a distance r and then walk in a circle centred on the tree the worst case distance walked is:

$\displaystyle d=r+2 \pi r - 2 r \arccos(1/r)$

which has a minimum near $\displaystyle r=1.0435$ km, with a worst case distance walked of $\displaystyle \approx 6.995$ km. This compares with a worst case of $\displaystyle \approx 7.28$ km if he walks out $\displaystyle 1$ km befor starting to circle.

RonL

4. Thanks for the answers, guys - I'll take a look and see how it works...

'ppreciate it...

5. Originally Posted by capndaft
Thanks for the answers, guys - I'll take a look and see how it works...

'ppreciate it...
Note: I am not claiming my solution is globally mininmum worst case distance, only subject to the constaints or a radial walk followed by a circle centred on the tree it is.

RonL

6. Originally Posted by CaptainBlack
Well if we walk out radially a distance r and then walk in a circle centred on the tree the worst case distance walked is:

$\displaystyle d=2 \pi r - 2 r \arccos(1/r)$

which has a minimum near $\displaystyle r=1.062$ km, with a worst case distance walked of $\displaystyle \approx 5.94$ km. This compares with a worst case of $\displaystyle \approx 6.28$ km if he walks out $\displaystyle 1$ km befor starting to circle.

RonL
I think you need an extra $\displaystyle r$. You need to include the walk out radially.

$\displaystyle d= r + 2 \pi r - 2 r \arccos(1/r)$

7. Originally Posted by meymathis
I think you need an extra $\displaystyle r$. You need to include the walk out radially.

$\displaystyle d= r + 2 \pi r - 2 r \arccos(1/r)$
Ops..

Of course, and so the minimum is near $\displaystyle r=1.0435$, and is $\displaystyle \approx 6.995$km.

Original post corrected.

RonL

8. After thinking about it, I don't think the line then circle approach is optimal (not that you claimed it would be). Here is the thought exercise, you walk out to 1.0435 km. Instead of walking along the circle go on either of the two straight lines which are tangents to the 1 km circle. You will quickly hit the inner circle. Then you will hit outer 1.0435 km circle. This will cover all of the same 1km circle's tangents that you would have if you had instead walked along the outer circle but you walked more efficiently. You can repeat this motion a total of n times where

$\displaystyle n = floor(2\pi/2\arccos(1/r))-1$

each segment length is $\displaystyle 2\sqrt(r^2-1)$ where $\displaystyle r$ is the distance out from the center that you walked initially. Note that I am calling a segment here the straight line along a tangent from the outer into the inner and back out to the outer circle.

So we have walked a total distance so far of:
$\displaystyle r + n*2\sqrt(r^2-1) \approx6.41$
but we still haven't touched all of the tangent lines. At this point if you walked the along the outer circle you would have shaved off some distance.

$\displaystyle r + n*2\sqrt(r^2-1)+ r(2*pi-(1+2n)\arccos(1/r)) \approx6.48$

There is probably a more efficient way of finishing it off rather than following the outer circle.

9. Also, this wasn't optimized. I just picked the r from the previous method discussed to show that we could do better.

10. Originally Posted by meymathis
Also, this wasn't optimized. I just picked the r from the previous method discussed to show that we could do better.
Well, it appears the solution is 3+7pi/6+1 = 6.3972, as can be seen at this link

Thanks for all the help - now if I could only get some idea of what that looks like plotted out... :-)

11. It would have been nice if they had actually said what the curve was.

Just as a guess, I wonder if the answer isn't this:

go out radially some distance R. Now walk back along one of two tangent lines to the 1 km circle, like what I has said, but once you hit the 1 km circle, you walk along it. Eventually you will hit the tangent line that you didn't take.

Just a guess.

12. Originally Posted by capndaft
Well, it appears the solution is 3+7pi/6+1 = 6.3972, as can be seen at this link

Thanks for all the help - now if I could only get some idea of what that looks like plotted out... :-)

Well at least if you can get access to the reference that it comes form:

[3] J. R. Isbell. An optimal search pattern. Naval Res. Logist. Quart., 4:357-359, 1957

RonL

13. Originally Posted by CaptainBlack
Well at least if you can get access to the reference that it comes form:

[3] J. R. Isbell. An optimal search pattern. Naval Res. Logist. Quart., 4:357-359, 1957

RonL
The attachment shows a description of the solution but not is proof.

This is from:

"Search Theory: Some Recent Developments" By David Chudnovsky (which can be found on Google Books)

RonL

14. Thanks RonL!

capndaft, I hope that was only an extra credit problem! For being such a "well known" problem, it sure seemed obscure to me. Google search for "sailor in the fog" didn't come up with except a few people saying it was well known.

15. My thanks to everyone who helped in this thread, from the prosed solutions to the final picture. Your answers are greatly appreciated.

Thank you.