36
$\begingroup$

So the puzzle is like this:

An ant is out from its nest searching for food. It travels in a straight line from its nest. After this ant gets 40 ft away from the nest, suddenly a rain starts to pour and washes away all its scent trail. This ant has the strength of traveling 280 ft more then it will starve to death. Suppose this ant's nest is a huge wall and this ant can travel in a whatever curve it wants, how can this ant find its way back?

I interpret it as: I start at the origin. I know that there is a straight line with distance 40 ft to the origin, but I don't know the direction. In what parametric curve I will sure hit the line when the parameter $t$ is increasing, while the total arc length is less than or equal to 280 ft.

I asked a friend of mine who is a PhD in math, he told me this is a calculus of variation problem. I wonder if I could use basic calculus stuff to solve this puzzle (I have learned ODE as well). My hunch tells me that a spiral should be used as the path, yet I am not sure what kind of spiral to use here. Any hint shall be appreciated. Thanks dudes!

Clarification by dfeuer

As some people seem to be having trouble understanding the problem description, I'll add an equivalent one that should be clear:

Starting in the center of a circle of radius 40 ft, draw a path with the shortest possible length that intersects every line that is tangent to the circle.

$\endgroup$
6
  • $\begingroup$ For all intents-and-purposes, the ant nest intersects tangentially anywhere on a circle of radius 40ft from the current position of the ant. Then the naive solution would be to walk out 40ft to an arbitrary point and then traverse the circumference of the circle. However, this uses at worst 40+2\cdot \pi 40 ft which slightly exceeds 280ft. Try to somehow cover more ground, perhaps by stepping outside the circle. $\endgroup$
    – Alex R.
    Commented Dec 12, 2013 at 23:47
  • 1
    $\begingroup$ A lesson from the two current answers: while intuition may suggest spiraling out, you actually want to spend as much time as possible far from your starting position, so whatever you do, the first step should be to travel at lease 40ft in a straight line. $\endgroup$
    – dfeuer
    Commented Dec 13, 2013 at 0:30
  • $\begingroup$ I'm so confused on what the question is asking. So the ant travels in some unknown direction for 40 ft in a straight line from the origin. Then what? $\endgroup$
    – Shahar
    Commented Dec 15, 2013 at 1:20
  • $\begingroup$ @dfeuer Is it okay if I use a software to solve it or do I need to show steps? $\endgroup$
    – Shahar
    Commented Dec 15, 2013 at 1:37
  • 1
    $\begingroup$ By the way, this is not a calculus-of-variations problem. $\endgroup$
    – TonyK
    Commented Dec 15, 2013 at 21:42

5 Answers 5

36
+100
$\begingroup$

Historical summary

It is the famous problem invented by R. Bellman in 1956 [1]. It is known as 'Lost in a Forest Problem':

What is the best path to follow in order to escape a forest of known shape and dimensions?

The subproblem for the half-plane forest with known distance from the boundary was solved by J. R. Isbell in 1957 [2]. He described the path with the length

$$\left(\sqrt{3}+\frac{7\pi}{6}+1\right)d$$

where $d$ is the distance from the boundary of the forest. He gave the proof in outline that his path had minimal length. The complete and detailed proof was given by H. Joris in 1980 [3]. The consideration about this problem can also be found in the book [4].

The overview of the results on the general problem up to 2004 can be found in [5].

Isbell's path

The form of the shortest path:

The shortest path

As @Will Nelson wrote the shortest path consists of the 3 line segments with lengths $\frac{2}{\sqrt{3}}d$, $\frac{1}{\sqrt{3}}d$ and $d$ and the arc of the circle with radius $d$ which subtends the angle $\frac{7\pi}{6}$. The total length of the path is

$$L_{\min}(d)=\frac{2}{\sqrt{3}}d+\frac{1}{\sqrt{3}}d+\frac{7\pi}{6}d+d=\left(\sqrt{3}+\frac{7\pi}{6}+1\right)d\approx 6.397d$$

In our case $d=40$ so $L_{\min}\approx 255.890<280$. The ant can survive!

References

  1. R. Bellman, Minimization Problem, Bull. Amer. Math. Soc. 62 (1956) p. 270. [Available online at the AMS BAMS archive, free of charge.]

  2. J. R. Isbell, An optimal search pattern, Naval Res. Logist. Quart. 4 (1957) pp. 357-359. [Available online at Wiley Online Library, 35$ cost.]

  3. H. Joris, Le chasseur perdu dans la foret, Elem. Math. 35 (1980) pp. 1-14. [Available online at the site of École polytechnique fédérale de Lausanne, free of charge.]

  4. Z. A. Melzak, Companion to Concrete Mathematics: Mathematical Techniques and Various Applications, Wiley, New York, 1973, pp. 150-153. [I couldn't find this book online. According to @Barry Cipra Google Books let some users see a big chunk of this book with relevant pages.]

  5. S. R. Finch and J. E. Wetzel, Lost in a Forest, American Mathematical Monthly 111 (2004) pp. 645-654. [Available online at the site of Mathematical Association of America, free of charge.]

Update: Some references were added.

$\endgroup$
13
  • $\begingroup$ I am interested in the optimality proof, will need to visit the local math. library tomorrow... $\endgroup$
    – copper.hat
    Commented Dec 15, 2013 at 19:19
  • $\begingroup$ @copper.hat Unfortunately I couldn't find the original Bellman article in the Internet, only the later works of other authors and the review papers. Should I add references to some papers reviewing results received on this problem? $\endgroup$ Commented Dec 15, 2013 at 19:28
  • $\begingroup$ The references you gave look sufficient to me... $\endgroup$
    – copper.hat
    Commented Dec 15, 2013 at 20:12
  • $\begingroup$ @copper.hat I've added one overview paper. $\endgroup$ Commented Dec 15, 2013 at 21:50
  • $\begingroup$ @copper.hat It looks like that original Isbell's paper doesn't contain the rigorous proof of the minimality. I've added the reference to the article where possibly can be found the complete proof, but sadly it is in French... $\endgroup$ Commented Dec 16, 2013 at 19:17
17
$\begingroup$

Rescale so that radius $R=1$. Assume the starting point (the center of the circle) is at $(0,0)$. Unless I've made a calculation error (I don't think so), the minimum is achieved with the following path:

  • Straight line from $(0,0)$ to $\left(\frac{\sqrt{3}}{3},-1\right)$.

  • Straight line from $\left(\frac{\sqrt{3}}{3},-1\right)$ to $\left(\frac{\sqrt{3}}{2},-\frac{1}{2}\right)$.

  • Follow the circular arc counterclockwise about center $(0,0)$ from $\left(\frac{\sqrt{3}}{2},-\frac{1}{2}\right)$ to $(-1,0)$.

  • Straight line from $(-1,0)$ to $(-1,-1)$.

The length of each of these subpaths is $\frac{2}{3}\sqrt{3}$, $\frac{1}{3}\sqrt{3}$, $\frac{7}{6}\pi$, and $1$. The total length is $$ \frac{7}{6}\pi + \sqrt{3} + 1 $$ or for R=40, $$ 40\left(\frac{7}{6}\pi + \sqrt{3} + 1\right) \approx 255.89. $$

I'll try to sketch a proof of this when I get a chance.


UPDATE: I'll begin to sketch a proof. Consider the unit circle $C$ centered at the origin in $\mathbb{R}^2$. Consider the line $l$ tangent to $C$ defined by $y=-1$. Fix two points $(x_+,-1)$ and $(x_-,-1)$ on $l$ such that $x_+\ge 0$ and $x_-\le 0$. Suppose $\Gamma$ is a path from $(x_+,-)$ to $(x_-,-1)$ such that the convex hull of $\Gamma$ includes $C$. Let $\Gamma'$ be any path from $(0,0)$ to $(x_+,-1)$ and then along $\Gamma$ to $(x_-,-1)$. Observe that $\Gamma'$ is an admissible solution to the problem, i.e., all tangent lines of $C$ intersect $\Gamma'$.

It turns out that the optimal solution to the problem must be such a path $\Gamma'$. That's the hard part of the proof, but it's intuitively quite clear if you think about it. And it's not hard to find the minimum length $\Gamma'$. To do so, fix $x_-\le 0$ and $x_+\ge 0$, then solve for the minimum length $\Gamma'$ with these values for $x_-$ and $x_+$. Then vary $x_-$ and $x_+$ to solve for the minimum length path overall. The minimum length $\Gamma'$ for fixed $x_-$ and $x_+$ is easy to find.

More details when I get a chance.

$\endgroup$
0
4
$\begingroup$

The envelope of the walls sweeps out a circle of radius $40$. Here's one possible method to find the wall (i.e. a path which intersects every tangent of the circle). From the origin, walk to $(0,40)$. Now walk counter-clockwise around the circle three-quarters of the way to $(40,0)$. Now walk vertically upwards to $(40,40)$. All in all you've travelled $40 + \frac{3}{2}\pi 40 + 40 \approx 268.5$ ft.

$\endgroup$
4
$\begingroup$

This is only a partial proof and it is intended only as an illustration of my comment to @copper.hat - a full proof seems already be given the other answer...

I'm not sure with the second part: The second part is, that we assume , the minimal path ends with a path walking on the circumference of the circle and finally on the vertical line down to the horizontal "wall-shaped nest"; this means the upper half circumference ( $p_4=r \cdot \pi$ ) and one radius ( $p_5 = r \cdot 1$ ) are assumed to be the minimal trailing path after the leading part has been done and thus is fixed to the length $p_4+p_5 = r \cdot (\pi+1)$ where $r=40$ is the radius.

The initial part of the path is then the variable part of the problem.
The ant has to go down to the wall with some angle $\varphi$ which is the first part of the path ( $=p_1$ ) , then it has to go back to the circumference ( second part $p_2$ ) , and walk on the circumference to the position $\pi/2$ on the circumference which is the end of the first quadrant (third part $p_3$ ).

  1. Obviously that part on the circumference is $p_3=r\cdot (\pi/2-2\varphi)$
  2. The part $p_1$ depends on the angle $\varphi$: $p_1 = r \cdot {1 \over\cos(\varphi)}$ and
  3. the part $p_2$ is $ p_2 = p_1 \cdot \sin(\varphi)$

So th variable part of the ant's path is $f(\varphi) = p_1 + p_2 + p_3 = r\cdot \left({1+\sin{\varphi}\over \cos\varphi} + \pi/2 - 2 \varphi \right) $ and for this a minimizing expression can be given: $ {d \over d \varphi} f(\varphi) = r \cdot \left({\sin^2 \varphi+\sin \varphi\over \cos^2 \varphi}-1\right) $ and the solution occurs indeed as $\varphi = 2 \pi/12 = 30°$ which is the half angle of the hexagon.

However, this is not yet the full proof; perhaps there is a somehow fractal path crossing the circumference to the inside of the circle, do some shortcut there and proceed - it must be shown, that there is indeed no shorter path for this part.

instructive picture

$\endgroup$
3
$\begingroup$

Here is a slightly shorter solution:

enter image description here

$40(\sqrt{2}+1 + \pi +1) \approx 262.2$.

$\endgroup$
10
  • 2
    $\begingroup$ Is this optimal? An optimality proof of any solution will buy a small bounty. $\endgroup$
    – dfeuer
    Commented Dec 13, 2013 at 0:33
  • $\begingroup$ @dfeuer: A good question. I am having a little difficult characterising solutions in a convenient way. $\endgroup$
    – copper.hat
    Commented Dec 13, 2013 at 0:34
  • $\begingroup$ @dfeuer: So far I have not been able to show that there is a minimum. $\endgroup$
    – copper.hat
    Commented Dec 14, 2013 at 19:38
  • $\begingroup$ There's a sort of lightning rod effect of points outside the circle, where knowing that the path reaches that point implies that if you draw the tangents from that point, the path intersects all the tangents that touch the circle between the points where those tangents do. I believe this constrains the shapes the path can take outside the circle, but I'm not sure just how. $\endgroup$
    – dfeuer
    Commented Dec 14, 2013 at 21:37
  • $\begingroup$ @dfeuer: Assuming there is an optimizing solution, it must be rotation invariant (around the starting point), so the solution as such is not unique. I suspect that the path to showing that a minimizer exists will lead to a useful characterization. $\endgroup$
    – copper.hat
    Commented Dec 15, 2013 at 0:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .