Duck and Fox ... and other Great Puzzles

The Game Room
1

One of my favorite math puzzles is Duck and Fox. I see it is also one of Roger’s Favorite Puzzles.

Better is to ask: What is the maximum speed advantage the Fox can have and still be unable to catch the Duck? (I’d also write that the Duck can fly away from land but not water, and that Duck is hungry and can’t outwait the Fox. Exact solution requires some math, so take full credit just for describing Duck’s strategy.)

Some of the other puzzles on that page are also great puzzles. Anyone want to offer more?

I wouldn’t consider Duck and Fox to be a “Two Minute Puzzle.” Moreover, the solution presented on that page is not the solution to the more interesting question above.

2

[spoiler]The duck should start in the center and swim directly away from the fox. If the fox moves, the duck should adjust his position so that the center of the pool always lies directly between them.

The duck follows this strategy until he gets radius/4 away from the center. At that point the duck can just keep up with the fox as he changes position.

Now the duck makes his break for it, swimming straight for the edge of the pool. The fox has to cover half the circumference to reach him – 3.14159 * radius. But the duck only has to go 3/4 of the radius. Since the duck is traveling 1/4 as fast as the fox he can reach the edge in 3 time units, while it takes the fox 3.14159 time units. The duck is free![/spoiler]

3

The Hamster King’s solution does work for the problem as stated, but what if the Fox is faster? What if his speed is 4.6 times that of the Duck, not just 4 times?

4

OK, so solving for the marginal speed:

I’ll assume without loss of generality that the pond has radius 1, the duck has speed 1, and the fox has speed f (basically, this amounts to a definition of my length and time units). The duck swims out to a radius of 1/f. From there, the fox will take a time pi/f to reach the far shore, and we’re looking for the duck to get to the shore exactly at the same time as the fox, so the duck has to travel distance (f-1)/f in a time pi/f. The duck’s speed is 1, so that means that t = (f-1)/f = pi/f. It is straightforward to solve that f = pi+1

Of course, this is assuming that the strategy The Hamster King described is optimal. It’s conceivable that the duck can use some other strategy which is slightly better.

5

I don’t think it’s optimal, but that might be beyond me at this moment. The duck can swim in an Archimedean spiral, starting from the center, and reach the edge at the same moment as the Fox. This leads me to think that a similar spiral from the limiting radius will produce a better result.

6

Here’s a proof for the minimum fox speed :

The time for the duck to reach a point e on the shore is

t(duck) = d(e) / s

where s is the speed of the duck, and d(e) is the distance to that point.

The time for the fox to reach that same point is:

t(fox) = | ang[sub]fe[/sub] | / (*f**s)

where ang[sub]fe[/sub] is the smallest angle between the fox’s current location and the exit point e. f is how much faster the fox travels than the duck.

For the duck to escape, t(duck) must be less than t(fox). If the distance for the duck to travel is expressed in units of the radius, and angfe is likewise in radians, the distances can be compared directly and the duck’s speed s cancels out. (This is essentially the same set of simplifications Chronos made).
There is a critical quantity

ang[sub]c[/sub] = *f**d(e’)

where e’ is the closest exit point to the duck.

If ang[sub]c[/sub] >= pi, it is impossible for the duck to escape by making a break for the shore, since no matter where the fox starts out, it can reach the duck[sup]*[/sup]. Note if ang[sub]c[/sub] < pi, that doesn’t mean the duck can escape, only that it may be able to if the fox is out of position.

This means that if it is at all possible for the duck to escape, it must be able to reach a point where the distance dc to the shore is such that

dc < pi/f

with the fox out of position (i.e. at pi radians from e, or opposite the center from the duck). Incidentally, this is the point at which the duck can make a break for it in the original problem; it doesn’t have to go out to 3/4 of the radius.

The radius of the circle within which the duck can beat the fox is 1/f (again, in units of the pond’s radius). The distance to the shore from any point on this circle is

ds = 1 - 1/f

This means that the duck can only escape if dc > ds

pi/f > (1 - 1/f)

pi > f - 1

pi + 1 > f

or more clearly, f < pi + 1. Which is exactly the same result Chronos calculated.
[sup]*[/sup] I also claim that at some point the duck must make a Euclidean straight line to the shore, however briefly. That means this shows the duck cannot ever reach the shore unless it can reach a critical distance like this. My phrasing is because when the duck is at the center, it is in such an ‘unescapable’ location, and yet it escapes. The rest of the proof demonstrates (somewhat loosely) that if f > 1, there will be a location where the duck can no longer keep the fox out of position.

7

Er… wouldn’t it entirely depend on the size of the pond (and the actual, specific, not relative) fox and duck speeds? Sorry, I hate puzzles, because they almost always take place in a ficitonal non-world with no constraints.

8

Not really; all problems of different sizes or amounts are “scale models” of the generalized problem.

9

If you look at the first two equations of my post, they both work using the actual speed of the animals and size of the pond. Saying ‘the duck’s speed cancels out’ is a bit of a cheat on my part - but in any comparison expression t(duck) ? t(fox) the duck’s speed will drop out. You could keep including it, but it would keep dropping out.

The size of the pond is being accounted for, since everything is in units of the radius. I did this intentionally to use units of radians for angles, which are also in units of the radius.

10

Or, f < 4.1416.

As I mentioned earlier, f = 4.6 is doable. (And this would definitely not be “one of my favorite math puzzles” if the straightforward answer already given were optimal. :smiley: )

Finding duck’s optimal strategy for f ~= 4.6 can be done with good intuition. (Or perhaps by working backwards from the value “4.6” – so forget I’ve given that hint! :D).

Proving that duck cannot improve on that strategy as f increases is a much harder challenge.

11

Possibly when the duck makes its break for it, the duck should not swim on the line directly away from the fox. When the duck makes its break, the fox has to pick a direction to run around the pond. Maybe the duck can improve its chances by adjusting its approach to shore, reaching the shore at a point that makes the fox have to run further.

So: say the fox is at due north, the duck is at a point due south of the centre of the pond at the point where he has to make a break for shore. The current solution says the duck should swim due south. But when the duck does this, the fox has to pick a direction. Say he heads east - then the duck has the option to head to a point on shore that is west of his original target, which means the fox will take more time to get there. It will take the duck a bit longer to reach the shore, but it will also take the fox longer to reach that point. Which “longer” is more?

12

I’m not up to doing the calculations right now, but what if the duck starts at the equal-angular-speed circle, but then always travels in a direction perpendicular to the fox’s current direction of motion?

13

Ok, the idea I had works, I think. Take the duck’s speed as 1, the radius of the pond as 1, and the fox’s speed as 4.6. Make the centre of the pond the point (0,0).

The fox is at the north end of pond (0,1). The duck is on the “equal angular speed” circle, so at (0, -1/4.6). The duck makes its break for it, and the fox picks a direction to chase. It makes no difference which direction the fox chooses, so let’s say he heads east. The duck reacts by swimming due west.

…trigonometry…

The duck has to swim a distance of 0.976. To reach this point on the shore, the fox has to run 257.44 degrees around the pond, which is a distance of 4.493. 4.493 / 0.976 = 4.603. The duck barely escapes.

Compared to the strategy of the duck swimming due south, the duck has to swim an extra 0.19, but the fox has to go an extra 1.35. Also, if the fox ever tries to switch directions, he doesn’t gain anything, as the duck is further out than the “equal speed” circle and can just use this strategy again.

I will guess that this is optimal based on the fact that “due west” here is tangent to the “equal speed” circle (and the fact that septimus used 4.6 as the question).

14

Yes. You got it. The duck lives!!

Two other solutions were proposed in the thread: Swim directly away from the fox (Too simple) and Swim on a spiral (Too complicated). The correct solution is simple, elegant, and just right (as Goldilocks likes things!).

Googling, I see the puzzle is almost always presented with f = 4 so the inferior solution is good enough. :mad:

And when the correct solution is presented, many object with “But the fox will just double back!” (Ignoring that duck is looking over her shoulder and ready to react.)

I don’t know how many will find the correct solution intuitively clear. Proving its optimality isn’t hard, if hardly trivial.

15

Could you explain what exactly happens once the fox changes direction? Because all I can see as a result is a stalemate.

What does the duck’s final path to the edge look like?

16

If the fox constantly changes direction, it’ll look like a zig-zaggy straight line - and the fox will get nowhere near the duck. Every time the fox changes direction it loses ground (I think).

17

No. This is only true if the duck is within the critical circle that’s been mentioned. I don’t know if I buy the 4.6 figure. A proof would also show that the fox doesn’t lag more than half a circle behind or else switching directions is optimal. This would be the case with the head tangent strategy?

18

Note that the fox will already be going his best direction, except for an immediate course-change, i.e. after a slight feint to get the duck to “commit.” But if he forces duck to change direction, duck is OK. The important thing to note is that duck’s velocity always has a postive component away from the center. In other words, if they’re zigzgging, fox will be making no progress, while duck gets closer and closer to opposite edge.

It does fox no good to do the feint or zigzag variation. With fox playing in his best, straightforward way, the duck’s path (once he leaves the critical circle) will be … the shortest distance between 2 points! … a straight line!!

19

Why is it that you think the fox will be sitting in one spot, going back and forth if the duck’s moving? Whichever direction the duck picks, the fox will choose the same side and catch the duck. If the duck makes any movement that doesn’t go directly back to the safe spot on the critical circle, the duck has still picked a side and the fox catches it.

20

By the way, when I do this puzzle, I choose
R = Fox’s speed = radius of lake
Now, the critical circle has radius 1. No big deal, but (1,R) is slightly less messy than (1/R,1).

Unless the Fox is very close to his unbeatable speed, R = 4.60334, there are many circles that can play the role of “critical circle”, for example the one with radius (1 - epsilon), where epsilon is sufficiently small.

The smallest such “critical circle” is the one where Duck CAN “commit”; the largest is the one where Duck MUST “commit.”

Following, I think, is the simplest argument. I should have given it earlier.

You (the Duck) are on the North point of the critical circle (of radius 1 - epsilon) and Fox is due South. You don’t even look at Fox for a moment; you just continue North, by distance epsilon. Now you look at Fox: if he went West, you go East and vice versa. (If he didn’t move you continue North.)

If he feints West and then switches back to East, you’re OK. That extra distance epsilon gives you margin for corrective action.

But, you may object, I’m trying to dazzle with smoke and mirrors; what’s with the TWO critical circles, switching the argument between them as convenient? :dubious: Well, you will no longer escape if the Fox’s speed is near 4.60334; You only escape from a Fox of speed 4.60334 - g(epsilon). (Nevermind details of g()!)

But, as usual, you can make epsilon as small as needed!.