Conjecture du coureur solitaire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
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 due à J. 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 L. Goddyn en 1998[3].

La conjecture[modifier | modifier le code]

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 | modifier le code]

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 | modifier le code]

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 | modifier le code]

  1. T. W. Cusick, « View-Obstruction problems », Aequationes Math., vol. 9, no 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 T. Bohman, R. Holzman et D. Kleitman, « Six lonely runners », Electronic Journal of Combinatorics, vol. 8, no 2,‎ .
  6. (de) U. Betke et J.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. T. 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) T.M. 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)
  9. (en) Jérôme Renault, « View-obstruction: a shorter proof for 6 lonely runners », Discrete Mathematics, vol. 287, no 1-3,‎ , p. 93-101 (DOI 10.1016/j.disc.2004.06.008, lire en ligne)

Liens externes[modifier | modifier le code]