14
$\begingroup$

In $\mathbb{R}^2$, a wolf is trying to catch two sheep. At time $0$ the wolf's at $(0,0)$ and the sheep are at $(1,0)$. The animals are moving continuously 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?

Technical note

To those who find the descriptions above somewhat ambiguous and subject to possible misinterpretations, we can reframe some terms in a more rigorous manner:

  • Continuous movement: we use $w(t)$, $s_1(t)$ and $s_2(t)$ to denote the animals' positions at time $t$. Call the functions $w, s_1, s_2$ the wolf path or the sheep path. They satisfy $$\vert w(t)-w(s)\vert \leq \vert t-s\vert, \vert s_i(t)-s_i(s)\vert \leq \frac{1}{2}\vert t-s\vert, i=1,2, \forall t,s\geq0,$$ with initial conditions: $w(0)=(0,0)$, $s_1(0)=s_2(0)=(1,0)$

  • Instantaneous reaction: intuitively we want each animal's choice of path (strategy) be as free as possible influenced only by the other players paths up to this moment. Let $W$ be the set of all wolf paths and $S_i$ the set of all sheep $i$ paths. Then

    • The wolf's strategy is a function $f_w$ from $S_1\times S_2$ to $W$ such that if $s,s'\in S_1\times S_2$ agree on $[0,t]$, then $f_w(s)$ and $f_w(s')$ also agree on $[0,t]$, $\forall t$.
    • The sheep's strategy is a function $f_{s}$ from $W$ to $S_1\times S_2$ such that if $w, w'\in W$ agree on $[0,t]$, then $f_{s}(w)$ and $f_{s}(w')$ also agree on $[0,t]$, $\forall t$.
$\endgroup$
13
  • $\begingroup$ Does the wolf catches the sheep in a whole number of steps? $\endgroup$ Commented May 9, 2023 at 15:02
  • 5
    $\begingroup$ The sheep will choose different paths because their aim is to delay the second sheep's death. I think Sheep 2 will stay the same distance from the wolf as Sheep 1, plus a tiny bit, until it can flee directly away from Sheep 1. Sheep 1 will somehow balance moving away from the wolf and away from Sheep 2. $\endgroup$ Commented May 9, 2023 at 15:24
  • 3
    $\begingroup$ A quick upper bound is 8 minutes, since the wolf can catch sheep 1 in two minutes, and at that point the second second sheep is a distance of at most 3 away and so can be caught in six more minutes. $\endgroup$ Commented May 9, 2023 at 18:24
  • 5
    $\begingroup$ @Tyler Seacrest. That's a useful comment. However, isn't Sheep 2 at most 2 away at that point? This gives an upper bound of 6 units of time in total. $\endgroup$ Commented May 9, 2023 at 18:55
  • 2
    $\begingroup$ On second thought, always going toward the closer sheep is probably not the right move. In some cases, it might be better for the wolf to try and corral the sheep toward each other so it can minimize the time needed to catch both sheep. $\endgroup$ Commented May 15, 2023 at 4:16

2 Answers 2

Reset to default
3
+50
$\begingroup$

(Too long for a comment.) As it is discussed in comments, the upper bound is $6$. The wolf being faster than the sheep by $1/2$ will catch this sheep within $2$ time units. Each sheep goes no more than $1$ during this time, therefore distance to the other sheep is at most $2$, and the wolf will catch it in $4$ time units.

My observation is that this upper bound doesn't depend on metrics. Also for Manhattan $L_1$ metrics this bound is reachable. If two sheep go in two different constant directions other than directly to the wolf (e. g., along the line $x = 1$ in the opposite directions), then the wolf will catch one of them exactly after $2$ time units (at the point $(1, \pm 1)$). The second one will be at distance $2$ at that moment and will not need to change anything to be alive for $4$ more time units (will be caught at the point $(1, \mp 3)$). Also both sheep may change direction with a simple restriction: not getting closer to the wolf and to each other.

For Chebyshov $L_{\infty}$ metrics situation is rather similar, however the strategy is a bit different. Now both sheep should move away from the wolf and at the same time away from each other. This is possible only when moving along lines $y = x - 1$ and $y = 1 - x$ with increasing $x$. Then the wolf will catch one of them at the point $(2, \pm 1)$. The second sheep may vary its $x$-speed keeping the same $y$-speed to be caught at $(x_2, \mp 3)$ for some $x_2 \in [0, 4]$. Also the second sheep could start changing $x$-speed before the wolf catches the first sheep. However it changes only the range of $x_2$ to $[-1, 4]$, not the total time.

If we have $3$ sheep instead of $2$ then situation will be rather similar for Manhattan $L_1$ metrics. Simple upper bound is $18$ and it is easily reachable. However $3$ sheep for Chebyshov $L_{\infty}$ metrics and $4$ sheep for Manhattan $L_1$ metrics are not so easy cases.

In $k$-dimensional space $s \le 2k-1$ sheep have a strategy to reach simple upper bound of $2 \cdot 3^{s - 1}$ time units for Manhattan $L_1$ metrics and $s \le 2^{k - 1}$ sheep have such strategy for Chebyshov $L_{\infty}$ metrics.

$\endgroup$
0
2
$\begingroup$

Inspired by @10010100102ohno from a puzzling stack exchange thread, I tried to code it up (though I'm not nearly as good a programmer; note I started with some GPT4 code). Here is what I came up with:

https://jsfiddle.net/pbzn1Lva/

The wolf strategy is simply to follow the closest sheep. The sheep strategy is to initially head in opposite directions, and then the sheep closer to the wolf slowly turns in a direction heading directly away from the wolf, and the farther sheep slowly turns in a direction away from the other sheep. This leads to a time of about 4.6. Niether the sheep nor wolf movement is optimal, but it was the best I could do and should be in the ball park.

$\endgroup$
5
  • 1
    $\begingroup$ Actually the code is not bad at all! I leave you my considerations here: 1) There is some numerical instability (epsilon, directional vector integration,L2 norm). This generates the wolf to change sheep target in the start two or three times, slowing it a bit. Maybe is a good idea to lock the target and keep it locked until the distance is "big enough". 2) Try to work in the integer domain as long as you can or use javascript "BigInt" type. If you feel brave enough you can try BigRational.js to work in Q. However I do not think that this point will really change something in the observation... $\endgroup$ Commented May 9, 2023 at 23:12
  • 1
    $\begingroup$ ...a part finer values at the end of the round. 3) Wolf d vector changes values immediately (dx and dy are assigned every round), but sheeps integrate over their d vector (dx and dy increase by some values proportional to distance to wolf/other sheep). The sheep d vectors normalized are then used to compute the next position. This calculation generates a kind of weighted average of direction to take based on all the distances calculated up to the actual round. At the start you can observe a sheep moving towards the wolf for a bit, maybe it is related! Anyway, great job Tyler! $\endgroup$ Commented May 9, 2023 at 23:25
  • 1
    $\begingroup$ I've come to think a discrete version, with simultaneous movement on the grid, would be an interesting puzzle. I'm thinking about the right step size: too long, then the problem becomes too easy; too short then the search tree becomes too long. If the step size is infinitely short, then the problem becomes continuous and identical to this one. $\endgroup$ Commented May 10, 2023 at 12:05
  • $\begingroup$ @Eric The problem with grid is that on the plane you can move in any direction. And on the grid you have a finite number of options. "Proof" that $\pi = 4$ is based on the same principle $\endgroup$ Commented May 15, 2023 at 15:57
  • 1
    $\begingroup$ @Smylis You are correct. Grid probably won't work as we desire. Discrete approximation actually requires two parameters: a stepwise radius r and a radian theta. $\endgroup$ Commented Jul 10, 2023 at 1:20

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.