From: karr@cs.cornell.edu (David Karr)
Newsgroups: rec.puzzles
Subject: Re: ducks and foxes (SPOILER)
Keywords: ducks, foxes
Date: 14 Aug 92 15:04:59 GMT
Organization: Cornell Univ. CS Dept, Ithaca NY 14853

In article <1992Aug14.043132.27119@cco.caltech.edu> keith@cco.caltech.edu (Keith Allan Schneider) writes:
>dwr2560@zeus.tamu.edu (RING, DAVID WAYNE) writes:
>[...]
>>4 should have been an a, but the fox still can't catch the duck (if the duck
>>is clever! )
>
>Well, we were assuming that both the fox and the duck use the best strategy
>possible, and that their reaction times were instantaneous...

You were also assuming that the strategy YOU analyzed IS the best one
possible.  Think about it!  Or read on ...



<SPOILER> ahead ...



Assume the ratio of the fox's speed to the ducks is a, and the radius
of the pond is r.  Strategy S1 is for the duck to swim to a point on
the concentric circle of radius r/a diametrically opposite the fox,
then head out in a radial direction until she reaches the side.  It
has been shown that the duck can then escape if a < 1 + pi.

But there is a better strategy S2 that allows the duck to escape for
some values of a > 1 + pi.

The steps of strategy S2 (from the duck's perspective) are as follows:

1.  Swim around a circle of radius (r/a - delta) concentric with the
pond until you are diametrically opposite the fox (you, the fox, and
the center of the pond are collinear).

2.  Swim a distance delta along a radial line toward the bank opposite
the fox.

3.  Observe which way the fox has started to run around the circle.
Turn at a RIGHT ANGLE in the opposite direction (i.e. if you started
swimming due south in step 2 and the fox started running to the east,
i.e. clockwise around the pond, then start swimming due west).  (Note:
If at the beginning of step 3 the fox is still in the same location as
at the start of step 2, i.e.  directly opposite you, repeat step 2
instead of turning.)

4.  While on your new course, keep track of the fox.  If the fox slows
down or reverses direction, so that you again become diametrically
opposite the fox, go back to step 2.  Otherwise continue in a straight
line until you reach the bank.

5.  Fly away.

The duck should make delta as small as necessary in order to be able
to escape the fox.

The key to this strategy is that the duck initially follows strategy S1
(radial path away from the fox) until the fox commits to running either
clockwise or counterclockwise around the pond.  The duck then turns onto
a new course that intersects the circle at a point MORE than halfway
around the circle from the fox's starting position.  In fact, the duck
swims along a tangent of the circle of radius r/a.  Let 

  theta = arc cos (1/a)

then the duck swims a path of length

  r sin theta + delta

but the fox has to run a path of length

  r*(pi + theta) - a*delta

around the circle.  In the limit as delta goes to 0, the duck will
escape as long as

  r*(pi + theta) < a*r sin theta

that is,

  pi + arc cos (1/a) - a * sqrt(a^2 - 1) < 0

Now we need to maximize a in the above.  I don't expect a closed-form
solution, but numerically the solution is just a little bit greater
than 4.6 .  So if the duck swims 5 mph, she can escape a fox that runs
23 mph -- with very little room to spare.

"But wait," I hear you cry, "When the duck heads off to that spot
'more than halfway' around the circle, why doesn't the fox just double
back?  That way he'll reach that spot much quicker."  That is why the
duck's strategy has instructions to repeat step 2 under certain
circumstances.  Note that at the end of step 2, if the fox has started
to run to head off the duck, say in a clockwise direction, he and the
duck are now on the same side of some diameter of the circle.  This
continues to be true as long as both travel along their chosen paths
at full speed.  But if the fox were now to try to reach the duck's
destination in a counterclockwise direction, then at some instant he
and the duck must be on a diameter of the pond.  At that instant, they
have exactly returned to the situation that existed at the end of step
1, except that the duck is a little closer to the edge than she was
before.  That's why the duck always repeats step 2 if the fox is ever
diametrically opposite her.  Then the fox must commit again to go one
way or the other.  Every time the fox fails to commit, or reverses his
commitment, the duck gets a distance delta closer to the edge.  This
is a losing strategy for the fox.

If anyone would care to produce a more precise value of the maximum a
for which this strategy works for the duck, go ahead.  You might find
it easier to solve for theta in the equation

  pi + theta - tan theta = 0

where theta is approximately 1.35 (remember to use radians, not
degrees :-).

-- David Karr (karr@cs.cornell.edu)