Conjecture du coureur solitaire
En mathématiques, et plus particulièrement dans l'étude de l'approximation diophantienne, la conjecture du coureur solitaire est une conjecture formulée par John M. Wills en 1967. Les applications de cette conjecture balayent de nombreux domaines des mathématiques : problèmes d'obstruction de vue[1], calculs de nombres chromatiques[2], etc. Le nom pittoresque de cette conjecture a été proposée par Luis Goddyn en 1998[3].
La conjecture modifier
Considérons k coureurs sur une piste circulaire de longueur 1. Au temps t = 0, tous les coureurs sont à la même position et commencent à courir à des vitesses deux à deux distinctes. Un coureur est dit solitaire au temps t s'il est à une distance d'au moins 1/k de tous les autres coureurs. La conjecture du coureur solitaire affirme que chaque coureur sera solitaire à certains moments.
Propriétés modifier
A priori, les vitesses sont des réels, mais on peut se restreindre sans perte de généralité à des rationnels ou des entiers[4],[5].
Résultats démontrés modifier
| k | année | démontrés par | notes |
|---|---|---|---|
| 1 | - | - | trivial: tout t convient |
| 2 | - | - | trivial: t = 1 / (2 * (v1-v0)) |
| 3 | - | - | Toute preuve pour k>3 prouve également le cas k=3 |
| 4 | 1972 | Betke et Wills[6]; Cusick[7] | - |
| 5 | 1984 | Cusick et Pomerance[8]; Bienia et al.[3] | - |
| 6 | 2001 | Bohman, Holzman, Kleitman[5]; Renault[9] | - |
| 7 | 2008 | Barajas et Serra[2] | - |
Notes et références modifier
- Thomas W. Cusick, « View-Obstruction problems », Aequationes Math., vol. 9, nos 2–3, , p. 165–170 (DOI 10.1007/BF01832623)
- J. Barajas et O. Serra, « The lonely runner with seven runners », The Electronic Journal of Combinatorics, vol. 15, , R48.
- Wojciech Bienia, Luis Goddyn, Pavol Gvozdjak, Andras Sebo et Michael Tarsi, « Flows, view obstructions, and the lonely runner problem », Journal of combinatorial theory series B, vol. 72, , p. 1-9 (DOI 10.1006/jctb.1997.1770).
- Terence Tao, « A remark on the lonely runner conjecture », sur What's New, .
- Tom Bohman, Ron Holzman et Daniel J. Kleitman, « Six lonely runners », Electronic Journal of Combinatorics, vol. 8, no 2, .
- (de) Ulrich Betke et John M. Wills, « Untere Schranken für zwei diophantische Approximations-Funktionen », Monatshefte für Mathematik, vol. 76, no 3, , p. 214-217 (DOI 10.1007/BF01322924)
- Thomas W. Cusick, « View-obstruction problems in n-dimensional geometry », Journal of Combinatorial Theory, Series A, vol. 16, no 1, , p. 1-11 (DOI 10.1016/0097-3165(74)90066-1)
- (en) Thomas W. Cusick et Carl Pomerance, « View-obstruction problems, III », Journal of Number Theory, vol. 19, no 2, , p. 131-139 (DOI 10.1016/0022-314X(84)90097-0, lire en ligne, consulté le )
- (en) Jérôme Renault, « View-obstruction: a shorter proof for 6 lonely runners », Discrete Mathematics, vol. 287, nos 1-3, , p. 93-101 (DOI 10.1016/j.disc.2004.06.008, lire en ligne, consulté le )
Liens externes modifier
- Terence Tao, « A remark on the lonely runner conjecture », sur What's New,
- Pierre-Antoine Guihéneuf, « Coureur solitaire et forêts impénétrables », sur Images des mathématiques,
