Lonely runner conjecture
From Wikipedia, the free encyclopedia
In number theory, and especially the study of diophantine approximation, the lonely runner conjecture is a conjecture originally due to J. M. Wills in 1967. Applications of the conjecture are widespread in mathematics; they include view obstruction problems[1] and calculating the chromatic number of distance graphs and circulant graphs[2]. The conjecture was given its picturesque name by L. Goddyn in 1998[3].
Contents |
[edit] The conjecture
Consider k + 1 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 if she is at distance of at least 1/(k + 1) from each other runner. The lonely runner conjecture states that every runner gets lonely at some time.
A convenient reformulation of the problem is to assume that the runners have integer speeds, not all divisible by the same prime; the runner to be lonely has zero speed. The conjecture then states that for any set D of k positive integers with gcd 1, there exists a real t such that
where ||x|| denotes the distance of real number x to the nearest integer.
[edit] Known results
| k | year proved |
|---|---|
| 3 | 1972 |
| 4 | 1984 |
| 5 | 2001 |
| 6 | 2008 |
| 7 | 2008 |
[edit] Notes
- ^ T. W. Cusick (1973). "View-Obstruction problems". Aequationes Math. 9: 165-170.
- ^ J. Barajas and O. Serra (2008). "The lonely runner with seven runners". The Electronic Journal of Combinatorics 15: R48.
- ^ W. Bienia and others (1998). "Flows, view obstructions, and the lonely runner problem". Journal of combinatorial theory series B 72: 1-9.
