A question about lonely runner conjecture

1.2k Views Asked by At

After wikipedia:

"Consider $k$ runners on a circular track of unit length. At $t = 0$, all runners are at the same position and start to run; the runners' speeds are pairwise distinct. A runner is said to be lonely at time $t$ if he is at a distance of at least $1/k$ from every other runner at time $t$. The lonely runner conjecture states that each runner is lonely at some time."

I gave some thoughts to it by myself. Could you please tell me if my thinking, presented below, is correct?

Let's simplify the problem making following assumption:

$m_{i}$ - number of full circles which runner $i$ runs within some period of time (let's call it $\delta_{t}$), $m_{i}$ is a natural number such that $\gcd(\{m_i\})=1$, $i = 1,..,k$.

After time: $T_{j} = \mathrm{lcm}({m_i, i=1,..,k\text{ and }i \neq j})$ all of the runners, apart from the runner $j$, cross starting point. Runner $j$ is apart from the rest (i.e. from the starting point) by some distance $d_{j}$.

It is ease to notice that $\forall j \quad \exists n \in N$: after time $nT_{j}$ we get: $d_{j} > 1/k$.

Is my thinking correct? That would be a very short proof (assuming of course boundaries put on $m_{i}$).

1

There are 1 best solutions below

12
On

As far as I can see, your proof is entirely correct; however, it is not a proof of the full lonely runner conjecture, but rather a proof of a particular easy special case.

In the original statement of the problems, the speeds of the runners are allowed to be arbitrary real numbers. It is a theorem that it is in fact enough to take the speeds of the runners to be rational.

What you have proved is that the conjecture is true if the speeds of the runners are taken to be $1/m_i$, where $m_1,\dots,m_k$ are pairwise coprime integers. This is not enough to prove the full conjecture.


As an example of why your approach can't prove the full conjecture, let $v_i=i$ for $i=0,\dots,k$. Suppose the runners have been running for time $\alpha$. Then, by the Dirichlet approximation theorem, there exist integers $p,q$ with $1\le q\le k$ such that $$ |q\alpha - p|<\frac1k $$ $q\alpha$ measures the distance along the track that runner $q$ has run. Subtracting $p$ means subtracting off a whole number multiple of full laps, so $|q\alpha-p|$ can measure the distance between runner $q$ and runner $0$ (who is stuck at point $0$ forever). So in this case there is always some runner within $1/k$ of runner $0$ (where there are $k+1$ runners).

In your case, however, no such bound holds. Indeed, you have situations where all but one of the runners are clustered together at the same point but one of them is far away from the others. So you are considering a special case that can't hope to prove other cases like the one outlined above.