The Lonely Runner Conjecture
Suppose that six runners are running around and around a circular track, each running at a different constant speed, but in the same direction. Will each runner eventually be in a situation where each of the other five runners is at least 1/6 of a lap away? According to the Lonely Runner Conjecture
, the answer is yes
This animation from Wikipedia by Claudio Rocchini
illustrates the situation for six runners. The runners are initially represented by black dots, which turn to yellow as soon as the corresponding runner has 1/6 of a lap of empty track both ahead of and behind them. Eventually, all the runners have had the experience of being in this state.
In general if the number of runners on the circular track is k, a runner is said to be lonely
if each of the other runners is at least 1/k of a lap away. The conjecture is that if k is at least 2 and each runner runs at a different speed, then each runner will be “lonely” at some point.
The conjecture was originally made by J.M. Wills
in 1967. Although it is easy to state, the conjecture is even now only known to be true in general for small values of k. The case k=2 is trivial, the case k=3 is not too hard, and the case k=4 was proved in 1972. A proof of the case k=5 involving a computer check was found in 1984, and a more elegant proof was found in 1998. The case k=6 was proved in 2001, with a shorter proof being found in 2004. The case k=7 was proved by Barajas and Serra in 2008, but the problem is still open if k is 8 or more.
The Lonely Runner Conjecture has points of contact with other areas of mathematics. As Barajas and Serra explain in the introduction to their paper (http://arxiv.org/abs/0710.4495
), the positive solution of the conjecture would prove a theorem about nowhere zero flows in regular matroids. The known results about the conjecture have also been used to compute chromatic numbers of distance graphs.
If all the runners' speeds are irrational multiples of each other, the problem becomes easy and the conjecture is known to be true. For this reason, attacks on the problem focus on the most difficult case, where all the speeds are rational multiples of each other. This case quickly reduces to the case where all the runners' speeds are integers with no common factor greater than one. We may also assume that one of the speeds is zero, meaning that one of the “runners” is stationary.
In the case of six runners, the stationary runner will be lonely when the other five runners are bunched in the 4/6 of the track centred at the point diametrically opposite the stationary runner. This point of view can be used to recast the conjecture in terms of a line of sight problem in Euclidean space. My previous post on this topic goes into more detail about this aspect of the problem (https://plus.google.com/101584889282878921052/posts/JMtPiZeVVnT
) and provides a link to another relevant paper.
Picture source: http://en.wikipedia.org/wiki/Lonely_runner_conjecture#mathematics #scienceeveryday #spnetwork