Hungry Wolf Vs Scared Chicken

[wy125]

Okay here's a problem to play around with. I saw this posted years ago on a math puzzle website. The given solution is very simple and I to this day haven't been able to figure out how they came up with it. The solution I got was complicated and tedious. Anyway, maybe someone here can figure it out.

Here is the problem:

(1) There is a wolf and a chicken initially separated by some distance.
(2) The wolf runs at a speed that is faster than the chicken's.
(3) The chicken and wolf begin running at the same time. The chicken runs perpendicular to the line that would initially connect them and can only run in that direction. The wolf on the other hand runs such that he is always facing the chicken.

The question is how far does the chicken get before the wolf catches the chicken.

For those of you who prefer working with numbers let's say that they are initially separated by a distance of 200 m. The wolf runs at 5 m/sec and the chicken can run 3 m/sec.

Hope I explained that well enough.

[techgnome]

sad part is that I can see the resulting graph in my head... the line of the chicken's travel is the vertical axis. The initial line between the wolf and chicken's start positions is the horizontal axis.... the path of the wolf is a parabolic curve. So the time of travel for the wolf is more than 200/5 (40s - if the wolf could travel a straight line) ... Which means the chicken is should be able to get at least 120m.
So the question is, how much further does the chicken get? Depends on the extra distance the wolf has to travel due to the curve.

-tg

[jemidiah]

Here's a tentative and incomplete solution.

Variables: vs = sheep velocity; vw = wolf velocity; tc = time of capture; t0=0 = start time; d = distance separating the sheep and wolf; s = total arc length of the wolf's path.

Picture: the wolf and sheep are in a 2D Cartesian plane, with the wolf starting at (-d, 0) and the sheep at the origin. The sheep runs up the positive y-axis with the wolf initially pursuing due east but turning north as the chase progresses.

Consider the arc length of the wolf's path. Since his velocity is constant, when he captures the sheep the length is vw*tc. Consider various symmetries of the problem. First, try scaling both vs and vw by the same factor. This effectively speeds up time, but arc length remains the same, so at least we have s = ...(vs/vw)^n... or ...(vw/vs)^n.... Increasing vw cuts the chase short, so the vw needs to be in the denominator. Now try distance: scale d by some factor. Scaling both the speeds does nothing to arc length, so scale them by the same factor. We've scaled the entire plane up by that factor which scales distances by that factor, so we also have s = ...d^1.... From dimensional analysis and these two observations we can say that s = C*d*(vs/vw)^n for some constants n and C. n and C are undetermined right now, but at least we have this: s = vw*tc = C*d*(vs/vw)^n, or tc = C*d*vs^n/vw^(n+1).

In algebra this is all incredibly dense:
s = Integral from 0 to tc of Sqrt(a'^2+b'^2) dt = Integral from 0 to tc of vw dt = vw*tc
s = C*d*(vs/vw)^n
therefore
tc = C*d*vs^n/vw^(n+1)

Again this is tentative and not rigorous.

[wy125]

techgnome,

yes it's all in the extra...


jemidiah, you're way off.... It's a chicken not a sheep Actually, you may be barking up the right tree but I'm not really sure. i took a different approach. I didn't really understand your analysis so I can't really say. I don't want to give too much away so I'll stop there. You may be onto the solution that was given on the site but I can't really say at this point because I have no idea how they came up with it...

[jemidiah]

lol, chicken, sheep, wolf--they all taste the same.

Unfortunately I thought a bit more about my analysis, and all it really shows is that you can factor the d out of the rest of the arc length formula, and that s must be a function of vs/vw--that is, the other factor is some arbitrarily complicated function of vs/vw, not necessarily just one power of it.

Back to the drawing board I think.

[wy125]

Haha sounds good. You have no idea how much time I've spent on this problem. I'm excited that someone might figure out some way of 'seeing' a solution. I just hope I can understand it when someone does....

[NickThissen]

I tried it, but didn't get very close... It seems to me that you can define a vector V which is always pointing from the wolf to the chicken. The vector is just the position vector of the chicken, minus the position vector of the wolf.

The position vector of the chicken is known at all times. If the chicken starts at (0,0) and runs 'up' the positive y-axis, then it's position vector is ( 0 , v t ) where v is the speed of the chicken.

The position vector of the wolf, well... That is what we're trying to figure out I guess. Let's call it ( x_w(t), y_w(t) ). The vector V is then:
V = ( - x_w(t) , vt - y_w(t) )

This is where I'm stuck lol... What do we know more?

[wy125]

Hi Nick. All the information is there. I don't want to bias anyone with how I tackled the problem because that would lead away from the posted answer which was amazingly simple. There must be some way of just 'seeing' it.... It's beyond me though.

[jemidiah]

I've gotten to a differential equation that's not too bad. If I had some advice from on high to solve it the rest would work out, but it's rather nasty to solve.

On the other front so far I have...

tc = d / vw * f(vs/vw) for some function f.

Is this correct?

[wy125]

Yeah jemidiah, that looks correct.

[NickThissen]

What's the DE you got?

[jemidiah]

Well I wrote a program to run some simulations, and I found that my function f is 1/(1-x^2). That is,

tc = d/vw * 1/(1-(vs/vw)^2)

This worked experimentally to a relative error of less than 0.006% in my trials. I know that this reflects some symmetry in the problem, but which symmetry--I don't know yet.

I'll post the DE if I go back to trying that method. I'd have to rederive it, since I threw the paper away.

[wy125]

It looks like you're coming along okay. How did you determine f?

[Fizziii]

Not sure on the parabolic equations at the moment... but it seems to me that the parabolic path is determined primarily by the velocities of the chicken(sheep) and the wolf. Once you have that it seems like the formula would be set up so that

Distance traveled along the parabola where it crosses the y axis(Dw)/wolf's speed(Sw) = distance the chicken traveled(Dc)/ chickens speed(Sc).

or (Dw * Sc)/Sw = Dc

I'm just note entirely sure how the speeds drive the parabola, and how to determine the distance traveled along that parabola...

Edit... upon thinking about this more, if you can get the parabola's equation, you could just solve for the y value when X = 0... it's just a matter of getting the parabola's equation that's the hard part.

[NickThissen]

But how did anyone determine it's a parabola in the first place? I can visualize it being one, but I can visualize a ton of functions it could look like right now... I don't think anyone has proven it's a parabola (yet). And if jemidiah is correct, it looks nothing like a parabola.

[Fizziii]

Worst case scenario if the speeds are equal, I imagine it goes to tangency... with the wolf ending up a constant distance behind the chicken.

[techgnome]

That may have been my fault... it's what I saw in my head at the time... and it seemed valid... now I'm not sure.

Teacher? Can I make my guess now? The rabbit lived for another 50 seconds and made it 150m. And that means the wolf traveled.... [strike this]hold on... that can't be right... ???[/strike this] it is right... wolf travels 250m.

-tg

[Fizziii]

200^2 + 150^2 = 250^2
40000 + 22500 = 62500

I think you came up with the straight line distance...

[NickThissen]

I made a quick simulation in XNA Game Studio (hehe) and this is the result:
(Blue = wolf, red = chicken)

First, with a relatively slow wolf. Speed of chicken = 0.5, speed of wolf = 0.7:

It looked like it was going to be a parabola, but it looks nothing like it in the end.

I figured it may be too slow to resemble a parabola, so I tried it a bit faster. Speed of the wolf is now 1.5 (chicken still 0.5):


As you can see it really does not look like a parabola at all.

I however have no idea what it does look like

I guess in the limit that the wolf never reaches the chicken, the curve is exactly a vertical asymptote. But as soon as the wolf reaches the chicken there will be a 'dent' in the path, when it goes from 'almost reaching it' to 'reaching it'. You can see that clearly in the second image.

The logic for this code is this. I think it's right... I simply let the chicken move upwards at a constant speed, and I determine the direction vector of the wolf from the difference in X and Y positions. This vector is then normalized (so that the speed will remain constant) and the position of the wolf is updated.

            //1. Move chicken
            C.Position.X += C.Direction.X * C.Speed;
            C.Position.Y += C.Direction.Y * C.Speed;

            //2. Update wolf direction
            W.Direction.X = C.Position.X - W.Position.X;
            W.Direction.Y = (C.Position.Y - W.Position.Y);

            // normalize
            float norm = (float)Math.Sqrt((Math.Pow(W.Direction.X, 2) + Math.Pow(W.Direction.Y, 2)));
            W.Direction.X = W.Direction.X / norm;
            W.Direction.Y = W.Direction.Y / norm;

            //3. Move wolf
            W.Position.X += W.Direction.X * W.Speed;
            W.Position.Y += W.Direction.Y * W.Speed;

[techgnome]

I did... and it is... For every 3 rise of the axis where the rabbit is, the wolf is going to travel 5 across the hypotenuse... this results in a horizontal gain of 4 each second.... The assumption that is is a curve is inaccurate. the curve would indicate that the wolf is constantly changing his vector... and he is, but in a manner that results in a straight line. the wolf basically remains parallel to the rabbit until such time as he intercepts the rabbit.The rate of the rabbit is constant, as is the wolf, so of course it's a straight line. He's also constantly facing the rabbit, so as soon as the rabbit takes off, the wolf's travel along the vertical axis also starts moving.

The OP also stated "The given solution is very simple" ... and it doesn't get much simper than a^2 + b^2 = c^2
if the speed of the rabbit is b (3m/s) and the wolf's c (5m/s) ... then a^2 + 3^2 = 5^2 or a^2 + 9 = 25 .... less 9 on each side gives us a^2 = 16. a= 4 So, for every 3 rise of the rabbit, we get 4 horizontal out of the wolf..... the total horizontal distance is 200m ... 200 / 4 = 50. distance of the rabbit is then 3 * 50 or 150. Now we have two sides of the triangle....for which Fizziii has supplied the final numbers.

But I don't even know if I'm right.

-tg

[NickThissen]

So why does my simulation show a curve?

I think your logic is flawed. If what you say is true then the wolf must already 'look' at the point where he is going to intercept the chicken, as soon as he starts moving. So he had to 'calculate' where the chicken would end up if he ran in a straight line, at constant speed.

Sure, that would work for the wolf, but it is not what the OP stated the wolf would do. "The wolf runs such that he is always facing the chicken". That is not true if he moves in a straight line. In fact, the wolf would then NEVER face the chicken, until they finally meet.

[Fizziii]

Nick,

What's the blue point on your graphs? Is that an arbitrary end point? The Wolf catching the rabbit is at the intersection of the blue & red lines, right?

--Fizziii

[NickThissen]

The blue dot is the wolf. The chicken is a red dot, but it's behind the blue dot :P

In both graphs the wolf has already caught the chicken for some time, I just let it run for a few seconds longer to show the 'kink' in the graph.

(As soon as the blue dot touches the red dot, it kinda stays on top of it. It jiggles around a little, but that's just random error I think, also because I'm divinding by the norm of the vector, which should be nearly zero. Not a good idea in general

I'll make a movie of it and upload it soon.

[Fizziii]

The second graph could be part of a parabola... if you cut the parabola where it crosses the Y axis... I'm not thinking a parabola could be correct though. If chicken speed = wolf speed, then eventually they would both be running up the y-axis, and a parabola would always cross it somewhere.

[NickThissen]

A parabola has no vertical asymptote. This curve does (at least in the limit that chicken speed = wolf speed). Also, it doesn't look like a parabola at all. A parabola would have a much 'sharper' base, and the curvature does not look constant (which it is for a parabola).

[NickThissen]

Here's two video's (might take a little while processing):
http://www.youtube.com/watch?v=2q3yir2_Ohs
http://www.youtube.com/watch?v=NiEI_uemIns

[Fizziii]

I'm wondering if it doesn't represent more of 1/4 of an ellipse...

[wy125]

Hi guys, looks like you guys are keeping busy When I said the solution was simple i didn't mean to imply that it was easy to figure out. I don't understand the rationale behind the easy solution (it may be easy to see but I haven't in years). Just so we're clear the easy solution is the same in the end as the one that I calculated. My solution was just a lot of work to get the same result.

Good work so far guys.

[NickThissen]

Well, I think I found it. But it's not really a simple solution. It's not very hard either, but I wouldn't call this 'simple'.

When I plot the function, I get this:


Looks familiar?

The equation I found is:

This is assuming the wolf starts in (0,0), and the chicken in (d,0). v is the speed of the wolf, and w the speed of the chicken.


Derivation coming up...


EDIT
Crap... I don't think it's correct after all. I choose d (the separation) = 10. But the graph's asymptote is not at 10... :\
Hmff...

[Fizziii]

I don't think the asymptote necessarily would be at 10, unless both of their speeds were equal... and then it'd depend on the speed chosen...

[NickThissen]

Hmm now I'm doubt full too. Maybe I should simply stop the graph when x = d?

I am expecting an asymptote at d = 10 though... But wait.. Maybe if I take v = w?? Let's see hehe.


EDIT
Hmm, that's odd. If I take v = w = 1 then the asymptote is at 10. If I take a different value however then it's not?! If I take v = w = 2, the asymptote is at x = 5. If I take 0.5, it's at 20...

[Fizziii]

Hmm now I'm doubt full too. Maybe I should simply stop the graph when x = d?

I am expecting an asymptote at d = 10 though... But wait.. Maybe if I take v = w?? Let's see hehe.


EDIT
Hmm, that's odd. If I take v = w = 1 then the asymptote is at 10. If I take a different value however then it's not?! If I take v = w = 2, the asymptote is at x = 5. If I take 0.5, it's at 20...

Your edit makes perfect sense to me. Your speed serves as a scaling factor for the graph. As you go twice as quick, you catch up twice as quick... so the rabbit moves twice as far in the same time and the wolf moves twice as far, so it goes vertical in half the distance.

Your shape will stay the same. The speed scales the graph, and the distance between the 2 changes where along the curve the catch-up is. IF your wolf is speed = 100 and your chicken's speed is 1, it's happen very early in the graph.

[wy125]

Hi guys, looks like you guys are keeping busy When I said the solution was simple i didn't mean to imply that it was easy to figure out. I don't understand the rationale behind the easy solution (it may be easy to see but I haven't in years). Just so we're clear the easy solution is the same in the end as the one that I calculated. My solution was just a lot of work to get the same result.

Good work so far guys.

[NickThissen]

Your edit makes perfect sense to me. Your speed serves as a scaling factor for the graph. As you go twice as quick, you catch up twice as quick... so the rabbit moves twice as far in the same time and the wolf moves twice as far, so it goes vertical in half the distance.

Your shape will stay the same. The speed scales the graph, and the distance between the 2 changes where along the curve the catch-up is. IF your wolf is speed = 100 and your chicken's speed is 1, it's happen very early in the graph.

But, if I take v = w = 2, then the wolf will never reach x = 10. The chicken starts and stays at x = 10, but the wolf never gets past x = 5. I guess it's logical that it never reaches the chicken, as their speeds are the same, but it would get close, wouldn't it..??

[Milk]

I'm not getting such a prominent dent in my simulations, are you sure your getting the point of capture right? EDIT: Ahh, I see you state you let the simulate run over, that will be why.

Re parabola. If a straight line was drawn from the sheep/rabbit/chicken/child through the wolf extending it to the x-axis every n seconds then, if the wolfs path was parabolic I would expect these straight lines to bisect the axis at even distances would I not?? As it is the spacing widens then shrinks, I don't know if that counts as any sort of proof.

[Fizziii]

If their speeds are identical, I think that the wolf should always end up right behind the chicken (right behind being some distance, but directly below on the graph). I would think the asymptote should always be where the rabbit is start IF and ONLY IF their speeds are identical.

If your equation isn't getting that, is it taking into account where the rabbit starts? (Please note, your equation exceeds my level of math. I understand the principle of what we're doing here, just not the specific math... so I could be wrong).

[NickThissen]

Here is the derivation of my equation:



For identical speeds, the wolf can not only never catch the chicken, but it should also never be exactly on the same x-coordinate as the chicken! It will get arbitrarily close to x = d though, but never reach it. At least that is what I think.

So it doesn't make sense for me to have the speed be a factor in the asymptote. I think it should always be at x = d, if the speeds are identical.

[Fizziii]

I agree... x should equal d if the speeds are equal...
Also, as the wolf gets quicker than the chicken, the intercept point should move left, while staying on that line.

[NickThissen]

How can the interception point move left, while staying on x = d..?

The x-coordinate of the interception point is ALWAYS x = d. Since that is where the chicken is always going to be.


I just did a sim. with equal speeds, and found that they start chasing each other at equal speeds, and constant distance. It looks as though the blue line is actually at x = d at the top, but I think that it's just so close that you cannot see it (or that the computer is not precise enough anymore). There's no way to verify that though I think lol...

[Fizziii]

How can the interception point move left, while staying on x = d..?

The x-coordinate of the interception point is ALWAYS x = d. Since that is where the chicken is always going to be.
<snip>

True... the intereception point is ALWAYS x=d.

What I meant was as you look at your graph, as the speed of the wolf increases, the interception point **and the d point** move left, away from the asymptote, while staying on the curve in the graph.