You're blindfolded, disoriented, and standing one mile from the Great Wall of China. How far do you have to walk to guarantee that you will run into the wall?

Assume that the wall is infinitely long and straight.

(In reply to re(3): Much shorter solution by Steve Herman)

I concede your point.  My masterful error occured because I did not draw this out.  (My physics professor would kill me if he knew.)  When calculating the return angle in my head, I wasn't paying attention to the location of the wall and using dead reckoning, I thought the 1, 1, 2, 2 would cross it, but this only succeeds in crossing the x axis in the worst case.  Below is the actual math used to verify your point, and sadly, I find it is not a shorter solution, but it is a good approximation, and even with rounding the figures up, you could dead reckon 1.5 miles for the first leg, 1.5 miles for the second leg, 3 miles for the third leg, and a final 1.5 miles for the final leg for a total of 7.5 miles.

I still think the golden spiral would minimize the distance, but I'm not so sure anymore.

The goal is to minimize the overall distance.  Since you don't know the direction of the wall, then you would have to travel at most 4 perpendicular directions to be sure to hit the wall.

Now, to minimize this damage if the first two directions are wrong, then we should have their legs be the same distance.  The worst case would be if the angle of the first leg was away from the wall towards the left. This would require the third leg to recover the distance back to the line parrallel to the wall passing through the starting point. Now the fourth leg would have to cover the distance from this point to the wall.

To illustrate, let's assume the wall is y=1, and the starting point is the origin.  Using this case, maximum distance would occur if you started heading towards the south east (quadrant IV).  Since the change in the y direction is the only important function, we need to minimize the following equations:

cos(theta)=-x/a
sin(theta)=-x/a

Given these two, (derived from trigonometric analysis), the only theta which would satisfy both is 45 degrees.  Therefore, theta must be 45 degrees.

Continuing:

cos(theta)=2x/b
sin(theta)=1/c

Given these, we know:

-x/a=2x/b
-1/a=2/b
-b=2a

So, ignoring the sign difference, which only indicates direction, we know that leg b must be twice the size of leg a, or in other words, the first leg and second leg combined must be the length of the third leg.

Finally, we know:

D(distance traveled)=2a+b+c

We also know that:

a*sin(45)>1, or failing that, then
b*sin(45)>1, or failing that, then
c*sin(45)>1

(Notice that the second leg will never be correct. :) )

So a>1/sin(45), b=2a, and c=1/sin(45).

Let a=1/sin(45)+1/infinity, b=2a, and c=1/sin(45),

Then the minimum distance needed is D=2/sin(45)+2/sin(45)+1/sin(45)+3/infinity.

Solving, we get D is just greater than 7.07 miles following this path:

Start out in any direction for 1/sin(45) miles, or roughly 1.41 miles.
Turn right 90 degrees and go another 1/sin(45) miles.
Turn right 90 degrees and go 2/sin(45) miles, or roughly, 2.83 miles.
Turn right 90 degrees and go 1/sin(45) miles, or roughly another 1.41 miles.

Posted by Joshua on 2011-09-03 03:36:29