Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
A wolf is trying to catch two sheep. At time $0$ the wolf's at $(0,0)$ and the sheep are at $(1,0)$. All animals move continuously in real time and react instantaneously according to each other's positions. Wolf speed is $1$ and sheep speed is $1/2$. The wolf catches a sheep if their distance is $0$.
The wolf wants to catch the pair of sheep in minimum time. The sheep want to maximize that time.
Question: How does everyone move?
Originally posted on math.stackexchange.
Descriptive answer, using logic to determine the optimal strategies.
1/ The wolf will catch the nearest sheep first (:sheep1)
- Catching a further away sheep will cost more time, and allow the sheep to get further away from each other, so is suboptimal
2/ The other sheep (:sheep2) will make sure not to get closer to the wolf then sheep1
- Then the wolf will save time by switching to catch sheep2; which the sheep obviously will prevent
All have perfect information; they can thus determine the position S1 (where sheep1 is caught) and S2 (where sheep 2 is cought)
3/ The wolf will move straight to S1 and then straight to S2 .
- Any detour just costs time
4/ Sheep 1 will move straight to S1
- Since S1 is the optimal point by definition, any detour or ending up in any other point is suboptimal for the sheep.
The direction of sheep1 to S1 and the wolf to S1 will make an angle a
The direction of sheep1 to S1 and the wolf from S1 to S2 will make an angle b
5/ The angle a and b will be the same, otherwise the total time would be higher if the sheep had choosen a direction closer to (a+b)/2
6/ Since sheep 2 moving closer to the wolf then sheep 1 is suboptmal for the sheep, the line S1-S2 will end up touching the unity circle.
- This since the collection of circles with origin Wolf(t) and radius |Wolf(t)-Sheep1(t)| does that.
Thus (see picture 1)
- cos(2a) = 1/2x
- 2x = x cos(a) + sqrt(1-xsin2(a))
this yields a = 26.673 degrees / x = 0.8373
7/ Sheep 2 will maximize it distance with sheep 1 , while making sure not to get closer to the wolf then sheep 1
This will lead to a curved path where the distance wolf-sheep1 equals the distance wolf-sheep2 until the line S1S2 is reached. (see picture 2 , rotated for convenience)
The exact path of sheep2 still needs to be calculated by some computer program.. (at least I do not think it will be an easily integrated function)
Tried my hand at it. I saw no specified units so I assumed millennia and microns.
The sheep have the ability to choose what point the first capture happens at, within the bounds of what they are capable of reaching in time. Each sheep will additionally be balancing the advantage of running away from the wolf with the advantage of running away from each other. Actually, that's not quite right as the furthest sheep is really trying to get as far away as possible from where the other sheep gets captured.
I assumed the lower of the two sheep would be first to die, and it chooses to run at some angle down and to the right. The second Sheep has two goals during this first phase. Most important is he must remain the further of the two sheep from the wolf. Technically he could be an infinitesimally small distance further than his counterpart, so for purposes of our analysis we will think of them as equidistant from the wolf for this phase. His second goal is to get as far as possible from the point where the first sheep will be captured.
Eventually there will be a point where the second sheep is no longer close enough to the wolf to be a contender with the first sheep. I consider this the end of phase 1.
Phase 2 is the period up until the first sheep is overtaken. The wolf and sheep 1 will continue on their straight paths until meeting up. Sheep 2 is running a straight line away from the capture point.
Phase 3 is simple enough, the wolf makes a (physics-breaking) turn and pursues the second sheep in a direct path. It ends with the second sheep being captured
The ideal Sheep starting angle appears to be 156.08 deg (or depending on where you define it, 23.92 deg). Phase 1 ends at time 0.59167. The first capture point is (1.55707,-0.24709) at time 1.21882. The second capture point is (0.62713,0.79976) at time 3.08581. Excuse me, 3.08581 millennia. I hope my program stayed accurate enough where all those decimals are reliable... it's kinda hard to tell.
I have very little to say about that curved path. It starts at the same angle as the straight sheep's path, just mirrored. It ends tangent to the straight path the 2nd sheep ends up running afterward. I'm sure there's some "real" math in between but I have no idea what it would be. My code used Newton's method to solve for the angle that made the sheep remain equidistant from the wolf.
Just a weird note, I don't actually think this is the only way the pursuit would happen. I treated the sheep as being equidistant during phase 1 which means there shouldn't be a meaningful difference if we suddenly switched which sheep was technically closest in the middle of that phase. The sheep would exchange strategies and the wolf would change direction but I think that wouldn't effect the capture times. That would change the capture coordinates, of course. Assuming any of that's true then there should be a strategy where both sheep travel an identical path up until phase 1 ends and one of the sheep is chosen permanently. I wonder if that would make the math easier or worse.
Note that While this doesn't serve as a intented answer, this is intended to help the others to solve it if there is a way with pure math. Because I'm unable to provide a solution using purely mathematical methods. I can propose a programming-based solution, but I'm uncertain about its validity according to OP.
The upper bound is
6
where
One sheep takes 2 units of time to be caught, while the other sheep moves in the opposite direction towards to the wolf to increase the distance between them, after the wolf catches the first, then it will take an additional 4 units of time. I won't go into the details as it is easily understandable.
Of course there is an assumption to find the upper bound:
The second caught sheep will not be caught while passing through the wolf and the wolf ignores the second sheep while the wolf is after the first,
If we go back to the original question;
At all times,
the primary wolf pursues the sheep that is closest to it. If a wolf chooses to chase one sheep, it should maintain its direction until the second sheep becomes closer than the one it is currently pursuing.
Therefore
the sheep should consider this fact as well.
as a graphical representation;
please note that
The movements of the wolf are represented by blue, the first sheep is indicated by green, and the second sheep's movements are shown in orange.
this shows how the first sheep is caught:
When the wolf approaches, both sheep begin to move away. If the wolf pursues one sheep, that sheep will attempt to create as much distance as possible from the other sheep. Meanwhile, the second sheep ensures that it maintains a distance from the wolf that is always greater than or equal to the distance between the wolf and the first sheep. As a result, such a graph should be formed.
After the first sheep is caught, the rest is
a straight line between the second sheep and the wolf and should be easily calculated.
The wolf chooses one sheep and follows it, via dynamic Pro-Nav, at continuously random speeds, switching to the second sheep only after the first is taken.
The two sheep follow a dynamic Pro-Nav towards a point that is opposite to the vector sum of the two other bodies, also at continuously random speed.
