wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> duck in the pond part deux
        
(Message started by: pjay on Dec 3^rd, 2003, 5:59am)

Title: duck in the pond part deux
Post by pjay on Dec 3^rd, 2003, 5:59am

ok, so most of you have figured out how a duck escapes from the center of a circular pond when a 4x faster menacing creature awaits it at the edge of the pond, how bout a 5x faster monster?? (I don't know whether this can be done- in fact I now think that it cannot be done) For a harder problem, try to find a supremum for K where K represents how many times faster the monster is. I have a lower bound on K, but have not solved the problem completely. ~~(obviously the lower bound is greater than 5)~~. Another question is: does it matter that we are working in 2 dimensions? (I do have an answer to this question)

More specifically, the creature runs 5x as fast as the duck swims but runs slower than the duck runs so if the duck ever manages to swim to a part of the edge of the pond where the creature hasn't yet reached then it lives (the problem is that the creature always moves in a direction which minimizes its distance to the duck- if two directions are equally minimizing, flip a fair coin).

Title: Re: duck in the pond part deux
Post by aero_guy on Dec 3^rd, 2003, 6:10am

So the duck runs more than five times as fast as it swims? Odd...

Title: Re: duck in the pond part deux
Post by aero_guy on Dec 3^rd, 2003, 6:52am

I thought I already solved this in the last thread but I guess not and I am not able to search. Anyway, we take the first part of the last solution, where the duck is in equilibrium with the fox going round the pool. Then we [hide]find the angle the duck should take towards the edge to reach the edge at the same time as the fox in terms of n, how many times faster the fox is[/hide].

Now we solve this equation for n, take dn/d[theta] and set it equal to zero to minimize. This give us an equation for [theta],[hide] the angle measured from the center between the equilibrium starting point of the duck and where it hits the edge, of tan([theta])=[theta]+[pi]. Solve that (it comes out to about 1.352 rad) and plug it into the equation for n, n=cos([theta])+[sqrt](cos²([theta])-1+([theta]+[pi])²).[/hide]

This gives me an answer of [hide]n=4.603[/hide], which is less than 5, so I guess I am on the wrong track.

Title: Re: duck in the pond part deux
Post by Lightboxes on Dec 5^th, 2003, 11:06am

Quote:

So the duck runs more than five times as fast as it swims? Odd...

It took me a while...LOL

Title: Re: duck in the pond part deux
Post by aero_guy on Dec 9^th, 2003, 9:39am

Any hints would be appreciated. As it is I am seeing things this way:

The farthest the duck can start from the center is R/K and still have the fox on the other side. So long as the duck stays outside of this circle (with radius R/K) the fox will continue going in one direction around the pond after him. Thus, the duck should take a straight line to the edge to minimize the time it takes him to get there (after waiting a milisecond to see which way the fox goes).

I can't see any way out other than for the duck to either wait for winter and the pond to freeze so it can just run, or use its frickin wings and fly for cryin out loud.

Title: Re: duck in the pond part deux
Post by pjay on Dec 9^th, 2003, 10:47am

this hint will give it away so i've hidden it.

hint[hide] aeroguy says:
So long as the duck stays outside of this circle (with radius R/K) the fox will continue going in one direction around the pond after him.

the phrase "one direction" is a bad assumption to make[/hide]

Title: Re: duck in the pond part deux
Post by aero_guy on Dec 9^th, 2003, 1:03pm

I thought of something like this at first, but it does not seem workable.

:[hide]One way to screw up the fox would be to force it to keep changing directions. This way you could stay almost 180 deg away from it, continually making a reversal of direction the ideal move. In order for you to cause the fox to change direction you need to cause the radial distance between the fox and duck to be lower on one side than the other. The only way to do this is if the radial velocity of the duck is greater than that of the fox, otherwise the fox will continue going in one radial direction, and reducing the angle between them. This cannot happen outside of R/K.[/hide]

Title: Re: duck in the pond part deux
Post by towr on Dec 9^th, 2003, 1:48pm

Suppose you had a rectangle, and the duck had to go from the top to the bottom, and the fox had to go from bottom-left to the right to catch the duck. Would you still propose the duck's optoimal path is to go straight down? (In the case of going straight to the shore this is equivalent to using polar coordinates in the original problem.
In the polar plot of the optimal case I doubt it will be a straight line though, since angular speed decreases rapidly if you do that)
The goal is to reach the shore before the fox catches you, not keeping half a circle lead on him..

Title: Re: duck in the pond part deux
Post by James Fingas on Dec 10^th, 2003, 6:24am

I thought SWF and I had this problem licked in Duck in Pond II (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1046187731;start=2), but you're suggesting there's a better answer ... (BTW, it's the same answer Aero Guy got)

Towr wrote:

Quote:

...I doubt it will be a straight line though...

Title: Re: duck in the pond part deux
Post by pjay on Dec 10^th, 2003, 8:39am

remember aeorguy that the fox moves with the following algorithm. It always tries to minimize it's distance with the duck. (when two directions are equally good it flips a fair coin). I can write a more explicit hint if you so desire, but i think you basically have the idea. your last hidden comment was on the right track. just try to figure out how to make it work.

Title: Re: duck in the pond part deux
Post by aero_guy on Dec 10^th, 2003, 8:57am

The rectangle is a very different case, as how you measure the distance between the two is odd. For example, if the fox is on the middle of one side and the duck is just out of his reach, the duck may make a straight line to the opposite edge and the fox would just sit there as moving in either direction would actually increse his distance to the duck until he reached the corner.

You actually would go in a straight line (though not the shortest distance to the edge) as anything less causes you to lose ground to the fox. Draw any curved path from your starting point (R/K) to where you will hit the edge. Whatever path you choose, so long as you stay outside of R/K the fox will continue in the same direction. Therefore, wherever you choose to hit the edge your path will not change how long it takes the fox to get there. So, if nothing you do can change how long it takes the fox to get there, you should take the fastest path possible, a straight line. This will not be straight in polar coordinates, but a curve (it would only be straight if you travelled directly out from the center which is suboptimal).

However, the path from the center to the distance R/K will be a curve as you are trying to keep the fox opposite you. This can be found by setting the radial velocities of the two animals identical. Thus if the duck's velocity is V and its radial and azimuthal velocities are V_r and V_[theta]:

V_[theta]/r = KV/R

V_[theta]² + V_r² = V²

V_[theta] = KVr/R
V_r = V[sqrt](1-(Kr/R)²)

Solving these is not necessary to solve the problem, but it can be shown that you can get arbitrarily close to R/K with a curved path, after which you need to change to a sraight one.

modification: dang, you can't subscript [theta]. Also, pjay, my point was that I see what you are trying to do, or at least what I think you are trying to do, but that it is impossible. As far as I can see once you cross the R/K threshold the fox will never change directions.

proof: Draw a line from the fox through the center to the opposite side. By the nature of a circle, if you are on one side of this line you are closer in that direction for the fox. Radial velocity on your part cannot change which side of the line you are on. In order to move from one side of this line to the other your angular velocity must be greater than that of the fox. If not he will simply approach you and make it even more difficult to get to the other side. The fox's angular velocity is constant. You have max angular velocity when radial velocity is zero. Outside of R/K your angular velocity is always less than that of the fox.

How do you beat this?

Title: Re: duck in the pond part deux
Post by aero_guy on Dec 10^th, 2003, 9:09am

Also, the only places where the fox will be flipping a coin are when you are at 180 and when you are a 0 deg distance. I have shown you cannot maintain 180 deg close to the edge, 0 deg is useless as the fox is right on you. Either you are seeing something unbelievably clever or you have made a mistake.

Title: Re: duck in the pond part deux
Post by pjay on Dec 10^th, 2003, 11:35am

on 12/10/03 at 09:09:22, aero_guy wrote:

Either you are seeing something unbelievably clever or you have made a mistake.

I think it was the latter. I agree with you aero when you say that the fox will not change directions beyond the circle of radius R/K, but now it makes me wonder what exactly is the solution to this problem (it was posed to me by a friend). I'll ask him if even he has a solution, because it seems to me that aero's arguments are sound. i'll get back to you soon.

Title: Re: duck in the pond part deux
Post by rmsgrey on Dec 11^th, 2003, 7:10am

The only way I can think of for a duck to escape a fast fox is by taking off from the surface of the pond and flying away...

As to the side issue of higher dimensions, assuming a spherical "pond" (maybe a buried space-ship is attempting to launch without getting boarded by the local customs officer - whose helicopter can fly faster than the space-ship can burrow but as soon as the ship clears atmosphere, it can jump to hyperspace... Oh, and the ship can survive at the core of the planet) I think you get the same solution as the circular 2D pond - if you look at the great circle connecting the closest point on the sphere's surface to the prey with the location of the predator, then if the prey moves so as to change that great circle, he always decreases the length of the arc segment faster than keeping the same radial behaviour but with angular components moving along the great circle.

Title: Re: duck in the pond part deux
Post by pjay on Dec 25^th, 2003, 11:43am

my colleague who posed this to me agrees that 4/(4-pi) is the best one can do...

Title: Re: duck in the pond part deux
Post by Patashu on Sep 2^nd, 2004, 4:29am

on 12/10/03 at 08:39:04, pjay wrote:

Aha! So, to win you must force the fox to flip a coin, then while it's distracted with the coin you slip past!

...

Unless it's a grand master speed coin-flipper or something. Are foxes eligable for titles like that?