# Escaping an Infinitude of Lions

Mikkel Abrahamsen Basic Algorithms Research Copenhagen (BARC), University of
Copenhagen, Denmark<EMAIL_ADDRESS>MA was supported by
Advanced Grant DFF-0602-02499B from the Independent Research Fund Denmark
under the Sapere Aude research career programme. CWN was supported by the
Starting Grant DFF-7027-00050B from the Independent Research Fund Denmark
under the Sapere Aude research career programme.  Jacob Holm∗ Eva Rotenberg
Technical University of Denmark<EMAIL_ADDRESS>Christian Wulff-Nilsen∗

###### Abstract

We consider the following game played in the Euclidean plane: There is any
countable set of unit speed lions and one fast man who can run with speed
$1+\varepsilon$ for some value $\varepsilon>0$. Can the man survive? We answer
the question in the affirmative for any $\varepsilon>0$.

#### Note:

A preliminary version of this paper was part of the paper [1]. After the
publication of this paper [2], it has come to our attention that Chernous’ko
[6] proved already in 1976 that a fast man can escape any finite number of
lions. It seems that the same technique can be used to escape from an infinite
set. For work on a related game and more references, see the paper by
Ibragimov, Salimi, and Amini [11].

##  1 Introduction

“A lion and a man in a closed circular arena have equal maximum speeds. What
tactics should the lion employ to be sure of his meal?”111The curve of pursuit
($L$ running always straight at $M$) takes infinite time, so the wording has
its point. These words (including the footnote) introduce the now famous lion
and man problem, invented by R. Rado in the late 1930s, in Littlewood’s
_Miscellany_ [14].

It was for a long time believed that in order to avoid the lion, it was
optimal for the man to run on the boundary of the arena. A simple argument
then shows that the lion could always catch the man by staying on the radius
containing the man while approaching him as much as possible. However, A. S.
Besicovitch proved in 1952 that the man has a very simple strategy (following
which he will approach but not reach the boundary) that enables him to avoid
capture forever no matter what the lion does. See [14] for details.

One can prove that two lions are enough to catch the man in a circular arena,
and Croft [7] proved that in general a necessary and sufficient number of
birds to catch a fly inside an $n$-dimensional spherical cage is just $n$
(again, we assume that the fly and the birds are points with equal maximum
speeds).

Rado and Rado [15] and Janković [12] considered the problem where there are
many lions and one man, but where the game is played in the entire unbounded
plane. They proved that the lions can catch the man if and only if the man
starts in the interior of the convex hull of the lions. Inspired by that
problem, we ask the following question: What if the lions have maximum speed
$1$ and the man has maximum speed $1+\varepsilon$ for some $\varepsilon>0$? We
prove that for any $\varepsilon>0$ and any countably infinite set of lions,
such a fast man can survive forever provided that he does not start at the
same point as one of the lions. We find this result surprising. Indeed, it is
difficult to imagine how that man proceeds if, say, he starts at the point
$(\sqrt{2},0)$ and there are lions at all points with two rational
coordinates. In Section 2, we state the theorem and show how it follows from a
technical lemma. In Section 3, we prove the technical lemma.

Lion and man games with a fast man have been considered previously. Ramana and
Kothari [16] and Bakolas [4] studied variants with one or more lions that
catch the man if he is within a certain positive distance from a lion. Here,
the movements of the man and the lions are also restricted in other ways than
just limiting the speeds. Flynn [8, 9] and Lewin [13] studied the problem
where there is one lion and one fast man in a circular arena. The lion tries
to get as close to the man as possible and the man tries to keep the distance
as large as possible. Variants of the cop and robber game (a discrete version
of the lion and man game played on graphs) where the robber is faster than the
cops have also been studied. See for instance [3, 10].

###  1.1 Definitions

We follow the conventions of Bollobás et al. [5] for games with one lion and
one man. Let $R\subseteq\mathbb{R}^{2}$ be a region in the plane on which the
game is to be played, and assume that the lion starts at point $l_{0}$ and the
man at point $m_{0}$. We define a _man path_ to be a function
$m\colon[0,\infty)\longrightarrow R$ satisfying $m(0)=m_{0}$ and the Lipschitz
condition $\lVert m(s)-m(t)\rVert\leq(1+\varepsilon)\cdot\lvert s-t\rvert$ for
some small $\varepsilon>0$. Note that it follows from the Lipschitz condition
that any man path is continuous. A _lion path_ $l$ is defined similarly, but
with $\varepsilon=0$, i.e., the lion always runs with (at most) unit speed.
Let $\mathcal{L}$ be the set of all lion paths and $\mathcal{M}$ be the set of
all man paths. Then a _strategy_ for the man is a function
$M\colon\mathcal{L}\longrightarrow\mathcal{M}$ such that if
$l,l^{\prime}\in\mathcal{L}$ agree on $[0,t)$, then $M(l)$ and $M(l^{\prime})$
also agree on $[0,t]$. This last condition is a formal way to describe that
the man’s position $M(l)(t)$, when he follows strategy $M$, depends only on
the position of the lion at points in time before time $t$, i.e., he is not
allowed to act based on the lion’s future movements. (By the continuity of the
paths, it does not matter whether these time intervals are open or closed.) A
strategy $M$ for the man is _winning_ if for any $l\in\mathcal{L}$ and any
$t\in[0,\infty)$, we have that $M(l)(t)\neq l(t)$. Similarly, a strategy for
the lion $L\colon\mathcal{M}\longrightarrow\mathcal{L}$ is winning if for any
$m\in\mathcal{M}$, we have that $L(m)(t)=m(t)$ for some $t\in[0,\infty)$.
These definitions are extended to games with more than one lion in the natural
way.

It might seem unfair that the lion is not allowed to react on the man’s
movements when we evaluate whether a strategy $M$ for the man is winning.
However, we can give the lion full information about $M$ and allow it to
choose its path $l$ depending on $M$ _prior_ to the start of the game. If $M$
is a winning strategy, the man can also survive the lion running along $l$.

We call a strategy of the man $M$ _locally finite_ if it satisfies the
following property: if $l$ and $l^{\prime}$ are any two lion paths that agree
on $[0,t]$ for some $t$, then the corresponding man paths $M(l)$ and
$M(l^{\prime})$ agree on $[0,t+\delta]$ for some $\delta>0$. (We allow
$\delta$ to depend on $l|_{[0,t]}$.) Informally, a strategy is locally finite
if at any point in time the man commits to doing something for some positive
amount of time in the future dependent only on the situation in the past. In
particular, the strategy is _not_ locally finite if it involves staying at a
fixed distance from the lion or other behaviors that require the man to react
instantly based on the lion’s actions.

Bollobás et al. [5] proved that if the man has a locally finite winning
strategy, then the lion does not have any winning strategy. The argument
easily extends to games with multiple lions. At first sight, it might sound
absurd to even consider the possibility that the lion has a winning strategy
when the man also does. However, it does not follow from the definition that
the existence of a winning strategy for the man implies that the lion does not
also have a winning strategy. See the paper by Bollobás et al. [5] for a
detailed discussion of this (including descriptions of variants of the lion
and man game where both players have winning strategies). The winning strategy
of the fast man against finitely many lions is locally finite, so it follows
that the lions do not have a winning strategy. In fact, the man’s strategy
satisfies the stronger condition that it is _equitemporal_ , i.e., there is a
$\sigma>0$ such that the man at any point in time $i\cdot\sigma$, for
$i\in\mathbb{N}_{0}$, decides his behavior until time $(i+1)\cdot\sigma$. This
is a special case of a locally finite strategy since at time
$t\in[i\cdot\sigma,(i+1)\cdot\sigma)$, the man commits to doing something in
the future interval $(t,(i+1)\cdot\sigma]$. However, as the number of lions
tends to infinity, $\sigma$ tends to $0$, so the winning strategy against
infinitely many lions is not locally finite, and the lions might have a
winning strategy as well.

##  2 Main Theorem

######  Theorem 1.

In the Euclidean plane, for any $\varepsilon>0$, let a man able to run at
speed $1+\varepsilon$ start at a point $m_{0}$ and a unit speed lion start at
a point $l_{i}(0)\neq m_{0}$ for each $i\in\mathbb{N}$. Then the man has a
winning strategy against these infinitely many lions.

In the rest of the article, we adopt the setting of Theorem 1. We use $M_{n}$
to denote a strategy (to be defined later) of the man against $n$ lions
starting at the points $l_{1}(0),\ldots,l_{n}(0)$. We assume that we are given
arbitrary lion paths $l_{1},l_{2},\ldots$ such that $l_{i}$ starts at the
point $l_{i}(0)$. With slight abuse of notation, we also use $M_{n}$ to denote
the man path prescribed by strategy $M_{n}$ against the lion paths
$l_{1},\ldots,l_{n}$, that is, $M_{n}$ is shorthand for the formally correct
notation $M_{n}(l_{1},\ldots,l_{n})$.

In order to prove the theorem, we make use of the following technical lemma,
the proof of which is deferred to Section 3.

######  Lemma 2.

In the Euclidean plane, for any $\varepsilon>0$, let a man able to run at
speed $1+\varepsilon$ start at a point $m_{0}$ and a unit speed lion start at
a point $l_{i}(0)\neq m_{0}$ for each $i\in\mathbb{N}$. Let a sequence
$(\delta_{i})_{i\geq 2}$ of positive real numbers be given. For every
$n\in\mathbb{N}$, there is a strategy $M_{n}$ for the man against $n$ lions
starting at points $l_{1}(0),\ldots,l_{n}(0)$ with the following properties:

  1. 1.

There is a _safety distance_ $c_{n}>0$ such that while following $M_{n}$, the
man maintains distance at least $c_{n}$ from lion $l_{n}$.

  2. 2.

If $n\geq 2$, then $\|M_{n-1}(t)-M_{n}(t)\|\leq\delta_{n}$ at any time $t$.

  3. 3.

$M_{n}$ depends on $\delta_{i}$ only for $i\in\\{2,\ldots,n\\}$.

We now show how Theorem 1 follows from the lemma.

###### Proof of Theorem 1..

We define a sequence $(\delta_{i})_{i\geq 2}$ inductively, as follows. Suppose
that for some $n\geq 2$, we have already defined $\delta_{i}$ for all
$i\in\\{2,\ldots,n-1\\}$. By Lemma 2 (note in particular the use of property
3), these values of $\delta_{i}$ yield strategies $M_{1},\ldots,M_{n-1}$ with
associated safety distances $c_{1},\ldots,c_{n-1}$. We then define

$\delta_{n}:=\min\left\\{1/2^{n},\min_{i\in\\{1,\ldots,n-1\\}}\frac{c_{i}}{2^{n-i+1}}\right\\}.$

We now claim that the resulting sequence of strategies $M_{1},M_{2},\ldots$
converges to a winning strategy $M_{\infty}$. Note that for any
$n,m\in\mathbb{N}$, where $n<m$, we have

$\|M_{n}(t)-M_{m}(t)\|\leq\sum_{i=n}^{m-1}\|M_{i}(t)-M_{i+1}(t)\|\leq\sum_{i=n}^{m-1}1/2^{i+1}<1/2^{n}.$

Hence, the sequence $(M_{n}(t))_{n\in\mathbb{N}}$ is a Cauchy sequence and
converges to some point $M_{\infty}(t)$.

We need to ensure that $M_{\infty}(t)$ moves with speed at most
$1+\varepsilon$. This is indeed the case since for any two points in time
$s,t$, we have for any $n$ that
$\|M_{n}(s)-M_{n}(t)\|\leq(1+\varepsilon)\cdot|s-t|$. Therefore, it must also
be the case that
$\|M_{\infty}(s)-M_{\infty}(t)\|\leq(1+\varepsilon)\cdot|s-t|$.

Finally, we need to verify that $M_{\infty}$ is winning. To this end, we see
that for any lion $l_{i}$ and strategy $M_{n}$ where $i\leq n$, we have

$\displaystyle\|M_{n}(t)-l_{i}(t)\|\geq{}$
$\displaystyle\|M_{i}(t)-l_{i}(t)\|-\sum_{j=i}^{n-1}\|M_{j}(t)-M_{j+1}(t)\|$
$\displaystyle\geq{}$ $\displaystyle c_{i}-\sum_{j=i+1}^{n}\delta_{j}\geq
c_{i}\left(1-\sum_{j=1}^{n-i}1/2^{j+1}\right)>c_{i}/2.$

It follows that $M_{n}$ is winning against the lions $l_{1},\ldots,l_{n}$.
Furthermore, as the man maintains distance at least $c_{i}/2$ from $l_{i}$
using any strategy $M_{n}$, $i\leq n$, we obtain that the limiting strategy
$M_{\infty}$ maintains the same distance, so $M_{\infty}$ is indeed winning
against all the lions. ∎

As a side remark, we note that it follows from the proof that using the
strategy $M_{n}$ against a finite number $n$ of lions, the man is able to
maintain the distance $d_{n}:=\min\\{c_{1}/2,\ldots,c_{n}/2\\}$ from every
lion $l_{1},\ldots,l_{n}$. Thus, if the $n$ lions and man are disks with
radius less than $d_{n}/2$, the man is still able to win.

##  3 Proof of Lemma 2

We first give a high-level description of the proof. We proceed by induction
on $n$. The strategy $M_{n}$ yields a curve consisting of line segments all of
the same length.

Let $\varepsilon_{n}:=(1-2^{-n})\cdot\varepsilon$ so that
$\varepsilon_{n}<\varepsilon$ for all $n$ and
$0<\varepsilon_{1}<\varepsilon_{2}<\cdots$. We define the strategy $M_{n}$
such that the man runs at constant speed $1+\varepsilon_{n}$ when following
$M_{n}$. Inductively, we know the previous strategy $M_{n-1}$ by which the man
runs at speed only $1+\varepsilon_{n-1}$. We place _milestones_ at the curve
defined by $M_{n-1}$ equidistantly at distance at most $\delta_{n}/2$. When
using strategy $M_{n}$, the man runs toward the milestones one by one, so that
at any time $t$, he is close to the point $M_{n-1}(t)$ where he would be when
following strategy $M_{n-1}$.

Using strategy $M_{n}$, the man runs with speed $1+\varepsilon_{n}$, i.e.,
slightly faster than when using strategy $M_{n-1}$. This gives time to make
some detours caused by the lion $l_{n}$ while still being close to the
milestone prescribed by strategy $M_{n-1}$. If $l_{n}$ gets too close, the man
makes an _avoidance move_ , keeping a safety distance $c_{n}$ from $l_{n}$.
Intuitively, when performing avoidance moves, the man runs counterclockwise
around a circle of radius $c_{n}$ centered at the lion $l_{n}$. After a
limited number of avoidance moves, the man can make an _escape move_ , where
he simply runs toward the milestone defined by the strategy $M_{n-1}$.

By choosing $c_{n}$ sufficiently small, we can make sure that the detour
caused by the lion $l_{n}$ is so small that it can only annoy the man once in
between any neighboring pair of milestones. It is then possible to ensure that
he will be within distance $\delta_{n}$ from the position defined by strategy
$M_{n-1}$ at any time, as required by the lemma.

###### Proof of Lemma 2.

We assume without loss of generality that $\varepsilon<1$. We define
strategies $M_{1},M_{2},\ldots$ such that $M_{n}$ is a strategy for a man
starting at point $m_{0}$ against $n$ lions starting at points
$l_{1}(0),\ldots,l_{n}(0)$. We define these strategies so that $M_{n}$ has the
following properties in addition to the properties 1–3 stated in the lemma:

  1. 4.

The man is always running at speed $1+\varepsilon_{n}$, where
$\varepsilon_{n}:=(1-2^{-n})\cdot\varepsilon$.

  2. 5.

Let $t_{i}:=i\cdot\sigma_{n}$ for some $\sigma_{n}$ to be defined. The path
defined by $M_{n}$ is a polygonal chain with corners
$M_{n}(t_{0}),M_{n}(t_{1}),\ldots$ and each segment has the same length
$\|M_{n}(t_{i})-M_{n}(t_{i+1})\|=\sigma_{n}\cdot(1+\varepsilon_{n})$.

  3. 6.

The point $M(t_{i+1})$ can be determined from the positions of the man and the
lions $l_{1},\ldots,l_{n}$ at time $t_{i}$.

Properties 4–6 imply that the strategy is equitemporal and hence locally
finite, as explained in the Introduction. We prove the statement by induction
on $n$. For $n=1$, the man will run on the same ray all the time with constant
speed $1+\varepsilon_{1}=1+\varepsilon/2$. The man runs directly away from the
lion, i.e., in direction $m_{0}-l_{1}(0)$, and we define $\sigma_{1}:=1$. This
strategy obviously satisfies the stated properties. Assume now that a strategy
$M_{n-1}$ with the stated properties has been defined.

The strategy $M_{n-1}$ defines a path consisting of segments of length
$\ell:=\sigma_{n-1}(1+\varepsilon_{n-1})$. On each segment we place
_milestones_ equidistantly (including at the endpoints) so that the segment is
divided into $p:=\left\lceil\frac{\ell}{\delta_{n}/2}\right\rceil$ pieces. The
length of each piece is then $\ell/p\leq\delta_{n}/2$. At any time $t$, the
succeeding milestone that the man would pass when following the strategy
$M_{n-1}$ is the point

$g(t):=M_{n-1}\left(\left\lfloor\frac{t}{\sigma_{n-1}/p}+1\right\rfloor\cdot\sigma_{n-1}/p\right).$

By property 6, the man can at any time $t$ compute the point $g(t)$.

We now describe the strategy $M_{n}$, where the man also has to avoid the lion
$l_{n}$. We first describe the intuition behind the strategy without
specifying all details, and later give a precise description.

Informally, the strategy $M_{n}$ is to attempt to run as according to the
strategy $M_{n-1}$. Thus, at any time $t$, the man’s goal is to run toward the
point $g(t)$. However, the lion $l_{n}$ might prevent him from doing so.
Compared to $M_{n-1}$, the man has now increased his speed by
$1+\varepsilon_{n}-(1+\varepsilon_{n-1})=2^{-n}\varepsilon$, so he has time to
take detours while still following the strategy $M_{n-1}$ approximately. Note
that the goal $g(t)$ that the man is attempting to reach will change at any
point in time $t$ that is a multiple of $\sigma_{n-1}/p$.

Assume that we have defined the man’s strategy $M_{n}$ up to time $t$. We use
$m(t)$ as shorthand for $M_{n}(t)$. If he is close to the lion $l_{n}$, i.e.,
the distance $\|m(t)-l_{n}(t)\|$ is close to $r$, for some small constant
$r>0$ to be specified later, then he runs counterclockwise around the lion,
maintaining approximately distance $r$ to the lion. He does so until he gets
to a point where running directly toward $g(t)$ will not decrease his distance
to the lion. He then escapes from the lion $l_{n}$, running directly toward
$g(t)$. Doing so, he can be sure that the lion cannot disturb him anymore
until he reaches $g(t)$ or $g(t)$ has changed.

In order to bound the deviation between $m(t)$ and $M_{n-1}$, and thus
obtaining property 2, we choose $r$ so small that when the man is running
around the lion $l_{n}$, we are in one of the following cases:

  * •

The lion is so close to $g(t)$ that the man is also within distance
$\delta_{n}/2$ from $g(t)$.

  * •

After running around the lion in a period of time no longer than $6\pi
r/\varepsilon_{n}$, the man escapes by running directly toward $g(t)$ without
decreasing the distance to the lion. By choosing $r$ sufficiently small, we
can therefore limit the duration, and hence the length, of the detour that the
lion can force the man to run, so that the man is ensured to be within
distance $\delta_{n}$ from the point $M_{n-1}(t)$ at any time $t$.

We now describe the details that make this idea work. We define

$r:=\min\left\\{\frac{\sigma_{n-1}/p\cdot\varepsilon_{n}(\varepsilon_{n}-\varepsilon_{n-1})}{2+2\varepsilon_{n}+18\pi(1+\varepsilon_{n})},\frac{\delta_{n}/2\cdot\varepsilon_{n}}{2+2\varepsilon_{n}+12\pi(1+\varepsilon_{n})},\|m_{0}-l_{n}(0)\|\right\\},$
$\rho:=2r/\varepsilon_{n},$ $\theta:=\arccos\frac{1}{1+\varepsilon_{n}},$
$\varphi\in(0,\pi/2]\quad\text{so
that}\quad\tan\theta=\frac{\rho\sin\varphi}{\rho\cos\varphi-2r},\quad\text{and}$
$\displaystyle\sigma_{n}>0\quad\text{sufficiently small that}\quad$
$\displaystyle
2\arcsin\frac{(2+\varepsilon_{n})\sigma_{n}}{2(r-\sigma_{n})}+\frac{\sigma_{n}}{\rho}\leq\varphi\quad\text{and}$
$\displaystyle\sigma_{n}<\frac{r}{3+\varepsilon_{n}}.$

We note that $\varphi$ can be chosen since the function
$x\longmapsto\frac{\rho\sin x}{\rho\cos x-2r}$ is $0$ for $x=0$ and tends to
$+\infty$ as $\rho\cos x$ decreases to $2r$. As for $\sigma_{n}$, the function
$x\longmapsto 2\arcsin\frac{(1+\varepsilon_{n})x}{2(r-x)}+\frac{x}{\rho}$ is
$0$ for $x=0$ and increases continuously, and hence $\sigma_{n}$ can be
chosen.

figureA free move. The circles with centers $m(t_{i})$ and $l_{n}(t_{i})$ have
radii $(1+\varepsilon_{n})\sigma_{n}$ and $r$, respectively.

figureAn escape move. The man runs to $b$.

figureAn avoidance move. The man runs to $q$.

Define a point in time $t$ to be a _time of choice_ if $t$ has the form
$t_{i}:=i\sigma_{n}$ for $i\in\mathbb{N}_{0}$. At any time of choice $t_{i}$,
the man chooses the point $m(t_{i+1})$ at distance
$(1+\varepsilon_{n})\sigma_{n}$ from his current position $m(t_{i})$, as given
by the following strategy:

  1. A

Suppose first that $\|m(t_{i})-l_{n}(t_{i})\|\geq
r+\sigma_{n}(1+\varepsilon_{n})$. Then the man chooses the direction directly
toward $g(t_{i})$. In the exceptional case that $m(t_{i})=g(t_{i})$, i.e., if
the man is standing at the goal he is pursuing, he chooses an arbitrary
direction.222It might seem counterintuitive to run away from $g(t_{i})$ in
this case instead of, say, stay in place until $t_{i+1}$. However, it makes
the subsequent analysis simpler that the man is always moving at full speed
$1+\varepsilon_{n}$. See Figure 3.

  2. B

Suppose now that $\|m(t_{i})-l_{n}(t_{i})\|<r+\sigma_{n}(1+\varepsilon_{n})$
and $m(t_{i})\neq g(t_{i})$. Let $b$ be the point at distance
$(1+\varepsilon_{n})\sigma_{n}$ from $m(t_{i})$ in the direction toward
$g(t_{i})$. If there exist two parallel lines $W_{0}$ and $W_{1}$ such that
$m(t_{i})\in W_{0}$, $b\in W_{1}$,
$\operatorname{dist}(l_{n}(t_{i}),W_{0})\geq r-\sigma_{n}$, and
$\operatorname{dist}(l_{n}(t_{i}),W_{1})\geq\operatorname{dist}(l_{n}(t_{i}),W_{0})+\sigma_{n}$,
then the man runs to $b$. The man will increase his distance from the lion in
a step of this type. See Figure 3.

  3. C

In the remaining cases, the circles
$C(m(t_{i}),\sigma_{n}(1+\varepsilon_{n}))$ and $C(l_{n}(t_{i}),r)$ intersect
at two points $p$ and $q$ such that the arc on $C(l_{n}(t_{i}),r)$ from $p$
counterclockwise to $q$ is in the interior of
$C(m(t_{i}),\sigma_{n}(1+\varepsilon_{n}))$. The man then runs toward the
point $q$. See Figure 3.

A move defined by case A, B, or C is called a _free move_ , an _escape move_ ,
or an _avoidance move_ , respectively. Let _move $i$_ be the move that the man
makes during the interval $[t_{i},t_{i+1})$.

######  Claim 3.

At any time of choice $t_{i}$, we have that $\|m(t_{i})-l_{n}(t_{i})\|\geq
r-\sigma_{n}$ and if the preceding move was an avoidance move, we also have
that $\|m(t_{i})-l_{n}(t_{i})\|\leq r+\sigma_{n}.$ Furthermore, at an
arbitrary point in time $t\in[t_{i-1},t_{i}]$ and any point $m^{\prime}\in
m([t_{i-1},t_{i}])$ we have that
$0<r-(3+\varepsilon_{n})\sigma_{n}\leq\|m^{\prime}-l_{n}(t)\|$ and if move
$i-1$ was an avoidance move then additionally $\|m^{\prime}-l_{n}(t)\|\leq
r+(3+\varepsilon_{n})\sigma_{n}.$

###### Proof.

We prove the claim by induction on $i$. It clearly holds for $i=0$ so assume
that the claim holds for $i-1$. If move $i-1$ was a free move, then we have

$\displaystyle\|m(t_{i})-l_{n}(t_{i})\|$
$\displaystyle\geq\|m(t_{i-1})-l_{n}(t_{i-1})\|-(2+\varepsilon_{n})\sigma_{n}$
$\displaystyle\geq
r+\sigma_{n}(1+\varepsilon_{n})-(2+\varepsilon_{n})\sigma_{n}=r-\sigma_{n}.$

If move $i-1$ was an escape move, then let $W_{0}$ and $W_{1}$ be lines
containing $m(t_{i-1})$ and $m(t_{i})$, respectively, as defined in B. Let
$b^{\prime}$ be the intersection of $W_{0}$ and the segment
$l_{n}(t_{i-1})m(t_{i})$. We then have

$\displaystyle\|m(t_{i})-l_{n}(t_{i-1})\|$
$\displaystyle=\|m(t_{i})-b^{\prime}\|+\|b^{\prime}-l_{n}(t_{i-1})\|$
$\displaystyle\geq\operatorname{dist}(W_{0},W_{1})+\operatorname{dist}(l_{n}(t_{i-1}),W_{0})$
$\displaystyle\geq\sigma_{n}+(r-\sigma_{n})=r.$

Hence

$\|m(t_{i})-l_{n}(t_{i})\|\geq\|m(t_{i})-l_{n}(t_{i-1})\|-\sigma_{n}\\\ \geq
r-\sigma_{n}.$

If move $i-1$ was an avoidance move, we have

$\|m(t_{i})-l_{n}(t_{i})\|\geq\|m(t_{i})-l_{n}(t_{i-1})\|-\sigma_{n}=r-\sigma_{n}$

and, similarly,

$\|m(t_{i})-l_{n}(t_{i})\|\leq\|m(t_{i})-l_{n}(t_{i-1})\|+\sigma_{n}=r+\sigma_{n}.$

Since at a point of choice $t_{i-1}$ we have
$r-\sigma_{n}\leq\|m(t_{i-1})-l_{n}(t_{i-1})\|$ and the lion and the man can
move at most $(2+\varepsilon_{n})\sigma_{n}$ closer to each other within
$\sigma_{n}$ time, we have for any point in time $t\in[t_{i-1},t_{i}]$ and any
point $m^{\prime}\in m([t_{i-1},t_{i}])$ that

$\displaystyle
r-(3+\varepsilon_{n})\sigma_{n}\leq\|m(t_{i-1})-l_{n}(t_{i-1})\|-(2+\varepsilon_{n})\sigma_{n}\leq\|m^{\prime}-l_{n}(t)\|.$

If move $i-1$ was an avoidance move, we have
$\|m(t_{i-1})-l_{n}(t_{i-1})\|\leq r+\sigma_{n}$, and hence for any point in
time $t\in[t_{i-1},t_{i}]$ and any point $m^{\prime}\in m([t_{i-1},t_{i}])$
that

$\displaystyle\|m^{\prime}-l_{n}(t)\|\leq\|m(t_{i-1})-l_{n}(t_{i-1})\|+(2+\varepsilon_{n})\sigma_{n}\leq
r+(3+\varepsilon_{n})\sigma_{n}.$

∎

One might fear that the lion $l_{n}$ could repeatedly disturb the man and
force him to make avoidance moves so that he would never approach $g(t)$.
Luckily, the following claim states that if he is able to make an escape move,
he will not be distrubed again until he reaches $g(t)$ or $g(t)$ changes.

######  Claim 4.

An avoidance move is succeeded by an avoidance move or an escape move. When
the man makes an escape move, he will not make an avoidance move before he
reaches $g(t)$ or $g(t)$ changes.

###### Proof.

Consider move $i$. We know from Claim 3 that if move $i-1$ was an avoidance
move, then $\|m(t_{i})-l_{n}(t_{i})\|\leq
r+\sigma_{n}<r+(1+\varepsilon_{n})\sigma_{n}$, so move $i$ cannot be a free
move.

Figure 1: The distance between two consecutive of the parallel lines
$W_{0},\ldots,W_{4}$ is at least $\sigma_{n}$, which proves that the man runs
from $m(t_{i})=w_{0}$ to $w_{4}$ unless $g$ moves in the meantime.

For the second part of the statement, assume that move $i$ is an escape move.
Let $g:=g(t_{i})$. Let $w_{0},\ldots,w_{k}$ be a sequence of points on the ray
from $m(t_{i})$ with direction to $g$ such that $w_{0}=m(t_{i})$,
$\|w_{0}-w_{j}\|=j(1+\varepsilon_{n})\sigma_{n}$, and $k$ is minimum such that
either $g\in w_{k-1}w_{k}$ or $g(t^{\prime})\neq g$ for some
$t^{\prime}\in[t_{i+k-1},t_{i+k}]$. See Figure 1. Let $W_{0}$ and $W_{1}$ be
the parallel lines defined in case B for move $i$. We define lines $W_{j}$ for
$j\geq 2$ to be parallel to $W_{0}$ and passing through $w_{j}$. We claim that
for any $j\in\\{0,\ldots,k-1\\}$, the man moves from $w_{j}$ to $w_{j+1}$
during move $i+j$ by making either an escape move or a free move. We prove
this by induction on $j$. The claim holds for $j=0$ by assumption, so assume
we have that $m(t_{i+j})=w_{j}$ and that move $i+j-1$ was an escape move or a
free move. Since the distance between consecutive lines $W_{j}$ and $W_{j+1}$
is at least $\sigma_{n}$, it follows that
$\operatorname{dist}(l_{n}(t_{i}),W_{j})\geq r+(j-1)\sigma_{n}$ and hence that
$\operatorname{dist}(l_{n}(t_{i+j}),W_{j})\geq r-\sigma_{n}$. Now, if
$\|m(t_{i+j})-l_{n}(t_{i+j})\|<r+\sigma_{n}(1+\varepsilon_{n})$, then the
lines $W_{j}$ and $W_{j+1}$ are a witness that move $i+j$ is an escape move so
that the man moves to $w_{j+1}$. Otherwise, move $i+j$ is a free move, in
which case the man likewise moves to $w_{j+1}$. Finally, since $g(t)$ changes
or the man reaches $g$ during move $i+k$, the statement holds. ∎

Define $\rho^{\prime}:=\rho+r+(3+\varepsilon_{n})\sigma_{n}$ and $\tau:=6\pi
r/\varepsilon_{n}$. Informally, $\tau$ is the time it takes for the man to run
around the lion $l_{n}$ before he can escape toward $g(t)$. This is made
precise by the following claim.

######  Claim 5.

If move $i$ is an avoidance move, one of the following three events occurs
before $\tau$ time has passed: (i) $g(t)$ changes, (ii)
$\|m(t)-g(t)\|<\rho^{\prime}$, or (iii) the man makes an escape move.

Figure 2: The thick arcs show the angles $\eta$ and $\xi$ at two different
times $t_{i}$ and $t_{j}$, where $t_{i}<t_{j}$, when the lion $l_{n}$ and the
man $m$ are running along the dotted paths. Here, $\xi(t_{j})>2\pi$, as
indicated by the arc making more than one full revolution around
$l_{n}(t_{j})$.

###### Proof.

Let $g:=g(t_{i})$. We first present an informal description of the proof.
Since move $i$ is an avoidance move, we know from Claim 4 that the man keeps
making avoidance moves until he makes an escape move. We show that if the
first two events do not occur, he will make an escape move during the interval
$[t_{i},t_{i}+\tau]$. Let $\xi(t)$, respectively $\eta(t)$, denote the angle
of the vector $\overrightarrow{l_{n}(t)m(t)}$, respectively
$\overrightarrow{l_{n}(t)g}$. A key observation is that if the difference in
these angles is small, then the man makes an escape move since then the lion
and the goal $g$ are roughly on opposite sides of the man. Showing that this
difference eventually becomes small involves showing that $\xi$ increases by
at least $2\pi$ more than $\eta$ after $\tau$ time so that at some point in
time $t\in[t_{i},t_{i}+\tau]$, the vectors $\overrightarrow{l_{n}(t)m(t)}$ and
$\overrightarrow{l_{n}(t)g}$ have the same orientation. By Claim 3, the lion
$l_{n}$ never gets closer than $\rho$ to $g$ which implies that the change in
$\eta$ is small in any time interval $[t_{j},t_{j+1}]$. Since the man keeps a
minimum distance from the lion, it similarly follows that the change in $\xi$
is small in $[t_{j},t_{j+1}]$. Picking $j$ to be the maximum such that
$t_{j}\leq t$ gives $t-t_{j}\leq\sigma_{n}$, which implies that the difference
in the two angles is small at time $t_{j}$, at which point the man makes an
escape move. Since $t_{j}\leq t+\tau$, the claim follows.

We now proceed with the proof of the claim. Since move $i$ is an avoidance
move, we know from Claim 4 that the man keeps making avoidance moves until he
makes an escape move. Assume that neither the first nor the second event
occurs before $\tau$ time has passed. By Claim 3, we know that for any
$t\in[t_{i},t_{i}+\tau]$, we have that

$\displaystyle\|l_{n}(t)-g\|$ $\displaystyle\geq\|m(t)-g\|-\|m(t)-l_{n}(t)\|$
$\displaystyle\geq\rho^{\prime}-(r+(3+\varepsilon_{n})\sigma_{n})=\rho.$ (1)

Since the distances from $l_{n}$ to $m$ and to $g$ are positive, there exist
continuous functions
$\xi,\eta\colon[t_{i},t_{i}+\tau]\longrightarrow\mathbb{R}$ that measure the
angle from $l_{n}$ to $m$ and to $g$, respectively; see Figure 2. These are
defined so that for any time $t\in[t_{i},t_{i}+\tau]$, we have

$\displaystyle m(t)$
$\displaystyle=l_{n}(t)+\|l_{n}(t)-m(t)\|\cdot(\cos\xi(t),\sin\xi(t))\quad\text{and}$
$\displaystyle g$
$\displaystyle=l_{n}(t)+\|l_{n}(t)-g\|\cdot(\cos\eta(t),\sin\eta(t)).$

Figure 3: Situation of the proof of Claim 5.

Consider an arbitrary time of choice $t_{j}$ where
$\|m(t_{j})-l_{n}(t_{j})\|<r+\sigma_{n}(1+\varepsilon_{n})$, so that move $j$
is either an escape move or an avoidance move. Let $\theta^{\prime}$ be the
counterclockwise angle from the direction
$\overrightarrow{l_{n}(t_{j})m(t_{j})}$ to $\overrightarrow{m(t_{j})g}$. We
now prove that a sufficient condition for move $j$ to be an escape move is
that $\theta^{\prime}\leq\theta=\arccos\frac{1}{1+\varepsilon_{n}}$. See
Figure 3, and let the point $b$ and the point on the segment $m(t_{j})g$ at
distance $\sigma_{n}(1+\varepsilon_{n})$ from $m(t_{j})$ be as defined in case
B. Consider the two lines $W_{0}$ and $W_{1}$ perpendicular to
$l_{n}(t_{j})m(t_{j})$ through $m(t_{j})$ and $b$, respectively. We claim that
$W_{0}$ and $W_{1}$ are a witness that the man makes an escape move to $b$.
This follows as

$\displaystyle\operatorname{dist}(l_{n}(t_{j}),W_{0})$
$\displaystyle=\|l_{n}(t_{j})-m(t_{j})\|\geq r-\sigma_{n}\quad\text{and}$
$\displaystyle\operatorname{dist}(l_{n}(t_{j}),W_{1})$
$\displaystyle=\operatorname{dist}(l_{n}(t_{j}),W_{0})+\|m(t_{j})-b^{\prime}\|$
$\displaystyle\geq\operatorname{dist}(l_{n}(t_{j}),W_{0})+\cos\theta^{\prime}\cdot\|m(t_{j})-b\|$
$\displaystyle\geq\operatorname{dist}(l_{n}(t_{j}),W_{0})+\cos\theta\cdot(1+\varepsilon_{n})\sigma_{n}$
$\displaystyle=\operatorname{dist}(l_{n}(t_{j}),W_{0})+\sigma_{n}.$

Next, we show that if the difference in the angles from $l_{n}$ to $m$ and to
$g$, respectively, is at most $\varphi$, then $\theta^{\prime}\leq\theta$, so
the man makes an escape move by the above. To put it another way, if

$\displaystyle\lvert\eta(t_{j})-\xi(t_{j})-2z\pi\rvert\leq\varphi$ (2)

for some $z\in\mathbb{Z}$, then $\theta^{\prime}\leq\theta$. To see this,
assume without loss of generality that inequality (2) holds for $z=0$, let
$\varphi^{\prime}:=\eta(t_{j})-\xi(t_{j})$, and consider the case
$0\leq\varphi^{\prime}\leq\varphi$. The case
$0\geq\varphi^{\prime}\geq-\varphi$ is analogous. Let $g^{\prime}$ be the
projection of $g$ onto the line through $l_{n}(t_{j})$ and $m(t_{j})$. We then
have

$\displaystyle\tan\theta^{\prime}$
$\displaystyle=\frac{\|g-g^{\prime}\|}{\|m(t_{j})-g^{\prime}\|}=\frac{\|l_{n}(t_{j})-g\|\sin\varphi^{\prime}}{\|l_{n}(t_{j})-g\|\cos\varphi^{\prime}-\|l_{n}(t_{j})-m(t_{j})\|}.$

Observe that $\tan\theta^{\prime}$, and hence $\theta^{\prime}$, are maximum
when $\varphi^{\prime}$ and $\|l_{n}(t_{j})-m(t_{j})\|$ are maximum and
$\|l_{n}(t_{j})-g\|$ is minimum, i.e., when $\varphi^{\prime}=\varphi$,
$\|l_{n}(t_{j})-m(t_{j})\|=r+\sigma_{n}$, and $\|l_{n}(t_{j})-g\|=\rho$. We
therefore get

$\displaystyle\tan\theta^{\prime}$
$\displaystyle\leq\frac{\rho\sin\varphi}{\rho\cos\varphi-(r+\sigma_{n})}\leq\frac{\rho\sin\varphi}{\rho\cos\varphi-2r}=\tan\theta.$

It now follows that $\theta^{\prime}\leq\theta$, so indeed, move $j$ is an
escape move.

In the following, we prove that there is some time of choice $t^{\prime}_{j}$
in the interval $[t_{i},t_{i}+\tau]$ for which the condition (2) is satisfied,
i.e., condition (2) is true when $t^{\prime}_{j}$ is substituted for $t_{j}$.

figureThe angle $\alpha$ is $\xi(t_{j+1})-\xi(t_{j})$. When
$\|m^{\prime}(t_{j})-m^{\prime}(t_{j+1})\|=(2+\varepsilon_{n})\sigma_{n}$,
then $\alpha=2\arcsin\frac{(2+\varepsilon_{n})\sigma_{n}}{2(r-\sigma_{n})}$.

figureThe man runs the path $m(t_{j})q_{j}q_{j+1}$. The angle from
$q^{\prime}_{j+1}$ to $q_{j+1}$ on $C(l_{n}(t_{j+1}),r)$ is at least
$\varepsilon_{n}\sigma_{n}$.

First, we show that for an arbitrary time of choice $t_{j}$ we have that

$\displaystyle\xi(t_{j+1})-\xi(t_{j})\leq
2\arcsin\frac{(2+\varepsilon_{n})\sigma_{n}}{2(r-\sigma_{n})}.$ (3)

To see this, define, for $t\in[t_{j},t_{j+1}]$,

$l^{\prime}_{n}(t):=l_{n}(t_{j})\quad\text{and}\quad
m^{\prime}(t):=m(t)+(l_{n}(t)-l_{n}(t_{j})),$

i.e., we fix the lion $l^{\prime}_{n}$ at the point $l_{n}(t_{j})$ and let the
man $m^{\prime}$ run for both so that the segment
$l^{\prime}_{n}(t)m^{\prime}(t)$ is a translation of $l_{n}(t)m(t)$. It
follows that the man $m^{\prime}$ runs at speed at most $2+\varepsilon_{n}$.
He runs from one point $m^{\prime}(t_{j})$ to another $m^{\prime}(t_{j+1})$,
both of which are on or in the exterior of the circle
$C(l^{\prime}_{n}(t_{j}),r-\sigma_{n})$, and $\xi(t_{j+1})-\xi(t_{j})$
measures the difference in angles from $l^{\prime}_{n}(t_{j})$ to the two
points. The difference of the angles is therefore maximal if the man
$m^{\prime}$ runs at full speed $2+\varepsilon_{n}$ along a straight line
segment between two points on $C(l^{\prime}_{n}(t_{j}),r-\sigma_{n})$. In
other words, $\xi$ cannot increase more on $[t_{j},t_{j+1}]$ than in the case
that
$\|l^{\prime}_{n}(t_{j})-m^{\prime}(t_{j})\|=\|l^{\prime}_{n}(t_{j+1})-m^{\prime}(t_{j+1})\|=r-\sigma_{n}$
and $\|m^{\prime}(t_{j})-m^{\prime}(t_{j+1})\|=(2+\varepsilon_{n})\sigma_{n}$.
From this observation, inequality (3) follows from an elementary argument; see
Figure 3.

We now note that

$\displaystyle\eta(t_{j+1})-\eta(t_{j})\leq\frac{\sigma_{n}}{\rho}.$ (4)

To see this, note that by inequality (3), the lion $l_{n}$ is running on or in
the exterior of the circle $C(g,\rho)$ while $\eta$ measures the angle from
$l_{n}$ to $g$. The angle is increasing the most when the lion runs
counterclockwise around $C(g,\rho)$ with unit speed, in which case equality
holds in (4).

Assume now that the moves $i,i+1,\ldots,i+k$ are all avoidance moves and
$t_{i+k}\leq t_{i}+\tau$. (See Figure 3.) For $j\in\\{i,i+1,\ldots,i+k\\}$,
let $q_{j}:=m(t_{j+1})$ be the point to which the man chooses to run at time
$t_{j}$ as defined in case C. Let $\xi_{j}\in[\xi(t_{j}),\xi(t_{j})+\pi]$ be
the angle of $q_{j}$ on $C(l_{n}(t_{j}),r)$, i.e., the angle such that

$q_{j}=l_{n}(t_{j})+r\cdot(\cos\xi_{j},\sin\xi_{j}),$

as shown in Figure 4.

Figure 4: The relation between the angles $\xi(t_{j})$ and $\xi_{j}$.

Let $q^{\prime}_{j+1}:=q_{j}+(l_{n}(t_{j+1})-l_{n}(t_{j}))$ be the point on
the circle $C(l_{n}(t_{j+1}),r)$ corresponding to $q_{j}$ on
$C(l_{n}(t_{j}),r)$. Then

$\displaystyle\|m(t_{j+1})-q^{\prime}_{j+1}\|=\|q_{j}-q^{\prime}_{j+1}\|=\|l_{n}(t_{j})-l_{n}(t_{j+1})\|\leq\sigma_{n}.$

Hence,

$\displaystyle\|q_{j+1}-q^{\prime}_{j+1}\|\geq\|q_{j}-q_{j+1}\|-\|q_{j}-q^{\prime}_{j+1}\|\geq(1+\varepsilon_{n})\sigma_{n}-\sigma_{n}=\varepsilon_{n}\sigma_{n},$

and we get that

$\xi_{j+1}-\xi_{j}\geq 2\arcsin\frac{\|q_{j+1}-q^{\prime}_{j+1}\|}{2r}\geq
2\arcsin\frac{\varepsilon_{n}\sigma_{n}}{2r}>\frac{\varepsilon_{n}\sigma_{n}}{r}$

for any $j\in\\{i,\ldots,i+k-1\\}$ and hence that
$\xi_{i+k}-\xi_{i}>\frac{k\varepsilon_{n}\sigma_{n}}{r}$.

Let $T$ be the triangle formed by the points $l_{n}(t_{j})$, $m(t_{j})$, and
$q_{j}=m(t_{j+1})$ (see Figure 4), and note that $\xi_{j}-\xi(t_{j})$ is the
angle of the corner $l_{n}(t_{j})$ in $T$. The lengths
$\|l_{n}(t_{j})-q_{j}\|$ and $\|m(t_{j})-q_{j}\|$ are fixed at $r$ and
$(1+\varepsilon_{n})\sigma_{n}$, respectively, while the last length
$\|l_{n}(t_{j})-m(t_{j})\|$ is only known to be in the interval
$[r-\sigma_{n},r+\sigma_{n}]$. It follows that $\xi_{j}-\xi(t_{j})$ is maximum
when the angle at $m(t_{j})$ is a right angle, in which case

$\xi_{j}-\xi(t_{j})\leq\arcsin\frac{(1+\varepsilon_{n})\sigma_{n}}{r}<\frac{2(1+\varepsilon_{n})\sigma_{n}}{r}.$

Hence we have

$\displaystyle D$
$\displaystyle:=\left(\xi(t_{i+k})-\xi(t_{i})\right)-\left(\eta(t_{i+k})-\eta(t_{i})\right)$
$\displaystyle>\left(\xi_{i+k}-\frac{2(1+\varepsilon_{n})\sigma_{n}}{r}-\xi_{i}\right)-\frac{k\sigma_{n}}{\rho}$
$\displaystyle>\frac{k\varepsilon_{n}\sigma_{n}}{r}-\frac{2(1+\varepsilon_{n})\sigma_{n}}{r}-\frac{k\varepsilon_{n}\sigma_{n}}{2r}$
$\displaystyle>\frac{k\varepsilon_{n}\sigma_{n}}{2r}-2,$

where the last inequality follows since
$\frac{(1+\varepsilon_{n})\sigma_{n}}{r}<\frac{(3+\varepsilon_{n})\sigma_{n}}{r}<1$
by the definition of $\sigma_{n}$.

Now, if $k\geq\frac{6\pi r}{\varepsilon_{n}\sigma_{n}}$, we get
$D>3\pi-2>2\pi$. Hence, after time $\frac{6\pi
r}{\varepsilon_{n}\sigma_{n}}\cdot\sigma_{n}=\tau$, $\xi$ has increased by at
least $2\pi$ more than $\eta$. It follows that at some point in time
$t\in[t_{i},t_{i}+\tau]$ and some $z\in\mathbb{Z}$, we have

$\lvert\xi(t)-\eta(t)-2z\pi\rvert=0.$

Let $j\in\\{i,\ldots,i+k\\}$ be maximum such that $t_{j}\leq t$. We now prove
that condition (2) is satisfied for the chosen $t_{j}$. Clearly,
$t-t_{j}\leq\sigma_{n}$. It then follows from inequalities (3) and (4) that

$\displaystyle\lvert\xi(t_{j})-\eta(t_{j})-2z\pi\rvert\leq{}$
$\displaystyle\lvert\xi(t_{j})-\xi(t)\rvert+\lvert\xi(t)-\eta(t)-2z\pi\rvert$
$\displaystyle+\lvert\eta(t)+2z\pi-\eta(t_{j})-2z\pi\rvert$
$\displaystyle\leq{}$ $\displaystyle
2\arcsin\frac{(2+\varepsilon_{n})\sigma_{n}}{2(r-\sigma_{n})}+\frac{\sigma_{n}}{\rho}\leq\varphi,$

where the last inequality holds by the choice of $\varphi$. This finishes the
proof of the claim. ∎

For $i\in\mathbb{N}_{0}$, define the _canonical interval_ $I_{i}$ as
$I_{i}:=\left[i\sigma_{n-1}/p,(i+1)\sigma_{n-1}/p\right)$, i.e., $I_{i}$ is
the interval of time such that the man would run from the $i$th to the
$(i+1)$st milestone on the path defined by the strategy $M_{n-1}$. We say that
$I_{i}$ _ends_ at time $t=(i+1)\sigma_{n-1}/p$. Note that if $t\in I_{i}$,
then $g(t)=M_{n-1}((i+1)\sigma_{n-1}/p)$ and $g(t)$ changes when $I_{i}$ ends.

As a consequence of Claim 4 and Claim 5, we get the following claim,
informally stating that once the man gets close to $g(t)$ for $t\in I_{i}$,
then he will stay close to $g(t)$ until $I_{i}$ ends.

######  Claim 6.

If $\bar{t}\in I_{i}$ and $\|m(\bar{t})-g(\bar{t})\|\leq\rho^{\prime}$, then
for every $t\geq\bar{t}$, $t\in I_{i}$, we have

$\|m(t)-g(t)\|\leq\rho^{\prime}+(1+\varepsilon_{n})\tau.$

###### Proof.

Consider a maximal interval of time
$J\subset[\bar{t},(i+1)\sigma_{n-1}/p)\subset I_{i}$ such that for all $t\in
J$, we have $\|m(t)-g(t)\|>\rho^{\prime}$. We show that during $J$, the man
gets to distance at most $\rho^{\prime}+(1+\varepsilon_{n})\tau$ from $g(t)$,
and the claim thus follows. Let $J=(t^{\prime}_{0},t^{\prime}_{1})$. At time
$t^{\prime}_{0}$, the man must be making an avoidance move since his distance
to $g(t)$ is increasing beyond $\rho^{\prime}$. By Claim 5, one of the
following three event occurs before time $\tau$ has passed after
$t^{\prime}_{0}$: (i) $I_{i}$ ends, (ii) $\|m(t)-g(t)\|<\rho^{\prime}$, or
(iii) the man makes an escape move. In case (i) and (ii), it trivially follows
that the length of $J$ is at most $\tau$. Hence, the man can get to distance
at most $\rho^{\prime}+(1+\varepsilon_{n})\tau$ from $g(t)$ during $J$. In
case (iii), let the escape move be at the time of choice $t_{j}$. We then have
that in the interval $[t^{\prime}_{0},t_{j}]$, the man gets to distance at
most $\rho^{\prime}+(1+\varepsilon_{n})\tau$ from $g(t)$. By Claim 4, he then
makes escape moves or free moves until he reaches $g(t)$ or $I_{i}$ ends.
Therefore, his maximum distance to $g(t)$ during $J$ is also
$\rho^{\prime}+(1+\varepsilon_{n})\tau$ in this case. ∎

Finally, the following claim informally states that the man is always close to
where he would be according to the strategy $M_{n-1}$.

######  Claim 7.

For any $i\in\mathbb{N}_{0}$ and at any time during the canonical interval
$I_{i}$, the man is at distance at most
$\rho^{\prime}+2(1+\varepsilon_{n})\tau$ away from the segment
$M_{n-1}(I_{i})$ and when $I_{i}$ ends, the man is within distance
$\rho^{\prime}+(1+\varepsilon_{n})\tau$ from the endpoint
$M_{n-1}((i+1)\sigma_{n-1}/p)$ of the segment.

###### Proof.

We prove the claim by induction on $i$. To easily handle the base case, we
introduce an auxiliary canonical interval $I_{-1}=[-\sigma_{n-1}/p,0)$ and
assume that the lions and the man (according to both strategies $M_{n-1}$ and
$M_{n}$) are standing at their initial positions during all of $I_{-1}$. The
statement clearly holds for $i=-1$.

Assume inductively that the statement holds for $I_{i-1}$ and consider the
interval $I_{i}$. Let $g:=M_{n-1}((i+1)\sigma_{n-1}/p)$. During $I_{i}$, the
man can run the distance

$\displaystyle\sigma_{n-1}/p\cdot(1+\varepsilon_{n})={}$
$\displaystyle\sigma_{n-1}/p\cdot(1+\varepsilon_{n-1})+\sigma_{n-1}/p\cdot(\varepsilon_{n}-\varepsilon_{n-1})$
$\displaystyle\geq{}$
$\displaystyle\sigma_{n-1}/p\cdot(1+\varepsilon_{n-1})+\rho+2r+3(1+\varepsilon_{n})\tau$
$\displaystyle>{}$
$\displaystyle\sigma_{n-1}/p\cdot(1+\varepsilon_{n-1})+\rho^{\prime}+3(1+\varepsilon_{n})\tau,$

where the two inequalities follow from the definitions of $r$ and
$\sigma_{n-1}$, respectively.

By the induction hypothesis, the man is within a distance of
$\rho^{\prime}+(1+\varepsilon_{n})\tau$ from $M_{n-1}(i\sigma_{n-1}/p)$ at
time $i\sigma_{n-1}/p$. Thus, his distance to $g$ at the beginning of interval
$I_{i}$ is
$\|m(i\sigma_{n-1}/p)-g\|\leq\sigma_{n-1}/p\cdot(1+\varepsilon_{n-1})+\rho^{\prime}+(1+\varepsilon_{n})\tau$,
where $\sigma_{n-1}/p\cdot(1+\varepsilon_{n-1})$ is the length of the interval
$M_{n-1}(I_{i})$.

If the man does not make any avoidance moves during $I_{i}$, he runs straight
to $g$, so it follows that he reaches $g$ at the latest at time

$\displaystyle\frac{\|m(i\sigma_{n-1}/p)-g\|}{1+\varepsilon_{n}}={}$
$\displaystyle\sigma_{n-1}/p+\frac{\|m(i\sigma_{n-1}/p)-g\|-\sigma_{n-1}/p\cdot(1+\varepsilon_{n})}{1+\varepsilon_{n}}$
$\displaystyle<{}$
$\displaystyle\sigma_{n-1}/p+\frac{(1+\varepsilon_{n})\tau-3(1+\varepsilon_{n})\tau}{1+\varepsilon_{n}}$
$\displaystyle={}$ $\displaystyle\sigma_{n-1}/p-2\tau.$ (5)

In the remaining part of $I_{i}$ after reaching $g$, he will be within
distance $\sigma_{n}(1+\varepsilon_{n})$ from $g$ (possibly doing a sequence
of free moves in each of which he passes over $g$), so the statement is true
in this case.

Figure 5: Situation of the proof of Claim 7. The dark gray disks are the
points at distance at most $\rho^{\prime}+(1+\varepsilon_{n})\tau$ from
$M_{n-1}(i\sigma_{n-1}/p)$ and $g$. The light gray hippodrome consists of the
points at distance at most $\rho^{\prime}+2(1+\varepsilon_{n})\tau$ from the
segment $M_{n-1}(I_{i})$.

Otherwise, let $t\in I_{i}$ be the first time of choice at which he makes an
avoidance move during $I_{i}$; see Figure 5. If
$t\geq(i+1)\sigma_{n-1}/p-2\tau$, then he already reached $g$ before time $t$,
and the statement follows from Claim 6, so assume that
$t<(i+1)\sigma_{n-1}/p-2\tau$. Hence, Claim 5 gives that at some time
$t^{\prime}\leq t+\tau$, either

  1. 1.

the man gets within a distance of $\rho^{\prime}$ from $g$, or

  2. 2.

he does an escape move.

We first prove that in the interval $[t,t^{\prime}]$, the distance from the
man to the segment $M_{n-1}(I_{i})$ is at most
$\rho^{\prime}+2(1+\varepsilon_{n})\tau$. To this end, note that during the
preceding interval $[i\sigma_{n-1}/p,t)$ of $I_{i}$, he makes no avoidance
moves and thus only gets closer to the segment. His initial distance is
$\rho^{\prime}+(1+\varepsilon_{n})\tau$ by the induction hypothesis, so that
is also a bound on his distance up to time $t$. Thus, since $t^{\prime}\leq
t+\tau$, his distance at time $t^{\prime}$ can be at most
$\rho^{\prime}+2(1+\varepsilon_{n})\tau$.

It remains to be proved that the man stays within distance
$\rho^{\prime}+2(1+\varepsilon_{n})\tau$ from $M_{n-1}(I_{i})$ after time
$t^{\prime}$ and that he is at distance at most
$\rho^{\prime}+(1+\varepsilon_{n})\tau$ from $g$ at time
$(i+1)\sigma_{n-1}/p$. If we are in case 1, the statement follows from Claim
6, so assume case 2.

By Claim 4, the man will run directly toward $g$ after time $t^{\prime}$ until
(i) he reaches $g$ or (ii) $I_{i}$ ends. We now claim that we will always be
in case (i), i.e., he always reaches $g$ before $I_{i}$ ends. The length of
the path he has to run in order to reach $g$ is at most

$L:=\|m(i\sigma_{i-1})-m(t)\|+\tau(1+\varepsilon_{n})+\|m(t^{\prime})-g\|,$

where $\tau(1+\varepsilon_{n})$ is a bound on the length of the path he runs
during $[t,t^{\prime})$ while making avoidance moves. The triangle inequality
gives

$\|m(t^{\prime})-g\|\leq\|m(t^{\prime})-m(t)\|+\|m(t)-g\|\leq\tau(1+\varepsilon_{n})+\|m(t)-g\|.$

We therefore get

$L\leq\|m(i\sigma_{i-1})-g\|+2\tau(1+\varepsilon_{n}).$

We now get from inequality (3) that the time it takes the man to run to $g$ is
at most

$\frac{L}{1+\varepsilon_{n}}\leq\frac{\|m(i\sigma_{i-1})-g\|}{1+\varepsilon_{n}}+2\tau=\sigma_{n-1}/p,$

so he indeed reaches $g$ before $I_{i}$ ends. Note that while he runs to $g$,
he stays within distance $\rho^{\prime}+2(1+\varepsilon_{n})\tau$ from segment
$M_{n-1}(I_{i})$. After he has reached $g$, we get by Claim 6 that he stays
within distance $\rho^{\prime}+(1+\varepsilon_{n})\tau$ from $g$ for the rest
of $I_{i}$. This finishes the proof. ∎

We are now ready to finish our proof of Lemma 2. We define the safety distance
to lion $l_{n}$ as $c_{n}:=r-(3+\varepsilon_{n})\sigma_{n}$. By Claim 3, we
know that the safety distance is maintained.

We now give a bound on the distance $\|M_{n-1}(t)-M_{n}(t)\|$ at any time $t$.
Suppose that $t\in I_{i}$. Claim 7 says that during interval $I_{i}$, the
distance from the man to the segment $M_{n-1}(I_{i})$ is at most

$\displaystyle\rho^{\prime}+2(1+\varepsilon_{n})\tau<\rho+2r+2(1+\varepsilon_{n})\tau\leq\delta_{n}/2,$
(6)

where the first inequality follows from the choices of $\rho^{\prime}$ and
$\sigma_{n}$ and the second from the definition of $r$. Since $M_{n-1}(t)$ is
a point on the segment $M_{n-1}(I_{i})$ of length
$\sigma_{n-1}/p\cdot(1+\varepsilon_{n-1})\leq\delta_{n}/2$, the bound (6)
implies that

$\displaystyle\|M_{n-1}(t)-M_{n}(t)\|\leq\delta_{n}/2+\delta_{n}/2=\delta_{n}.$
(7)

This proves the lemma.

∎

##  4 Concluding Remarks

We have shown that a fast man can survive any finite number of lions, and that
the lions do not also have a winning strategy since the man’s strategy is
locally finite. Furthermore, the man has a winning strategy $M_{\infty}$
against any countably infinite set of lions. However, this strategy is in
general not locally finite. Indeed, if it was, there would be $\delta>0$ such
that the man’s path according to $M_{\infty}$ up to time $\delta$ was already
determined at time $0$. If the lions’ start points were dense in the plane, a
lion sufficiently close to the point $M_{\infty}(\delta)$ could catch the man
at time $\delta$ by running to that point, and hence $M_{\infty}$ would not be
winning. Therefore, $M_{\infty}$ cannot be locally finite, so the lions might
also have a winning strategy, but we have not been able to find one.

We finally note that for the man to have a winning strategy, it is necessary
that there are only _countably_ many lions. Indeed, the man cannot win if
there is a lion at every point of the plane except for his starting point.

## Acknowledgments

We thank the reviewers of the published paper [2] for their comments and
suggestions that improved the paper a lot. We thank Mehdi Salimi for making us
aware of the papers [6, 11].

## References

  * [1] Abrahamsen, M., Holm, J., Rotenberg, E., Wulff-Nilsen, C. (2017).  Best Laid Plans of Lions and Men.  33rd Int. Symp. Comp. Geom. (SoCG 2017) 6:1–6:16.  doi.org/10.4230/LIPIcs.SoCG.2017.6
  * [2] Abrahamsen, M., Holm, J., Rotenberg, E., Wulff-Nilsen, C. (2020).  Escaping an Infinitude of Lions.  Am. Math. Mon. 127(10): 880–896.  doi.org/10.1080/00029890.2020.1820837
  * [3] Alon, N., Mehrabian, A. (2015).  Chasing a fast robber on planar graphs and random graphs.  J. Graph Theory. 78(2): 81–96.  doi.org/10.1002/jgt.21791
  * [4] Bakolas, E. (2017).  On the finite-time capture of a fast moving target.  Optim. Contr. Appl. Met. 38(5): 778–794.  doi.org/10.1002/oca.2289
  * [5] Bollobás, B., Leader, I., Walters, M. (2012).  Lion and man—can both win?  Isr. J. Math. 189(1): 267–286.  doi.org/10.1007/s11856-011-0158-6 Version with appendix: arxiv.org/abs/0909.2524
  * [6] Chernous’ko, F. L. (1976).  A problem of evasion from many pursuers.  J. Appl. Math. Mech. 40(1): 11–20.  doi.org/10.1016/0021-8928(76)90105-2
  * [7] Croft, H. T. (1964).  “Lion and man”: A postscript.  J. London Math. Soc. 39(1): 385–390.  doi.org/10.1112/jlms/s1-39.1.385
  * [8] Flynn, J. (1973).  Lion and man: The boundary constraint.  SIAM J. Contr. 11: 397–411.  doi.org/10.1137/0311032
  * [9] Flynn, J. (1974).  Lion and man: The general case.  SIAM J. Contr. 12: 581–597.  doi.org/10.1137/0312043
  * [10] Fomin, F. V., Golovach, P A., Kratochvíl, J., Nisse, N., Suchan, K. (2010).  Pursuing a fast robber on a graph.  Theor. Comput. Sci. 411: 1167–1181.  doi.org/10.1016/j.tcs.2009.12.010
  * [11] Ibragimov, G. I., Salimi, M., Amini, M. (2012).  Evasion from many pursuers in simple motion differential game with integral constraints.  Eur. J. Oper. Res. 218(2): 505–511.  doi.org/10.1016/j.ejor.2011.11.026
  * [12] Janković, V. (1978).  About a man and lions.  Matematički Vesnik. Vol. 2(15)(30), Issue 64: 359–361.  digizeitschriften.de/download/PPN311571026_0030/PPN311571026_0030___log73.pdf
  * [13] Lewin, J. (1986).  The lion and man problem revisited.  J. Optimiz. Theory App. 49(3): 411–430.  doi.org/10.1007/BF00941070
  * [14] Littlewood, J. E. (1986).  Littlewood’s Miscellany. Bollobás, B., ed.  Cambridge Univ. Press.
  * [15] Rado, P. A., Rado, R. (1974/75).  More about lions and other animals.  Math. Sprectrum. 7(3): 89–93.
  * [16] Ramana, M. V., Kothari, M. (2017).  Pursuit-evasion games of high speed evader.  J. Intell. Robotic Syst. 85(2): 293–306.  doi.org/10.1007/s10846-016-0379-3