Conjecture du coureur solitaire

Animation illustrant le cas de 6 coureurs
Exemple de la conjecture du coureur solitaire avec 6 coureurs

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

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

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

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

  1. ↑ Thomas W. Cusick, « View-Obstruction problems », Aequationes Math., vol. 9, nos 2–3,‎ , p. 165–170 (DOI 10.1007/BF01832623)
  2. ↑ a et b J. Barajas et O. Serra, « The lonely runner with seven runners », The Electronic Journal of Combinatorics, vol. 15,‎ , R48.
  3. ↑ a et b 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).
  4. ↑ Terence Tao, « A remark on the lonely runner conjecture », sur What's New, .
  5. ↑ a et b Tom Bohman, Ron Holzman et Daniel J. Kleitman, « Six lonely runners », Electronic Journal of Combinatorics, vol. 8, no 2,‎ .
  6. ↑ (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)
  7. ↑ 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)
  8. ↑ (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 )
  9. ↑ (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