34
$\begingroup$

Generally, in pursuit-evasion games, there's one prey and one or many pursuers. I'd like to know how extending the food chain would change the dynamics of such games.

Specifically, let's consider a closed, circular shape arena in $\mathbb{R}^2$. Three wolves are uniformly distributed at the border. The sheep and his lion friend are at the center.

enter image description here

If $d(w(t),s(t))=0$, the wolf eats the sheep, if $d(l(t),w(t))=0$, the lion eats the wolf, where w(t), s(t) and l(t) are the trajectories of the animals, and $d$ measures euclidean distance. The pack of wolves work as a group, their goal being to eat the sheep. The goal of the lion-sheep team is to prevent the sheep from being eaten, indefinitely. All animals move continuously in time at equal speed and are intelligent.

Can the lion protect the sheep from the wolves? In general, how many lions are necessary to protect the sheep from a pack of $N$ wolves uniformly distributed at the border?


This is a puzzle I originally asked here on puzzling.stackexchange. I know already that

  • A single wolf doesn't catch the sheep.
  • Two wolves will catch the sheep.
  • $N-1$ lions are sufficient to fend off $N$ wolves.

See here for the proof of those claims. I'm interested in knowing whether $N-2$ or less lions can fend off $N$ wolves.

$\endgroup$
15
  • 4
    $\begingroup$ The extraneous problem with this nice question is that when the lions get hungry they may eat the sheep themselves. $\endgroup$ Apr 6, 2022 at 13:54
  • 2
    $\begingroup$ For lion = N-2, can they just go after the closest wolf first to reduce the problem to N-1? $\endgroup$
    – Paichu
    Apr 6, 2022 at 16:42
  • 3
    $\begingroup$ On p.$135$ of his A Mathematician's Miscellany, J.E.Littlewood gives a plausible, but erroneous, argument purporting to show that a single lion can always catch a single wolf (which he calls a "man"). After noting that the argument is wrong, he gives A.S.Besicovitch's strategy for the wolf that enables it to avoid capture indefinitely $\endgroup$ Apr 8, 2022 at 14:57
  • 1
    $\begingroup$ Four clarifications seem necessary to answer: (i) Is the "top speed" of each entity the same? (This may be a convention for pursuit problems, but it's advisable to be explicit.) (ii) Does each entity move differentiably, or just continuously? (iii) Can the sheep and lion be at the same point, as described verbally? (If so, my first guess would be that they should stay together, possibly modulo the fourth clarification.) (iv) What happens if the sheep, one or more wolves, and the lion meet at a point? (Hopefully not a universe-creating explosion.... :) $\endgroup$ Apr 12, 2022 at 13:45
  • 2
    $\begingroup$ @AndrewD.Hwang Reaction is instantaneous, and the situation is symmetric: there's no "just before" to which the sheep can react but the wolves can't. $\endgroup$
    – Eric
    Apr 12, 2022 at 15:46

1 Answer 1

1
$\begingroup$

I like your problem. Let me summarize.

Is it possible for a lion to guard a sheep on a 2D plane against three wolves working as a team? This is for a video game scenario where all five animals travel at the same speed continuously and can all share the same coordinate. The wolves begin equidistantly apart. If the lion, the sheep and at least one wolf share the same coordinate, then the wolves win. All the lions begin at some point equidistance from each other to begin (an equilateral triangle).

I think I might have a proof, but would like it checked to be sure.

Theorem. It is possible for the lion to defend the sheep in this scenario so long as the following conditions are met: 1) the lion and the sheep run in a rotating elliptical orbit, having width a and length b, such that 2) the rotation of the ellipse is in the opposite direction that the lion and sheep run around the ellipse, 3) the wolves begin at a distance from the sheep greater than 2 times the distance of that between the lion and sheep, and 4) given

S_half=2a ∫_0^(π/2) 1-e^2 sin^2⁡(θ) dθ,

where S_half is half the distance around the perimeter of the ellipse, θ is maintained to be equal or greater than 2pi/3 radians.

Proof of the Theorem. Let a wolf and sheep begin on both the perimeter and the semi-minor axis of an ellipse whose width is a and length b, but on opposite sides from each other. Let the wolves be on the points of an equilateral triangle to begin. Let the triangle encompass the area of the ellipse, but not inscribed. Instead, align the lion to be directly between two of the wolves (on the perimeter of the triangle) and the sheep directly center of the triangle. Let this center point be the center of the cartesian plane in order to work out the math.

To begin, the lion and sheep run in a counter-clockwise motion on the ellipse whose theta is 120 degrees or greater (2pi/3 radians) the wolves will run in a straight line toward where the sheep is headed. If they run in any curved motion, this will be farther a distance to travel and the result will be even more advantageous for the lion and sheep. Because the lion is running in a curved motion, he charges two lions at the same time, the first to his left and also the next to his left as his curved run continues. Since the wolves must move continuously, they will need to curve their trajectory away from the curved run of the lion, which pushes them in the opposite direction from where the sheep will soon follow on the opposite side of the ellipse.

The third lion is the only one that can run in a straight line, as the lion is running in the opposite direction from it. However, since the third wolf began more than 2 times the distance from where the sheep was from the lion, and the theta is 120 degrees or greater (the arc is slight), he will return to where the sheep was prior before the third wolf can get the sheep. Since he will be coming in at a certain trajectory, the wolf must curve away in the opposite direction.

The cycle repeats as the lion curves once more toward the first wolf, but this time at a 60 degree pivot clockwise (assuming theta equals 120 degrees), and then the second as before. Since they are always pushed a greater distance away from the sheep, their distance will converge around a boundary. The direction of the wolves attack doesn’t matter, as it is assumed that would at most only one wolf at a time will be able to maintain a straight line attack. ∎

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .