\section{Introduction} \label{sec:intro}

In the classic \emph{lonely runners conjecture},
introduced by Wills~\cite{Wi67} and Cusick~\cite{Cu73},
$k$ agents run clockwise along a circle of length $1$,
starting from the same point at time $t=0$.
They have distinct but constant speeds. A runner is called \emph{lonely} when he/she is
at distance of at least $\frac{1}{k}$ from any other runner (along the circle).
The conjecture asserts that each runner $a_i$ is lonely at some time
$t_i\in (0,\infty)$. The conjecture has only been confirmed for up to
$k=7$ runners~\cite{BS08,BHK01}. A recent survey~\cite{DT14} lists
a few other related problems.

Recently, some problems with similar flavor have appeared in the context of
\emph{multi-agent patrolling}, particularly in some one-dimensional
scenarios~\cite{Ch04,CGKK11,DGT14,KK15,KS15}.
Suppose that $k$ mobile agents with (possibly distinct) maximum speeds
$v_i$ ($i=1,\ldots,k$) are in charge of \emph{patrolling} a closed or open
fence (modeled by a circle or a line segment). The movement of the agents
over the time interval $[0,\infty)$ is described by a \emph{patrolling schedule}
(or \emph{guarding schedule}), where the speed of the $i$th agent, ($i=1,\ldots,k$),
may vary between zero and its maximum value $v_i$ in any of the two directions
along the fence. Given a closed or open fence of length $\ell$ and maximum speeds
$v_1,\ldots,v_k>0$ of $k$ agents, the goal is to find a patrolling schedule that minimizes
the \emph{idle time}, defined as the longest time interval in $[0,\infty)$
during which some point along the fence remains unvisited, taken over all points.
Several basic problems are open, such as the following:
  It is \emph{not} known how to decide, given $v_1,\ldots,v_k>0$, and $\ell,\tau>0$
  whether $k$ agents with these maximum speeds can ensure an idle time at most $\tau$
  when patrolling a segment of length $\ell$.

This note is devoted to a question on track runners.
In the spirit of the lonely runner conjecture, we posed the following
question in~\cite{DT14}:

\begin{quote}
Assume that $k$ runners $1,2,\ldots,k$, with distinct but
constant speeds, run clockwise along a circle of length $1$, starting from
arbitrary points. Assume also that a certain half of the circular track (or
any other fixed circular arc) is in the shade at all times. Does there exist
a time when all runners are in the shade along the track?
\end{quote}

Here we answer the question in the negative: the statement does not hold
even if the shaded arc almost covers the entire track,
\eg, has length $0.999$, provided $k$ is large enough.

\paragraph{Notation and terminology.}
We parameterize a circle of length $\ell$ by the interval $[0,\ell]$, where
the endpoints of the interval $[0,\ell]$ are identified.
A \emph{unit} circle is a circle of unit length $C=[0,1] \mod 1$.
A \emph{schedule} of $k$ agents consists of $k$ functions
$f_i:[0,\infty] \rightarrow [0,\ell]$, for
$i=1,\ldots , k$, where $f_i(t) \mod \ell$ is the position of agent
$i$ at time $t$. Each function $f_i$ is continuous,
piecewise differentiable, and its derivative (speed) is bounded by $|f_i'|\leq v_i$.
A schedule is called \emph{periodic} with {period} $T>0$
if $f_i(t)=f_i(t+T) \mod \ell$ for all $i=1,\ldots , k$ and $t\geq 0$.
$H_n= \sum_{i=1}^n 1/i$ denotes the $n$th \emph{harmonic number}; and $H_0=0$. 


\section{Track runners in the shade} \label{sec:shade}

We first show that the general answer to the problem posed in~\cite{DT14} is negative:

\begin{theorem}\label{thm:no-shade}
  Consider the unit circle $C$ and a circular arc $A\subset C$ of length
  $\ell=|A| < 1$. Then there exists $k=k(\ell) \in \NN$, and a schedule for $k$
  runners with $k$ distinct constant speeds, so that at any time $t \geq 0$,
  at least one of the $k$ runners is in the complement $C\setminus A$.
\end{theorem}
\begin{proof}
Set $v_i=i$ as the speed of agent $i$, for $i=1,\ldots,k$, where $k=k(\ell)\in \mathbb{N}$
is to be specified later. Assume, as we may, that $C\setminus A=[0,a]$, for some $a \in (0,1)$.
Let $t_0=0$. Since the speed of each agent is an integer multiple of the circle length
$\len(C)=1$, the resulting schedule is periodic and the period is $1$.
To ensure that at any $t \geq 0$, at least one agent is in $[0,a]$, it suffices to ensure this
\emph{covering condition} on the time interval $[0,1]$, \ie, one period of the schedule.
All agents start at time $t=0$; however, it is convenient to specify their schedule
with their positions at later time.

    Agent $1$ starts at point $0$ at time $0$; at time $a$, its position is at $a$ (exiting $[0,a]$).
    Agent $2$ starts at point $0$ at time $a$; at time $a+a/2$, its position is at $a$  (exiting $[0,a]$).
    Agent $3$ starts at point $0$ at time $a+a/2$; at time $a+a/2+a/3$, its position is at $a$
    (exiting $[0,a]$). Subsequent agents are scheduled according to this pattern.
    For $i=1,\ldots,k$, agent $i$  starts at point $0$ at time
    $a H_{i-1}$; at time $a H_i$, its position is at $a$ (exiting $[0,a]$).
The schedules are given by the functions $f_i(t) = i t - i a H_{i-1}$ for $i=1,\ldots,k$.

    The construction ensures that
    \begin{enumerate} \itemsep 1pt
    \item agent $i$ is in $[0,a]$ during the time interval $[t_{i-1},t_i]$, for $i=1,\ldots,k$.
    \item $\bigcup_{i=1}^k [t_{i-1},t_i] \supseteq [0,1]$.
    \end{enumerate}

    Indeed, condition $2$ is $a H_k \geq 1$, or equivalently $ H_k \geq 1/a$.
    Since $\ln{k} \leq H_k$, it suffices to have $\ln{k} \geq  1/a$, or
    $k \geq \exp(1/a)$, and the theorem is proved.
\end{proof}

Now that we have seen that the general answer is negative, it is however
interesting to exhibit some scenarios when the result holds.


A set of numbers $\xi_1,\xi_2,\ldots,\xi_k$ are said to be \emph{rationally independent}
if no linear relation
$$ a_1 \xi_1 + a_2 \xi_2 + \cdots +  a_k \xi_k = 0, $$
with integer coefficients, not all of which are zero, holds.
In particular, if $\xi_1,\xi_2,\ldots,\xi_k$ are rationally independent,
then they are pairwise distinct.
Recall now Kronecker's theorem; see, \eg, \cite[Theorem 444, p.~382]{HW79}.
\begin{theorem} {\rm (Kronecker, 1884)} \label{thm:K}
If $\xi_1,\xi_2,\ldots,\xi_k\in \mathbb{R}$ are rationally independent,
$\alpha_1,\alpha_2,\ldots,\alpha_k\in \mathbb{R}$ are arbitrary,
and $T$ and $\eps$ are positive reals, then there is a real number $t>T$,
and integers $p_1,p_2,\ldots,p_k$, such that
$$ | t \xi_m -p_m - \alpha_m | \leq \eps \ \ \ (m=1,2,\ldots,k). $$
\end{theorem}

As a corollary, we obtain the following result.

\begin{theorem} \label{thm:shade1}
  Assume that $k$ runners $1,2,\ldots,k$, with constant rationally independent
  (thus distinct) speeds $\xi_1,\xi_2,\ldots,\xi_k$,
  run clockwise along a circle of length $1$, starting from
  arbitrary points. For every circular arc $A\subset C$
  and for every $T>0$, there exists $t>T$  such that
  all runners are in $A$ at time $t$.
\end{theorem}
\begin{proof}
  Assume, as we may, that $A=[0,a]$, for some $a \in (0,1)$.
  Let $0 \leq \beta_i < 1$, be the start position of runner $i$, for $i=1,2,\ldots,k$.
  Set $\alpha_i = a/2 + 1- \beta_i$, for $i=1,2,\ldots,k$,
  set $\eps=a/3$, and employ Theorem~\ref{thm:K} to finish the proof.
\end{proof}

\paragraph{Remark.}
It is interesting to note that Theorem~\ref{thm:no-shade} gives a negative answer
regardless of how long the shaded arc is, while Theorem~\ref{thm:shade1}
gives a positive answer regardless of how short the shaded arc is \emph{and} for
how far in the future one desires.

Observe that if $\xi_1,\xi_2,\ldots,\xi_k$ are rationally independent reals, 
then at least one $\xi_i$ must be irrational (in fact, all but at most one $\xi_i$ must be irrational). 
To obtain the conclusion of Theorem~\ref{thm:shade1} neither the condition that the 
speeds $\xi_1,\xi_2,\ldots,\xi_k$ are rationally independent, nor the condition that at least one
$\xi_i$ is irrational are necessary.
For instance, a condition imposed on the relative speeds suffices as it is shown in the following.

\begin{theorem} \label{thm:shade2}
  Assume that $k$ runners $1,2,\ldots,k$, with constant but distinct speeds
  run clockwise along a circle of length $1$, starting from arbitrary points.
  For every circular arc $A\subset C$, there exist suitable distinct speeds 
  $v_1,v_2,\ldots,v_k>0$, so that for every $T>0$, there exists $t>T$ such that
  all runners are in $A$ at time $t$.
\end{theorem}
\begin{proof}
  Assume, as we may, that $A=[0,a]$, for some $a \in (0,1)$.
  Let $\beta_1,\beta_2,\ldots,\beta_k$ be the starting points of the runners,
  where $0 \leq \beta_i < 1$, for $i=1,2,\ldots,k$.
  We proceed by induction on the number of runners $k$, and
  with a stronger induction hypothesis extending to every arc $A$.
  The base case $k=1$ is satisfied by setting $v_1=1$ for any interval.
  The subsequent speeds will be set to increasing values, so that
  $v_1 < v_2 < \cdots <v_k$.

 For the induction step, assume that the statement holds for runners $1,2,\ldots,k-1$,
 the arc $A'=[0,a/2]$ and $T$, and we need to prove it for runners $1,2,\ldots,k$,
 the arc $A=[0,a]$ and $T$.
 By the induction hypothesis, there exists $t>T$ so that
 runners $1,2,\ldots,k-1$, are in $A'$ at time $t$.
 Set $v_k =\frac{2}{a} v_{k-1}$.
 Observe that runner $k$ will enter the arc $A$ at point $0$ before any of the first $k-1$ 
 runners exits $A$ at point $a$, regardless of his or her starting point.
 Hence all $k$ runners will be in $A$ at some time in the 
 interval $[t,t+1/v_k]$, completing the induction step, and thereby the proof of the theorem.
\end{proof}


