How will the wolf catch the sheep in minimum time?

Question

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$.

Answer 1

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.

Answer 2

(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.