Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

You are blindfolded and disoriented, standing exactly 1 mile from the Great Wall of China. How far must you walk to find the wall?

Assume the earth is flat and the Great Wall is infinitely long and straight.

share|improve this question
3  
I've seen an equivalent question before involving a swimmer or fisherman who is lost at sea and needs to find the shore. – f'' Jan 19 at 7:01
8  
do you know you are exactly away 1 miles from the Great wall? – Oray Jan 19 at 7:25
5  
How capable are we at moving? Can I walk in a straight line for a half mile and know that I've walked a half mile? Am I able to rotate to within the degree? – Carl Jan 19 at 12:14
4  
if the lateral thinking tag was here people would go ham and throw random stuff like : take off what blinds you and rush to the wall... Let lateral away from that post :D – RiddlerNewComer Jan 19 at 13:49
6  
In the end, the researchers concluded, without any gadgetry, visual cues or other directional aids, humans have trouble moving too far from where they started. “[O]n average, people will not travel more than 330 feet (100 meters) from their starting point when using only body cues to guide their walking direction, regardless of how long they walk,” they write. “Without the use of an external directional reference, humans (like any animal) are not able to maintain a fixed course.” (healthland.time.com/2009/08/21) - a very cruel puzzle. – rumtscho Jan 19 at 17:36
up vote 30 down vote accepted

$\DeclareMathOperator{\arcsec}{arcsec}$

For each possible orientation of the wall (relative to some arbitrary initial orientation), the point on the wall closest to our starting point is a distance $1$ away. The collection of the closest points for all possible orientations of the wall form a circle of radius $1$ around our starting point.

If we move a distance $r>1$ away from the initial point, we intersect two orientations of the wall that are an angle $\theta$ apart. In order to reach that point we must have crossed all of the orientations in that angle. In the figure below on the left, those "explored" points are marked by a magenta line.

enter image description here

By trigonometry we can show that $\theta = 2\arcsec r$. If we traverse the path shown on the right side of the above figure, we travel a worst-case distance of:

$$ r + r(2\pi - \theta) \\ r + 2r(\pi - \arcsec r) $$

This distance is minimized when $r\approx 1.04356$ for a worst-case distance of $6.99528$, an improvement of about $3.95\%$

However, looking at the figure we can immediately see that the majority of the large circular arc is "wasted" distance. Only the ends contribute to additional "explored" points. If we shrink-wrap the rest of the path around the unit circle, we get the following path:

enter image description here

The worst-case distance of this path is:

$$ r + 2\sqrt{r^2-1} + (2\pi - 2\theta) \\ r + 2\left(\sqrt{r^2-1} + \pi - 2\arcsec r\right) $$

This happens to be minimized for $r = \sqrt{\frac{15-\sqrt{33}}{6}} \approx 1.24200$ (not the distance shown in the figure), for a worst-case distance of:

$$ \sqrt{\frac{9+\sqrt{33}}{2}}+4\arctan \sqrt{\frac{9+\sqrt{33}}{8}} \approx 6.45891 $$

an improvement of $11.32\%$.

Update

Thanks to Michael Seifert for pointing out that we can do better by letting the radii of the start and end be different, in which case we have the distance:

$$ r_1 + \sqrt{r_1^2-1} + \sqrt{r_2^2-1} + 2\pi - \theta_1 - \theta_2 \\ r_1 + \sqrt{r_1^2-1} + \sqrt{r_2^2-1} + 2\pi - \arcsec r_1 - \arcsec r_2 $$

Which is minimized by $r_1=2/\sqrt{3},\ r_2=\sqrt{2}$ (with $\theta_1=\pi/3,\ \theta_2=\pi/2$):

enter image description here

(Because of the nice angles, this picture is exactly to scale.) The worst-case distance here is simply

$$ \frac{2}{\sqrt{3}} + \frac{1}{\sqrt{3}} + \frac{2\pi}{3} + \frac{\pi}{2} + 1 \\ = 1 + \sqrt{3} + \frac{7\pi}{6} $$

(a $12.16\%$ improvement.)

share|improve this answer
    
This is excellent. I was about to start working on other angles, but see you've done it already. Slightly surprising – Dr Xorile Jan 19 at 18:34
1  
This can be further improved by allowing the distance you initially walk away from the origin (call it $r_1$) to be different from your final distance from the origin (call it $r_2$.) The total distance is then $r_1 + \sqrt{r_1^2 - 1} + \sqrt{r_2^2 - 1} + 2\pi - 2 \arcsec r_1 - 2 \arcsec r_2$, which is minimized when $r_1 = 2/\sqrt{3}$ and $r_2 = \sqrt{2}$. Total distance traveled is $1 + \sqrt{3} + 7 \pi/6 \approx 6.39724.$ – Michael Seifert Jan 19 at 18:39
    
@MichaelSeifert I don't follow. At which point do you deviate from the path in the shrink-wrap diagram? – SpiritFryer Jan 19 at 18:44
4  
According to this paper (see page 650), it was proved in 1980 here (written in French). – f'' Jan 19 at 21:59
3  
@MichaelSeifert My friend graciously posted his solution on his webpage. – dshin Jan 19 at 22:30

If the angle between the possible wall and the initial line is $x$ (the angle between the diagonal line and the bottom line in the diagram below), then the distance travelled is $1+(\pi/2+2x)+1/tan(x)+1/sin(x)$.

Gratifyingly this gives a slightly improved answer of $2+3\pi/2\approx6.7124$ for my first attempt (because you can drop down straight rather than complete the circle), where $x=\pi/2$.

It also gives my second attempt for $x=\pi/4$ (answer $2+\sqrt{2}+\pi\approx6.5558$).

Throwing the expression into wolfram alpha, shows that a minimum occurs at $\pi/3$. This gives a value of $1+\sqrt{3}+7\pi/6\approx6.397$


Old new upper bound: $2+\sqrt{2}+\pi$ as per diagram:

Walk near the wall


(Old upper bound: $2\pi+1$ miles. Walk 1 mile in any direction and then walk is a circle of radius 1, centred at your starting point. )

share|improve this answer
5  
You can save a bit by walking straight one unit instead of the last quarter circle. – xnor Jan 19 at 11:03
3  
Would someone who's blindfolded (or even not) be able to walk in a perfect circle with such a huge radius? I'm not sure if this is in the scope of the question, though. – dpwilson Jan 19 at 12:45
    
there is shorter upper bound – Oray Jan 19 at 12:58
1  
@dpwilson - I suppose the blinfolded person could be standing next to a metal stake firmly anchored into the ground with a very light and strong rope/cord attached to it that measures exactly 1 mile. (or he could have that in a backpack and attach it himself) - from there he could use that to precisely walk in a circle around the stake with only a slight margin of error, provided he constantly keeps his weight against the cord to keep it from dragging on the ground. – Spacemonkey Jan 19 at 15:35
1  
I think it's intended that the person has perfect control over their walking, otherwise there is no solution you can propose that doesn't introduce margins of error based on the person's ability. Can you walk exactly one mile, can you turn exactly N degrees, can you even walk in a perfectly straight line? – Ninety-Three Jan 19 at 16:24

I would like to present this non-rigorous but hopefully more intuitive explanation for the optimal path. (The technique used here was very helpful for working on Oray's variant with two people.)

The first part of 2012rcampion's answer explains that we should go as far out as some tangent $l$, before going around the circle to get back to $l$ on the other side. Call the starting point $A$ and the circle $O$. Then the problem is this:

Find the shortest path that comes from $A$, touches $l$, then goes around the circle and touches $l$ again.

It won't change which path is shortest if we turn around at the end and go all the way back:

Find the shortest path that comes from $A$, touches $l$, then goes around the circle and touches $l$ again, and then goes back around the circle to $l$ and then $A$.

Now, if we reflect the entire diagram over $l$, we get this:

1]

Instead of having our path touch $l$ and go back, we can have it switch sides every time instead, which won't change the length because it's just a reflection. So now the problem is this:

Find the shortest path from point $A$ that goes around circle $O^\prime$, then around circle $O$, then goes to point $A^\prime$.

Anyone should be able to do that (imagine putting a string from $A$ around the circles to $A^\prime$ and pulling it tight):

2]

And now if we only look at the part of the diagram above $l$, there's the answer without any calculations.

share|improve this answer

"...standing exactly 1 mile from the Great Wall of China. How far must you walk to find the wall?"

You must walk 1 mile. If you go the wrong way then you will end up walking further. If you don't walk that far you can't reach it.

share|improve this answer
    
A sock drawer contains 5 pairs of sockets. How many socks must you pull out to get a matching pair? – dshin Jan 19 at 20:58
    
@TracyCramer must is intended in the sense of what is the distance you must travel to be sure you reached the wall – njzk2 Jan 20 at 0:04
4  
@dshin why do you keep so many sockets opened my good man? You should clean up after your code that keeps socket connections opened – Patrice Jan 20 at 1:26
    
@njzk2 - I understand and accept that it's not the answer he was looking for - I answered somewhat in jest but didn't expect down votes for justified, accurate but not accepted answer. ;) I'll delete if more people object. – Tracy Cramer Jan 20 at 2:10
1  
@dshin: Two, all mine are currently the same – Mark K Cowan Jan 20 at 20:37

@DrXorile is clos to the answer. Mine isn't an answer either but here's some food for thoughts

I wanted to picture it. It looks like it.

If we take 360 individuals, all starting at the center of the circle and each at a different angle, only one will find the wall.

That's a 0.27% chance of finding the wall if you walk eaxtly one mile. If you need to reach the wall for your survival, you're dead.

Also imagine the guy who started just one degree slightly off, extend his hands and the wall is just 2 inches further, then starts over in the wrong direction.

enter image description here

Walking more than one mile means we could increase our chances of reaching the wall at slightly off angle.

enter image description here

But then again, this could happen:

enter image description here

share|improve this answer
1  
they could all miss the wall. to guarantee a hit you'd technically need infinite individuals – Slepz Jan 19 at 16:36
    
@Slepz you mean if they were to pick an angle at random or if they each pick one angle? – Nicolas de Fontenay Jan 19 at 16:40
1  
no I mean a circle is actually just an infinite number of points radius distance from the centre. We arbitrarily divide it into 360 degrees, but since a line tangent to a circle only touches at one point out of the infinite points you'd need infinite people. your .27% chance should be 0% because 360 / infinity = 0 – Slepz Jan 19 at 16:44
    
@Slepz I had a feeling you were talking about the circle definition ^^. You're right but humans aren't infinitely small though. So our arbitrary degree measurement should do the job for this. – Nicolas de Fontenay Jan 19 at 16:45
    
if we're going with real world, pi miles / average human arm span would be the probability. which is about 1/2000 or 0.05% – Slepz Jan 19 at 17:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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