ducks and foxes
GENE SIMON HUH
I don't think that this one is in the FAQ; please don't flame me too much
if it is. I heard it a while ago on a bus somewhere.
A duck is swimming about in a circular pond. A ravenous fox (who cannot
swim) is roaming the edges of the pond, waiting for the duck to come close.
The fox can run four times faster than the duck can swim. In order to escape,
the duck must swim to the edge of the pond before flying away. Assume that
the duck can't fly until it has reached the edge of the pond.
The question is, can the duck escape? Why or why not?
Cheers
Gene Huh
h...@wccf.mit.edu or huh@mitwccf
Stein Kulseth FBA
SPOILER:
Yes, it can:
The pond has a circumference of C1 = 2*PI*r. Now, the duck swims just
outside of a circle (1-PI/4)r from the pond centre, this circle has a
circumference of C2 = 2*PI(1-PI/4)r = 2*PI(4-PI)r/4 < 2*PI*r/4 =C1/4
As C2 < C1/4, the duck can swim around this circle faster than the fox
can run around the edge of the pond, so the duck is able to navigate to
a position where the fox is exactly opposite of the pond centre. Now the
distance to the nearest shore is just under (PI/4)r, while the fox must
cover an entire halfcircle measuring PI*r.
So, no duck for mr. Fox
--
stein....@nta.no (Norwegian Telecom Research)
'It's the howl from the desert, the scream from the slums
The Mississippi rolling to the beat of the drums'
- Phil Alvin ("American Music" recorded by the Blasters)
Keith Allan Schneider
>Dear puzzlelovers,
A friend (Hyong Lee) and I were bored, so we thought about this for a second.
Let's divide the pond into two sections. The first, extending 1/4 the
radius from the center, is a zone in which the duck can always keep the
center between it and the fox (it can spiral out, or whatever). Now, the
duck can travel the circumference of this boundry (1/4 of the radius from
the center) in the same time it will take the fox to travel the circumference
of the pond.
Now, once the duck crosses this boundry, the fox has the advantage, so she
must make a mad dash to the side. The distance from the boundry to the shore
is 3/4 of the radius, and the distance that the fox must travel is pi times
the radius (remember, the duck has kept the center of the pond between it and
the fox). Since the fox travels 4 times as fast, it will take the fox
pi/3 times longer than the duck to reach the edge. So, the duck gets away!
Now, some of you may be saying that the duck will never reach the boundry,
still keeping the center of the pond between it and the fox, since the spiral
would only converge to the boundry, as the circumnavigating time of the
duck approached the fox's. But, since the fox takes pi/3 times as long as
the duck to reach the edge, there is a bit of extra time here for the duck
to play with.
So, if the fox travelled 1 + Pi times as fast as the duck, it would JUST catch
the duck, but in this case, the duck would never reach the break-for-it
boundry.
Oh well, fun puzzle ( I hope we didn't mess up somewhere).
keith
.
e
RING, DAVID WAYNE
>swim) is roaming the edges of the pond, waiting for the duck to come close.
>The fox can run four times faster than the duck can swim. In order to escape,
>the duck must swim to the edge of the pond before flying away. Assume that
>the duck can't fly until it has reached the edge of the pond.
>
> The question is, can the duck escape? Why or why not?
Suppose the fox runs at a speed 23mph and the duck swims at 5mph. Can
the duck escape now?
Dave Ring
dwr...@zeus.tamu.edu
RING, DAVID WAYNE
>> A duck is swimming about in a circular pond. A ravenous fox (who cannot
>>swim) is roaming the edges of the pond, waiting for the duck to come close.
>>The fox can run four times faster than the duck can swim. In order to escape,
>>the duck must swim to the edge of the pond before flying away. Assume that
>>the duck can't fly until it has reached the edge of the pond.
>
>Let's divide the pond into two sections. The first, extending 1/4 the
>radius from the center, is a zone in which the duck can always keep the
>center between it and the fox (it can spiral out, or whatever). Now, the
>duck can travel the circumference of this boundry (1/4 of the radius from
>the center) in the same time it will take the fox to travel the circumference
>of the pond.
>still keeping the center of the pond between it and the fox, since the spiral
>would only converge to the boundry, as the circumnavigating time of the
>duck approached the fox's.
Excercise: show that the duck's path inside the region is a semicircular arc.
Dave Ring
dwr...@zeus.tamu.edu
Stein Kulseth FBA
|>
|> Suppose the fox runs at a speed 23mph and the duck swims at 5mph. Can
|> the duck escape now?
Suppose the fox to duck speed ratio is a (a=4, in the original puzzle,
a = 23/5 = 4.6 here)
Now the duck may swim out to (not including) a radius of r/a, while still
keeping the fox exactly opposite the pond centre. Now for the duck to
be able to escape we must have 4*(r-r/a) < pi*r <=> a < 4/(4-pi) ~= 4.65979
So, still no duck!!
Keith Allan Schneider
Well, it depends on what the fox does. or are you assuming that both the
duck and fox use the best strategy possible?
keith
Keith Allan Schneider
>|> > The question is, can the duck escape? Why or why not?
>|>
>|> Suppose the fox runs at a speed 23mph and the duck swims at 5mph. Can
>|> the duck escape now?
>Suppose the fox to duck speed ratio is a (a=4, in the original puzzle,
>a = 23/5 = 4.6 here)
>Now the duck may swim out to (not including) a radius of r/a, while still
>keeping the fox exactly opposite the pond centre. Now for the duck to
>be able to escape we must have 4*(r-r/a) < pi*r <=> a < 4/(4-pi) ~= 4.65979
>So, still no duck!!
That's not right. If a > pi + 1 = 4.14... then the fox can catch the duck.
Your 4 should be an "a."
keith
Stein Kulseth FBA
|> Now for the duck to
|> be able to escape we must have 4*(r-r/a) < pi*r <=> a < 4/(4-pi) ~= 4.65979
|>
|> So, still no duck!!
Sorry, I was a bit too quack there, that's:
a*(r-r/a) < pi*r, gives a-1 < pi, and DUCK!!
(for the fox, and I duck, too)
--
stein....@nta.no (Norwegian Telecom Research)
'When murders are committed by mathematics, they can be solved by
mathematics. Most of them aren't, and this one wasn't'
- Nick Charles (Dashiell Hammett's "The Thin Man")
Xavier Llobet EPFL - CRPP 1015 Lausanne CH
In article <1992Aug13.1...@nntp.nta.no>, st...@hal.nta.no (Stein Kulseth FBA) writes:
|>|> > The question is, can the duck escape? Why or why not?
|>|>
|>|> Suppose the fox runs at a speed 23mph and the duck swims at 5mph. Can
|>|> the duck escape now?
|>
|>Suppose the fox to duck speed ratio is a (a=4, in the original puzzle,
|>a = 23/5 = 4.6 here)
|>
|>Now the duck may swim out to (not including) a radius of r/a, while still
|>keeping the fox exactly opposite the pond centre. Now for the duck to
|>be able to escape we must have 4*(r-r/a) < pi*r <=> a < 4/(4-pi) ~= 4.65979
|>
|>So, still no duck!!
Where does your 4 come from? It should be a ! Then, the criterion for the duck to escape is a < pi+1 = 4.14159... If the duck swims at 5 mph, the fox needs only to run at 20.708 mph to have dinner.
Dave Dodson
By using the following strategy, the duck can escape as long as the fox
can run no more than v := 4.6033388487517003525565820291030165130674...
times as fast as the duck can swim:
Assume the pond is of radius 1 and the duck swims at speed 1. The duck
maneuvers to a point 1/v from the center of the pond and diametrically
opposite to the fox. Then the duck starts swimming radially outward toward
the shore. Eventually, the fox must decide which way to run around the pond,
or the duck will surely escape. When the fox starts to run, the duck makes a
90 degree and swims toward the shore such that the fox will have to run more
than halfway around the pond. If the fox turns around, the duck will turn
back onto an outward radial path until the fox passes colinearity, and then
will turn 90 degrees the other way, which puts the fox in a worse position
than if he had not turned around, so it is not in the fox's best interest to
turn around.
In the above case, the fox runs only 4.6 times as fast as the duck can swim,
so the duck escapes.
The number 4.6033388487517003525565820291030165130674... is the reciprocal of
the solution of the transcendental equation sqrt(1-r*r) = r*(pi+arccos(r)),
which can be derived from the fox's best case where he starts running when
the duck is 1/r+epsilon from the center and doesn't turn around.
----------------------------------------------------------------------
Dave Dodson dod...@convex.COM
Convex Computer Corporation Richardson, Texas (214) 497-4234
Seth Breidbart
Seth se...@fid.morgan.com
QUIT
Seth se...@fid.morgan.com
RING, DAVID WAYNE
>>keeping the fox exactly opposite the pond centre. Now for the duck to
>>be able to escape we must have 4*(r-r/a) < pi*r <=> a < 4/(4-pi) ~= 4.65979
>
>Your 4 should be an "a."
You're both wrong :-)
4 should have been an a, but the fox still can't catch the duck (if the duck
is clever! )
Dave Ring
dwr...@zeus.tamu.edu
Keith Allan Schneider
Well, we were assuming that both the fox and the duck use the best strategy
possible, and that their reaction times were instantaneous...
keith
David Karr
>dwr...@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 (ka...@cs.cornell.edu)
Stephen H. Landrum
> A duck is swimming about in a circular pond. A ravenous fox (who cannot
>swim) is roaming the edges of the pond, waiting for the duck to come close.
>The fox can run four times faster than the duck can swim. In order to escape,
>the duck must swim to the edge of the pond before flying away. Assume that
>the duck can't fly until it has reached the edge of the pond.
> The question is, can the duck escape? Why or why not?
**SPOILER** follows
Yes, the duck can escape.
Reasoning:
Call the radius of the pond 1 unit. As long as the duck is within
the circle concentric with the pond and with a radius of .25 units,
then the duck can stay directly opposite the center of the pond from
the fox. As soon as the duck is .25 units from the center of the pond,
the duck can make a dash for the edge, having a distance of .75 units
to cover, while the fox must cover a distance of PI units to catch the
duck. In the time that it takes the duck to cover .75 units of
distance, the fox can only move 3 units, and will miss the duck by a
small amount.
--
Stephen H. Landrum VOICE: (415) 813-8909
Domain: slan...@ntg.com UUCP: ...netcomsv!ntg!slandrum
USNAIL: New Technologies Group Inc. 2468 Embarcardero Way, Palo Alto CA 94303
Keith Allan Schneider
>In article <1992Aug14.0...@cco.caltech.edu> ke...@cco.caltech.edu (Keith Allan Schneider) writes:
>>dwr...@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 ...
>Assume the ratio of the fox's speed to the ducks is a, and the radius
>5. Fly away.
>that is,
>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 (ka...@cs.cornell.edu)
Okay, I see this now. This is a better strategy, but is it the best strategy
for the duck? If so (or not), can you prove it?
Anyone?
keith
Ajit Sanzgiri
> ..........
>than halfway around the pond. If the fox turns around, the duck will turn
>back onto an outward radial path until the fox passes colinearity, and then
>will turn 90 degrees the other way, which puts the fox in a worse position
>than if he had not turned around, so it is not in the fox's best interest to
>turn around.
and later ka...@cs.cornell.edu (David Karr) writes:
> ....
>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
Not so fast. Yes, the duck is closer to shore, but the arc along
which the fox must run is also correspondingly shorter. One needs
to check that the duck's gain outweighs the shorter distance the
fox must now run. This is in fact the case (thank god).
Ajit Sanzgiri
P.S. Strangely enough, I was told this puzzle by my brother
half-way across the world 4 years ago. These puzzles sure travel
faster than their characters.
Ajit Sanzgiri
In article <1992Aug14....@cco.caltech.edu> ke...@cco.caltech.edu (Keith Allan Schneider) writes:
>> [description of duck's strategy deleted]
>
>Okay, I see this now. This is a better strategy, but is it the best strategy
>for the duck? If so (or not), can you prove it?
>
>Anyone?
>
>keith
Yes, this is the best strategy for the duck. Specifically, the
following may be proven:
The limiting ratio of velocities that this strategy works against
cannot be improved by any other strategy. i.e. if the ratio of
the duck's speed to the fox's speed is less than r where r is defined
by the equation : sqrt(1-r*r) = r*(pi + arccos(r)), then the duck
cannot escape given the best fox strategy.
Given a ratio R of speeds less than the above r, the fox is sure to
catch the duck (or keep it in water indefinitely) by pursuing the
following strategy:
Do nothing so long as the duck is in a radius of R around the centre.
As soon as it emerges from this circle, run at top speed around the
circumference. If the duck is foolish enough not to position itself
across from the centre when it comes out of this circle, run "the short
way around", otherwise run in either direction.
To see this it is enough to verify that at the circumference of the
circle of radius R, all straight lines connecting the duck to points
on the circumference (in the smaller segment of the circle cut out
by the tangent to the smaller circle) bear a ratio greater than R
with the corresponding arc the fox must follow. That this is enough
follows from the observation that the shortest curve from a point on
a circle to a point on a larger concentric circle (shortest among all
curves that don't intersect the interior of the smaller circle) is
either a straight line or an arc of the smaller circle followed by a
tangential straight line.
Ajit Sanzgiri