15
$\begingroup$

In a closed arena, three wolves are on the vertices of an equilateral triangle at the border. The sheep and his lion friend are at the center.

enter image description here

The wolf eats the sheep if their distance is $0$, and the lion eats the wolf if their distance is $0$, all happening in an instant. All creatures are points moving at equal speed. The wolves don't care about death, all they want is to get the sheep.

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


Edit

In response to answer and its comments: the sheep, the wolves and the lion are intelligent. They will take optimal actions. The goal of the wolves is to eat the sheep. The goal of the sheep-lion team is to prevent that from happening, indefinitely. Also notice that this game happens in real-time, so all movement are continuous.

Hint

If there's just one wolf, the wolf can never catch the sheep, although it can get arbitrarily to it. If there're two wolves, then the sheep is doomed. If the lion is present, it can protect the sheep from two wolves by simply driving one of the wolves away radially, and the sheep can handle the other one.

$\endgroup$
13
  • $\begingroup$ If wolf, sheep, and lion happens to be at the same position at the same time, who wins? $\endgroup$
    – justhalf
    Apr 3 at 6:56
  • $\begingroup$ @justhalf According to my description, in that case the sheep and the wolf both die. $\endgroup$
    – Eric
    Apr 3 at 7:30
  • 5
    $\begingroup$ It's especially in situations like this when I really like Vi Hart's suggestion that the singular and plural forms of "sheep" should be different, and that the best possible outcome would be achieved by changing the singular to "a shoop". $\endgroup$
    – Bass
    Apr 3 at 11:09
  • 1
    $\begingroup$ @Bass I didn't even realize that I misread the details, lol. I have always somehow thought that there are many sheep (although it doesn't make sense in the question) $\endgroup$
    – justhalf
    Apr 3 at 14:01
  • 1
    $\begingroup$ Do the two teams take turns moving in discrete time intervals or can they employ strategies that react instantly to the opponents' movements, e.g., "stay on the same horizontal line"? $\endgroup$
    – noedne
    Apr 4 at 5:43

2 Answers 2

3
$\begingroup$

Edit

so this answer was posted before the question was clarified and it was explicitly stated that the wolves are intelligent


so for the first part before we have N wolves I think the answer is

yes. (Provided that the sheep is intelligent, which is perhaps a bit of an assumption to make.)

because

The lion and sheep can start by going upwards (or due North) to the first wolf with the sheep just behind the lion. The wolf from the top heading towards the sheep is eaten by the lion just before the wolf can eat the sheep. Meanwhile the wolves from below are moving up towards the sheep (and the lion). so now the lion and sheep head leftwards, (or due West), and the distance between the sheep and the wolf on the left (or south west) becomes smaller than the distance between the sheep on the right (or south east). Now the sheep can stop for a moment so that the lion can place itself between the sheep and the closer wolf and eat it. After two wolves are eaten the sheep and lion again move so that the lion is between the sheep and the remaining wolf and again the wolf is eaten.

What about N wolves

I suspect that 1 lion is still enough provided that the distance between the lion and the sheep is infinitessimal and the lion is always just in front of the sheep, but I don't have a proof for this. The strategy would be to start by heading directly up (north) to the first wolf then head left (west) and eat the wolves in an anti-clockwise direction arount the circle. As they travel at the same speed the pursuing wolves from the East should never catch up with the sheep until the sheep and lion turn towards them.

This answer assumes that the wolves want to eat the sheep so much that they go directly to the sheep always and do not mind dying

$\endgroup$
6
  • 4
    $\begingroup$ What derives the conclusion that going upward will result in the wolf being eaten? The wolves don't mind dying, but I think from the question we can infer that the wolves also work together to achieve their goal of getting the sheep killed, and so will not just kill themselves for nothing if there is no advantage to it. So I was expecting some proof that whatever the north wolf does, the lion can eat it. $\endgroup$
    – justhalf
    Apr 4 at 12:31
  • $\begingroup$ @justhalf - ah I assume from the question that the wolves want the sheep so much that they go directly to it and don't care about getting eaten on the way.... - so your comment suggests that the wolves work together and are intelligent... $\endgroup$
    – tom
    Apr 4 at 12:45
  • 1
    $\begingroup$ I feel something is wrong in this part: 'just before the wolf can eat the lion' Possibly you meant 'before the wolf can eat the sheep'...? :) $\endgroup$
    – CiaPan
    Apr 4 at 13:05
  • 1
    $\begingroup$ In fact, if the wolves were unintelligent and always ran straight toward the sheep, I think the sheep would be able to avoid being eaten without the lion's help. $\endgroup$
    – noedne
    Apr 4 at 14:45
  • 2
    $\begingroup$ Without details on levels of cooperation between wolves being established, this is the best answer we can really get. With cooperation and planning, Number of Lions + 1 = number of wolfs, will be able to coordinate an opening if all speeds are equal (though the wolf to get the sheep likely won't escape after). Currently it doesn't appear the wolves avoid the lion in any way in this question though. $\endgroup$ Apr 4 at 15:25
2
$\begingroup$

This is not an answer, but I'll try to prove the claims in the hint, and hopefully offer some helpful perspective.

First, a single wolf does not catch the sheep, even without the lion.

Let's say the speed of the animals is 1. The strategy of the sheep is to wait at the center $O$ until the wolf gets very close, say at $W_0$. It then chooses some $O'$ on the extension of the segment $OW_0$, and moves in the direction perpendicular to the line $O'O$ for $t_1$ amount of time to point $S_1$. Notice that the wolf can't catch the sheep while it's moving from $O$ to $S_1$.

enter image description here

When the sheep is at $S_1$, it notices that the wolf's at position $W_1$, and moves in the direction perpendicular to the line $O'S_1$ for for $t_2$ amount of time to point $S_2$. Of the two possible perpendicular directions, he chooses the one such that $\angle W_1S_1S_2\geq \pi/2$. Notice that the wolf can't catch the sheep while it's moving from $S_1$ to $S_2$.

At $S_2$, the sheep repeat the process above to arrive at $S_3$, then repeat again and again, ad infinitum to $S_{\infty}$. Notice that on no segment $S_iS_{i+1}$ can the wolf catch the sheep!

If the sheep lets $t_i=\Delta t/i$, then the total distance traveled by the sheep in this fashion is $$ \Delta t\left (1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\ldots\right)=\infty $$

But the length of $O'S_n$ is $$ \sqrt{{|O'O|}^2+\Delta t^2 \left[1+\left(\frac{1}{2}\right)^2+\ldots+\left(\frac{1}{n}\right)^2\right]} $$

which when $n$ goes to infinity is just $$ \sqrt{{|O'O|}^2+\Delta t^2\cdot\frac{\pi^2}{6}} $$

By taking say $OS_1=0.1$ and $\Delta t=0.1$, the sheep ensures that the chase is confined in a very small area, while it takes forever for the wolf to catch him.


Second, two wolves always catch the sheep, if there's no lion to offer help.

enter image description here

The wolves first move themselves to the projections of the sheep on x and y axis. From there $W_1$ keeps it's projection on the x axis the same as the sheep's, and uses any extra speed in moving towards the sheep in the y direction. $W_2$ acts similarly.

Let $v_x$ and $v_y$ be the speeds of the projections. Since the initial distance between $W_2$ and $S$ is at most the radius of the arena $R$, if the sheep is to avoid being caught, the total length of time for which $v_x\geq \sqrt{2}/2$ can't be greater than $\sqrt{2}R$. Similar reasoning for $W_1$ shows that the total length of time for which $v_y\geq \sqrt{2}/2$ can't be greater than $\sqrt{2}R$, either. But notice that the animals move at speed 1 means that $v_x^2+v_y^2=1$, which means if $v_x\geq \sqrt{2}/2$ then $v_y\leq \sqrt{2}/2$, and vice versa. This means after the wolves moved themselves to the projections, the sheep must be caught in no more than $2\sqrt{2}R$ amount of time.


Third, one lion safeguards the sheep from two wolves

The lion choose to stay on the segment connecting one of the wolves and the center of the arena, and uses any extra speed to move radially outward towards the wolf, thus keeping it far away from the center. The other wolf can be handled by the sheep as shown in the first case above.

enter image description here

$\endgroup$
12
  • $\begingroup$ I don't follow the one-wolf case. This just seems to show that no matter how long or far the sheep runs, it's always a finite distance from the wolf, which seems like a trivial result as both must remain in the circle. I don't see how that proves whether or not the wolf can catch the sheep. $\endgroup$ Apr 5 at 15:38
  • $\begingroup$ In the first diagram, how did the wolf end up between the center and the sheep when the sheep was the one waiting at the center? $\endgroup$
    – noedne
    Apr 5 at 16:18
  • 1
    $\begingroup$ @noedne The sheep waits near the center but not at the center. He can maneuver his movement to let the wolf in between. But even this is not necessary, since the sheep can just draw any circle in his mind with the wolf between its center and himself, and the argument still holds. $\endgroup$
    – Eric
    Apr 5 at 16:38
  • 1
    $\begingroup$ @Eric Thanks, I understand much better now. Although, now I wonder about the effect of the boundary. Suppose in the example when the sheep starts to move due north from S1 to S2, the wolf also moves due north, (arbitrarily close to) parallel to it. Eventually the sheep will hit the edge of the circle and will be unable to continue its strategy - you've convinced me this works on an infinite plane, but does it work in an enclosed space? I'd think the wolf could drive the sheep to the edge by keeping the angle of WS1S2 as close to 90 degrees as possible. $\endgroup$ Apr 6 at 15:08
  • 1
    $\begingroup$ @NuclearHoagie There're two perpendicular directions to go at each $S_i$: one up and one down. Don't forget that the sheep always chooses to go in the direction such that $\angle W_iS_iS_{i+1}\leq \pi/2$. If the wolf goes near parallel, the sheep would head back southward obeying the $\pi/2$ constraint. $\endgroup$
    – Eric
    Apr 6 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.