I came across a problem posted on a brain teaser website a while back (I no longer have the address) that I wanted to share with you. It took me a long time to solve it and the solution I came up with was rather tedious. When I checked the solution I found that my answer was correct but apparently I had taken a very difficult path towards solving the problem. I still don't understand how they arrived at their solution.
Anyway, I figured I would post the problem here. Maybe one of you guys will see an easy solution to this problem. If not, maybe you'll like the challenge of solving it the hard way. Enjoy...
Oh, numerical solutions are good, but I think the general solution is a bit more interesting. But whatever floats your boat I guess ....
Here goes:
The Wolf and the Chicken:
A wolf and a chicken begin separated by a distance of 100 meters. The wolf begins to chase the chicken. However, the chicken is restricted to running in a direction that is perpendicular to the line that is defined by the initial starting points of the wolf and chicken (so, if initially the wolf is 100 meters north of the chicken, then the chicken may only run in a straight line from its starting point directly towards the east). The wolf is also restricted. He must always run directly at the chicken. He is always directly facing the chicken as he runs. If the chicken can run 3 m/sec and the wolf can run 4 m/sec, how far does the chicken get from its starting point before the wolf catches him.
Is the chicken always running perpendicular to the wolf, or is she always running east? I think they are both running around in circles. Is the answer a whole number like 75m?
Sometimes what you're looking for is exactly where you left it.
JohnVB6: The chicken is always running east in a straight line so they do not run in circles. The answer is not a whole number.
Judd: You're right, it could also be west. In terms of the problem it doesn't matter. The chicken cannot change directions however. It must always move in a straight line, directly east or
west from its starting point. Choose whichever direction you want, but only one.
Integrate the wolf's position wrt to that of the chicken inside an integration over time? Until the wolf's x, y coordinates coincide with the chickens...
Dan
Outside of a dog, a book is a man's best friend.
Inside of a dog, it's too dark to read.
I'm trying to remember enough trig/calculus to find the analytic solution.
I'm trying to come up with the time based function for the wolf's movement, knowing that the length of the arc is 4t for every 3t of chicken movement. Ultimately, I'm trying to work out the time based equation for 'y' (the distance 'south' that the wolf has moved). Then when y = 100, you can work out t and hence x (the distance the chicken has moved).
I'm of the distinct impression that I can't actually remember enough maths to figure this out ...
Dan
Outside of a dog, a book is a man's best friend.
Inside of a dog, it's too dark to read.
I guess I also tried this incorrectly because I get Judd's answer,
Chicken runs for 37.79s = 113.389m. Obviously, the wolf runs 1/4 the circumference of a parabola with a wide side of 6m/s and a short side of 200m or vice-versa.
Sometimes what you're looking for is exactly where you left it.
Looking at it per sec. you can determine the new angle of
the wolf is approaching target.
t=1 :
arctg(angle) = x / y = 3/100
Then determine de x and y of the Place vector of the wolf.
Xwolf = 4 * sin(arctg(3/100))
Ywolf = 4 * cos(arctg(3/100))
t = 2 :
now you can do the same for the new triangle.
to get new angle:
arctg(angle) = x / y
where x has become : 6 - 4 *sin(arctg(3/100))
y : 100 - 4 * cos(arctg(3/100))
determine x and y of this new vector
and on and on...
maybe you can extrapolate it in a function with t and angle.
Now, How about altering the Problem, so that the Wolf and Chicken
start 10 LightSeconds from each other, the Wolf can run at
4 tenths of a LightSecond per second, The Chicken can run at 3
tenths of a LightSecond per Second, And you have to take into
account the Lag Between the Movement of the Chicken and the
actual time the Wolf sees the Chicken Move.
Since it seemed my progie worked, I plugged in 2 more sets of
value for WolfSpeed and ChickenSpeed. It seems that,
developing some equations and then testing them out with
furthur data sets, and double checking against my progie, the
following is the generic answer.
Code:
Assigning the following constants to their respective terms:
Wolf Speed = Ws
Chicken Speed = Cs
Initial distance Between Wolf and Chicken = WC_d
Final Travel Distance of the Chicken = C_d
Final Travel Distance of the Wolf = W_d
Then, it seems that:
C_d = Ws*Cs*WC_d / ( Ws2 – Cs2 )
W_d = Ws2*WC_d / ( Ws2 – Cs2 )
That's very impressive. You got the correct answer, but I'm not exactly sure how you did it? Did you try various forms until you got the correct answer? That's quite interesting. It looks like a difficult equation to just come up with by looking just examining data.
Good job.
It took me a long time to solve it analytically. And like I said before I can't understand how the original 'easy' solution was arrived at. Hopefully, someone will figure it out.
The way I developed the formula was somewhat simple.
Since I had the data for Ws = 4, Cs = 3, I decided to try
Ws = 2, Cs = 1, thinking that there could be a pattern revealed
useing such a simple set. And there was. I placed the data into
excel so you can see for yourself:
As you can see, with {1,2}, it jumps right out at you that
cfinal chickan distance plus the total distance the wolf traveled to
catch the chicken equals 200, twice that of the initial seperation.
Once I saw that, it was obvious that with {3,4}, the sum of the two equaled 400. So, it seemed that
C_d + W_d = Ws*WC_d
And, we also know that {Since Cs*time = C_d, and Ws*time = W_d}
the ratio Cs/C_D = Ws/W_d, since the travel time for the two are identical.
So, Solveing for independant equations for C_d and W_d, in terms of Cs, Ws, and WC_d, I got the following:
However, Once I saw that, I knew something was wrong.
It was apparant that if the chicken and the wolf ran at the same speed, the wolf would still catch the chicken.
Hmmm.
So, I then deceided to progie the data for Cs = 1, Ws = 3.
This is what I got:
As you can see, the sum of the chicken and wolf is 150, which is Half of Ws*WC_d. and as you can see , 2 = Ws - Cs, where in the first two data sets, Ws - Cs = 1.
So, another correlation.
Useing this, it seemed that
C_d + W_d = (Ws*WC_d) / (Ws - Cs)
Which, again in combination with Cs/C_D = Ws/W_d,
Gave me the following:
Which definetely made more sense in the case of Cs = Ws. {Div
By Zero means the wolf can't catch the chicken when they run at
the same speed}
So, then I decided to verify the equations, and useing Cs = 5, Ws = 7, saw that C_d = 145.8333333, and W_d = 204.1666667.
Then I ran my progie, and it also came up with the same results.
[edit] I now realize I should have used something else, where Ws - Cs <> 2 or 1, perhaps Ws = 11, Cs = 8. [/edit]
So, I assumed I had the right equations.
Of course, I never varied WC_d, so perhaps if they started at 50 instead of 100, there might have been another deviation, but
My brain was fried, decided to see what you said.
Now, the toughie is trying to develop the equation that projects
the path the wolf takes in X, Y coordinates. {I'm a weee bit stuck here! }
Something simpler, though would be altering your puzzle by
haveing the chicken run at a constant speed at other than a 90
degree angle.
Well, there's always tomorrow.
Last edited by NotLKH; Jun 27th, 2002 at 04:37 PM.
Now, the toughie is trying to develop the equation that projects
the path the wolf takes in X, Y coordinates. {I'm a weee bit stuck here! }
I think that given your past success you might be able to do it, though it may be difficult to just look at the numbers as they are. You might require a small bit of manipulation.
Something simpler, though would be altering your puzzle by haveing the chicken run at a constant speed at other than a 90 degree angle.
I'm working on that part now. I think I'm close to a solution. I'll post if I can figure it out. I think that solution is the key to figuring out how the original 'simple' solution was determined.
Huh,
Dontcha have any Q's about my Progie?
Guess not.
But, if your not up to snuff with Calc, this technique 'd probly help you with the Chicken angle prob.
Just through in a chicken_y, and some other stuff, well, never mind.
My problem is that in order to find the path of the Wolf, you need to know it's x and y co-ords (at least definitely the y co-ord). I can only see how to do this if the angle between the Wolf and Chicken is know. Unfortunately the angle is defined (inseparably) in terms of the x and y co-ords.
There are 10 types of people in the world - those that understand binary, and those that don't.
When I first noticed this Thread (several days ago), I expected to find an analytical solution in 15 minutes to an hour. After 2-3 hours (20-30 minutes at a time over two days), no analytical solution was in sight, so I wrote a VB application to find a numerical solution.
The numerical solution indicated that the chicken ran a little over 171 meters, which agrees with the NotLKH solution.
Over 50 years ago I encountered this problem on an examination, and did not have much trouble solving it. Ten or twenty years later, it came up again when I was helping the son of a friend with his college mathematics. It is a very standard differential equations problem, and should cause no problem for somebody currently taking a pertinent course. For somebody who never took such a course, it is a formidable (if not impossible) task to find an analytical solution.
BTW: The problem proposed to me years ago involved a bull and a man. The man was wearing a scarlet shirt and bright yellow pants. He was in a pasture alongside a high stone wall when he and the bull saw each other. The man ran toward an opening in the wall through which he had entered the pasture. This was the reason for the straight line path of the quarry. The bull was too dumb to realize where he was headed, so he charged toward the man, correcting his course as the man moved along the wall.
For my analytical solution, I started the man at the origin running along the X-Axis in the positive direction, with the bull starting on the Y-Axis 100 meters from the origin.
I was surprised that I could not recreate the solution which seemed so easy many years ago. After I post this, I will try again. I am sure I am missing something simple. Perhaps I should have the man run along the Y-Axis. It seems correct to have the quarry run along a coordinate axis, which simplifies his equation of motion.
In the original problem from many years ago, the bull did not start at a point perpendicular to the path taken by the man. In that problem, he started at coordinates like (50, 50) with the man starting at the origin. The bull’s path started toward the origin, curved toward the X-Axis, and then curved away from the Y-Axis, becoming asymptotic to the X-Axis as he started overtaking the man.
My numerical solution copes with various initial conditions, not requiring the bull to start at a point perpendicular to the man’s path.
Considering the problem with the quarry running along a line not perpendicular to the pursuer’s initial direction is equivalent to a different starting position for the pursuer. Some initial positions for the pursuer result in a path which has a later point at which the pursuer path is perpendicular to the quarry path.
NotLKH: My numerical solution agrees with yours, except for what I think is round off error. I wonder how close our methods were. I used very small time slices to calculate where the man and bull were at each instant. Using 524,288 (218) slices per second, I got a lower bound of 171.428576 and an upper bound of 171.428581 for the distance run by the quarry. In problems like this, a power of two is a good value for the number of time slices. It results in slightly better precision.
The exact values for the sum of the distances seems to me to be coincidental. Note that the ratio of the pursuer and quarry distances is equal to the ratio of their velocities since they both ran for the same amount of time. This increases the chance of some coincidental distance sums.
When I varied the velocities, I found a lot of problems with what looked like an irrational sum for the distances.
If I have some idlel time in the next few days, I might try to add a plot of the pursuer's path for the this problem.
BTW: I had a slight problem with determining reasonable conditions for terminating my computational loop.
Live long & prosper.
The Dinosaur from prehistoric era prior to computers.
Eschew obfuscation!
If a billion people believe a foolish idea, it is still a foolish idea!
VB.net 2010 Express
64Bit & 32Bit Windows 7 & Windows XP. I run 4 operating systems on a single PC.
Guv,'
I think the problem is that of being outside of an habitual
environment.
We know of the df/dy, and we know of an integration that
provides a length of area traveled. {based on time}
unfortunately, since the time of our teachings, our knowledge has
gone sour.
And, in reality, if we have had no need for such knowledge till
now, why should we require to retain such knowledge for the
future?
However, I am certain, if our jobs were to rely upon this, we
would, within a day or two, figure it out.
the distance covered by the chicken is x.
the distance covered by hte wolve is 100 + x.
speed = distance/time i.e S=d/t
speed of chicken : Sc=3 = x/t x is distance covered by chicken (1)
speed of wolve :Sw=4=(x+100)/t ........... (2)
time t is the same for both
from equation (1) t=x/3 ..................(3)
from equation (2) t=(100+x)/4 ........(4)
hence equation (1) = equation (2) since t is the same for both
i.e x/3 = (100+x)/4
from this we get x = 300 metres as the distance covered by the chicken.
substitute 300 for x in equation (3)
you get t = 300/3 =100 seconds..........that is the answer to your puzzle..............................................................................
Dylanzim: You solved a different problem. Your answer would be correct if the chicken had a 100 meter head start on a straight path.
In the problem for this thread, the wolf takes a curved path. He starts at a point 100 meters from the chicken on a line perpendicular to the chicken's straight line path.
Live long & prosper.
The Dinosaur from prehistoric era prior to computers.
Eschew obfuscation!
If a billion people believe a foolish idea, it is still a foolish idea!
VB.net 2010 Express
64Bit & 32Bit Windows 7 & Windows XP. I run 4 operating systems on a single PC.
I finally got around to writing up my solution, which was harder than I thought. But before reading it check out the 'easy' solution, which was originally posted on the website that I found the problem.
Compute the distance that the chicken would get if the chicken ran directly away from the wolf. Then compute the distance the chicken would get if the chicken ran directly at the wolf. Averaging those two distances gives you the answer.
It's amazing how simple the solution to this problem is. I still can't see how they arrived at it. Can anyone explain it? I'm still working on the more general problem of what happens if the chicken runs in a straight line at an arbitrary angle.
I put my solution into MS word to make it easier to read since there were a lot of equations.
Nice writeup. I never thort of using ds/dt as v of the wolf. Well done.
I think there may be a mistake from eq (12) to the following line which starts "which reduces to"..., namely I think it doesn't reduce to cos(theta). Did you mean cosec(theta)?
I'll read on after you reply...
There are 10 types of people in the world - those that understand binary, and those that don't.
Wy125: I am impressed with your solution. I thought I remembered it being easier, but it was over 50 years ago that I took a course in differential equations. Since I forgot how to do it, it would not be surprising if I also forgot how difficult it was.
I like a bull/man description of the problem instead of a wolf/chicken description. The man runs along a high stone wall toward the hole in the wall through which he entered a pasture. The bull always charges directly toward the man, changing course as the man moves. Given constant speeds for bull and man, treat bull & man as point objects. Analyze the pursuit problem, and determine where the bull overtakes the man, assuming the hole in the wall is too far away for the man to escape.
The bull/man description provides a reason for the straight line path of the quarry. I would always be distracted by wondering why a chicken would choose a straight line path other than one directly away from the wolf.
The skewed man path should be viewed from a different perspective. Your solution should be applicable. See below.
I suspect that the easy solution might be impossible to formally prove, although I think it is valid. Also see below.
There is a description of another interesting pursuit problem below.
The skewed man path is equivalent to changing the starting place for the bull. Think of the man as starting at the origin and running along the X-Axis in the positive direction. Starting points for the bull below the origin are trivial symmetric variants of corresponding starting points above the X-Axis, and will be ignored. There are three fundamentally different starting points for the bull. In each case, the bull moves toward the origin for an infinitesimal time interval.
Case 1: The bull starts at point in the first quadrant like (100, 100), (40, 70), or (150, 20). The bull path moves toward the Y-Axis, becomes vertical for an instant, and then moves away from the Y-Axis. The path always moves toward the X-Axis, and might seem to be asymptotic to it. It is not asymptotic if the bull runs faster than the man. The path is undefined after the bull catches the man. If the bull ran slower than the man or at the same speed, the path would be asymptotic to the X-Axis. Note that if the bull ran at the same speed as the man, there would be a time after which the bull and the man would appear to be running along the X-Axis a constant distance apart. The path of the bull would become an asymptote that appeared to be the X-Axis. If the man ran faster than the bull, there would be a time after which both seemed to be running along the X-Axis with the man getting farther and farther ahead.
Case 2: The bull starts at a point in the second quadrant like (-100, 100), (-40, 70), or (-150, 20). This type of path is similar to the latter part of a Case 1 path. I am almost certain that each path of this type is exactly equivalent to the latter part of some Case 1 path.
Case 3: The bull starts at a point on the Positive Y-Axis. This case is the subject of the thread. Note that all Case 1 paths have a point at which the bull path is vertical for an instant of time. From that point on, a Case 1 path looks like an entire Case 3 path. In fact, each case 3 path is exactly equivalent to the latter part of some Case 1 path.
Cases 1 & 2 are equivalent to a skewed man path.
Starting the man at the origin does not lose any generality. There might be a problem with case 1 due to an infinite derivative at the instant that the bull path is vertical. Perhaps there is some advantage to having the man run along the Y-Axis.
I wrote a VB application which solves any of the above cases by numerical approximation of the bull path. With small time slices (I used 524,288 slices per second), the results agree with the simple solution to about 8 significant digits (171.428575515 instead of 171.428571429).
For those who have not read all posts, the averaging method of solution applies to Case 3. It calculates the time required for a collision if the bull and the man run toward each other. It then calculates the timed required for the bull to overtake the man if the man always runs directly away from the bull. The average of these times is the solution to a Case 3 problem.
After some numerical experiments, I believe that the averaging method calculates the correct answer. I tried several sets of initial conditions. In each case the averaging method and the numerical integration method agreed, except for roundoff error.
Without verifying it via a proof or by comparison with results from a proven method, I would see no reason to accept the averaging method as valid.
I am convinced that the averaging method is valid, but I wonder if there is a way to prove it. It is my guess that any proof would be esoteric and difficult to grok. There might be no known proof.
The numerical integration method will work for cases 1 & 2. I doubt that any variation of the averaging method will work for these cases.
The numerical integration method is known to be valid for solving problems like this, and a convincing proof of this method can be developed. Comparing results for 10, 20, 50, 50,000 sets of initial conditions might convince almost anybody that the averaging method is also valid. However, this is not a proof that the method is valid. The millionth set of initial conditions might show that the two methods disagree. I would be surprised if a counterexample exists, but without a formal proof, can one be certain that the easy method is valid?
BTW: There is a cute differential equations problem involving pursuit which has an obviously valid easy solution. It is as follows.
Imagine four objects initially on the corners of a large square. Each pursues the counterclockwise object. Treat each object as a point whose course is corrected instantaneously, and assume that all move at the same speed. It is obvious that the four objects (perhaps guided missiles, falcons, bugs on a table, et cetera) are always on the corners of a square which contracts and rotates. The path of each object is a spiral, and the four objects meet at the center of the original square.
Given the speed of the objects and the size of the original square, determine how far each object travels before the collision at the center of the original square.
The differential equations solution to this one is easier than the bull/man pursuit problem. The following is the easy intuitive solution.
The velocity vector of each quarry and his pursuer are always orthogonal. Since no quarry has a velocity component toward or away from his pursuer, the motion of a quarry never results in an increase or a decrease in the distance between the quarry and his pursuer. Therefore the pursuer must travel the original distance separating himself from his quarry. The speed of the objects has no effect on the length of the paths. The distance traveled by each object is the length of one side of the original square.
In theory, the four objects spiral an unbounded number of times around the center of the square, although the length of the path is finite.
Live long & prosper.
The Dinosaur from prehistoric era prior to computers.
Eschew obfuscation!
If a billion people believe a foolish idea, it is still a foolish idea!
VB.net 2010 Express
64Bit & 32Bit Windows 7 & Windows XP. I run 4 operating systems on a single PC.
I may be meddling with forces I don’t understand here (please tell me if I’m wrong).
I approached this somewhat differently, can’t get a result, but the method may be simpler if not entirely incorrect. I’m trying to calculate the length of path of the wolf with respect to movement of the chicken.
On the graph with the wolf (or the bull) starting at y=(0,100), and the chicken(or man) at (0,0), I took a small change in y^2 to be: small movement by the wolf (dw) squared minus the equivalent small movement of the chicken (dc) squared.
Or dy = sqrt( (dw)^2 – (dc)^2)
Now sqrt( (dw)^2 – (dc)^2) = sqrt(((dw/dc)^2) - 1) * dc
And we know that dw/dc = 4/3.
So the equation can now be written as dy = sqrt(((4/3)^2) - 1) * dc
Or dy = sqrt((16 / 9) - 1) * dc
Or dy = sqrt(7/9)*dc
And so dy/dc = (7/9)^0.5
That’s where I get stuck as my nearest guess is:
Y=(2/3)*((7*chickenMovement)/9)^(3/2)
I feel that a value of y=100 should be given when chickenMovement = the answer.
And I can’t get anything like the accepted answer from this no matter how much I cheat.
Starman: The following might give you a clue. It is the calculation subroutine from a VB application I wrote to solve this problem numerically. I used 524,288 (219) time slices per second, which resulted in about 8 digits of precision.
I have omitted a lot of the application, and do not show some Dim Statements external to this Subroutine. The omitted details process user input of initial conditions.
The Latitude Function uses VB Atn Function to determine an angle. I use it to avoid problems with tangent of 90 degrees, and to get slightly more precision by only requiring the Atn Function to compute angles less than 45 degrees (Pi/4 radians).
If you draw a diagram, you can probably understand what is being calculated. The curved path taken by the bull/wolf is approximated by small distances along tangents to the curve. The small distance traveled by the bull/wolf in a time slice is the length of the hypotenuse of a right triangle. The legs of the triangle are the changes in XY coordinates. The man/chicken runs along the X-Axis.
The Subroutine will do computations for any reasonable starting point for bull/wolf. A starting point on Y-Axis is not required. Starting points off the Y-Axis are equivalent to a man/chicken path not perpendicular to initial velocity vector for bull/wolf (Id est: A skewed chicken/man path).
I might add a picture Box to the application and display a plot of the bull/wolf path.
VB Code:
Private Sub cmdCompute_Click()
Dim IterationTally As Double
Dim Angle As Double
Dim LastBullX As Double
Dim LastBullY As Double
Dim LastManX As Double
Dim ManDistance As Double
If BullSpeed > ManSpeed Then
'This is okay
Else
Junk = MsgBox("Bull is too slow: Try again")
Exit Sub
End If
'Unhide some text boxes used to hold calculated values.
Call ShowText
BullX = BullStartX
BullY = BullStartY
ManX = ManStart
Call ValueLoader 'Display some initial conditions.
The Dinosaur from prehistoric era prior to computers.
Eschew obfuscation!
If a billion people believe a foolish idea, it is still a foolish idea!
VB.net 2010 Express
64Bit & 32Bit Windows 7 & Windows XP. I run 4 operating systems on a single PC.
I think there may be a mistake from eq (12) to the following line which starts "which reduces to"..., namely I think it doesn't reduce to cos(theta). Did you mean cosec(theta)?
You around wy125?
There are 10 types of people in the world - those that understand binary, and those that don't.
Reply With Quote
Nope!
A paradox??
