wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Lost in the Woods, Again
        
(Message started by: SMQ on Aug 15^th, 2007, 8:13am)

Title: Lost in the Woods, Again
Post by SMQ on Aug 15^th, 2007, 8:13am

We've seen the setup (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1143054255) (and similar (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1185387676) ones (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1144965993)) before: you find yourself lost in the woods. You know that you are exactly halfway between two long, parallel roads which are two miles apart, but you don't know what direction you're facing. Due to darkness and fog you will only be able to find a road when you're very near it.

You know from your previous experience (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1143054255#16) that there's a pattern you can follow to ensure that you come to a road before walking more than about 3¹/₄ miles, but you can't remember the details so you settle on a simpler plan: you'll walk a certain distance, then, if you haven't found a road, make a right-angle turn and continue walking until you're out.

What distance should you plan to walk before turning in order to minimize 1) the worst-case distance, or 2) the expected distance you'll walk before finding one of the roads?

--SMQ

Title: Re: Lost in the Woods, Again
Post by mikedagr8 on Aug 15^th, 2007, 5:12pm

Yay, nice puzzle. Since it links over to the previous puzzle, for a start 1.1 miles :P

Seriously though, sqrt(2) miles (45 degree angle, so just go straight. I am thinking about phythagoras, and i'm not very good at explaining my thought progress in words), then continue untill you find the road. Also wait until it's day time so you can have better visability.

That's my 10 second mathematics there.

Title: Re: Lost in the Woods, Again
Post by Grimbal on Aug 16^th, 2007, 12:54am

For the worst case, I would walk [hide]1.608540[/hide] before turning,
for a worst-case distance of [hide]4.161938
[/hide]
But it is a numerical optimization. I don't have an exact formula.

Title: Re: Lost in the Woods, Again
Post by SMQ on Aug 16^th, 2007, 6:58am

I should maybe bump this over to Meduim. I put it in Easy because I thought it was a simple optimization problem -- a bit of number crunching but no real insight required -- but looking a little deeper it seems that mostly by luck I chose a particularly simplifying parameterization. So there's a hint: with the right parameterization the first part is almost trivial.

The second part is definitely Medium either way. I have a simple equation of which the optimal distance is a solution, but I haven't yet been able to wrangle a closed-form solution out of it (although I do know the numerical answer).

--SMQ

Title: Re: Lost in the Woods, Again
Post by Grimbal on Aug 16^th, 2007, 8:50am

OK, I got it
[hide]
You should turn after (2^(2/3)+1)^(1/2)
for a worst distance of (2^(2/3)+1)^(3/2)
[/hide]

Title: Re: Lost in the Woods, Again
Post by SMQ on Aug 17^th, 2007, 10:07am

Aye, that's what I have as well. Any thoughts on the expected distance version? ;)

--SMQ

Title: Re: Lost in the Woods, Again
Post by Grimbal on Aug 17^th, 2007, 3:32pm

Ouch!. That would involve an integral of trigonometric functions. I always hated these...