15
$\begingroup$

I've recently read here the following problem, called « four-runner problem » :

Suppose four runners (represented by labeled spheres) run around a circular track. Their speeds are constant positive rationals $v_1<v_2<v_3<v_4$.

At time $0$, all the runners are together at the starting gate; shortly after, they are arranged in the order $\{1, 2, 3, 4\}$, counting from the starting gate. The order changes to $\{4, 1, 2, 3\}$ when runner 4 passes the starting gate. Then either runner 3 passes the starting gate, runner 4 laps runner 1, or the two events happen at the same time, giving possible orders $\{3, 4, 1, 2\}$, $\{1, 4, 2, 3\}$, or $\{3, 1, 2, 4\}$. […]

The answer to this question is unknown: which rates generate all 24 possible orders?

For three runners, all six orders are achieved if and only if the two slower rates do not add up to the fast rate.

For instance, I found that the rates $0.1 < 0.2 < 0.61 < 0.9$ generate the 24 possible combinations.

I would like to know where to find more information on that problem. Are there some research articles about it? I didn't find anything, even for the case with 3 runners (which does not seem obvious to me).

Thank you in advance!

$\endgroup$
9
  • $\begingroup$ What is the length of the track? $\endgroup$ Commented Dec 29, 2015 at 15:47
  • $\begingroup$ I think this is 1. In some sense, we are considering the maps $t \mapsto t \cdot v_j \pmod 1$ for $1 \leq j \leq 4$. $\endgroup$
    – Watson
    Commented Dec 29, 2015 at 17:29
  • $\begingroup$ Presumably, then, the speeds are not integers but positive rationals? Or reals? $\endgroup$ Commented Dec 31, 2015 at 14:43
  • $\begingroup$ @Justpassingby : I noticed that. The speeds are positive rationals, say. $\endgroup$
    – Watson
    Commented Dec 31, 2015 at 15:20
  • 2
    $\begingroup$ The lonely runner conjecture is similar - it says that each runner in such a scenario will be a "far" from the others at some time. It is unproven for $8$ or more runners. $\endgroup$ Commented Jan 3, 2016 at 16:59

1 Answer 1

10
+100
$\begingroup$

(This is really a long comment, not an answer intended to attract up- or downvotes, acceptance or bonus - it's just not comfortable typing it in the SE comments format)

The problem becomes more symmetric if we award the starting point a velocity $v_0.$ The order of the runners changes whenever the time $t$ is an integer multiple of the reciprocal of $v_i-v_j$ for some $i>j\geq0.$ In fact we could even eliminate the condition $v_0<v_1<\cdots<v_n$ and and ask under which conditions on the $v_k$ the runners are guaranteed to reach at least once the order defined by the numbers on their back; the condition $v_i\neq v_j$ for $i\neq j$ then becomes part of the answer rather than part of the problem statement, and we could rephrase:

Which half-lines starting from the origin in $\mathbb R^n$ intersect the $n$-fold periodic set defined by translating the interior of the unit simplex $0<x_1<\ldots<x_n<1$ along the unit cubic $n$-dimensional lattice?

There are $C^n_2$ interesting quantities to compare:

$$\begin{matrix} v_1(-v_0)&v_2(-v_0)&\cdots&v_{n-1}(-v_0)&v_n(-v_0)\\ &v_2-v_1&\cdots&v_{n-1}-v_1&v_n-v_1\\ &&\ddots&&\vdots\\ &&&v_{n-1}-v_{n-2}&v_{n}-v_{n-2}\\ &&&&v_{n}-v_{n-1}\\ \end{matrix}$$

Any equality between two of these quantities - in fact, any equality between integer multiples of the reciprocals of two of these quantities - could theoretically cause the runners to complete a full race without ever reaching a particular given order, although many of these equalities are excluded if we assume $v_0<v_1<v_2<\cdots<v_n.$ It is therefore curious that for $n=3$ only one equality, namely, $v_3-v_2=v_1-v_0$ (or, equivalently, $v_3-v_1=v_2-v_0$) effectively prevents some permutations to be reached - it is no problem if, say, $v_2-v_1=v_3-v_2$ which means that the three runners overtake each other always at exactly the same moment.

In 4 dimensions we have, as a necessary condition, that every subset consisting of 3 runners (or 4, counting the starting point as a runner) has to satisfy the 3-dimensional condition, so we know that

$$\eqalign{ v_1+v_2&\neq v_3(+v_0)\\ v_1+v_2&\neq v_4(+v_0)\\ v_1+v_3&\neq v_4(+v_0)\\ v_2+v_3&\neq v_4(+v_0)\\ v_1+v_4&\neq v_2+v_3\\ }$$

One attempt to answer the question could be to try and prove that these five conditions together are also sufficient.

Putting $v_0=0$ again and $v_4=1$ (because the problem is homogeneous in the $v_i$) these five conditions divide the 3-dimensional unit simplex $0\leq v_1\leq v_2\leq v_3\leq 1$ into an number of sub-simplices (at most 32, I haven't figured out the exact number) along the following boundaries:

$$\eqalign{ v_1+v_2&= v_3\\ v_1+v_2&= 1\\ v_1+v_3&= 1\\ v_2+v_3&= 1\\ v_1+1&= v_2+v_3\\ }$$

Suggestion: identify these sub-simplices and prove for every sub-simplex separately that all 24 permutations are reached when $(v_1,v_2,v_3)$ is in the interior of the sub-simplex.

$\endgroup$
2
  • $\begingroup$ I have received 6 upvotes despite my request to the contrary - thank you for the recognition but if this results in an automatic bounty award then I will use the bounty to further promote this interesting (and unresolved) question. $\endgroup$ Commented Jan 5, 2016 at 12:57
  • $\begingroup$ As announced, my intent was to draw attention; I was not really hoping to get a complete answer (though this would be welcome, of course). And your input is very valuable, so I award the bounty without hesitation. $\endgroup$
    – zhoraster
    Commented Jan 5, 2016 at 14:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .