« Conjecture du coureur solitaire » : différence entre les versions

Contenu supprimé Contenu ajouté

Intégrés

Version du 14 mai 2015 à 20:31

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

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 distincts deux à deux. 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 pour certains temps.

Résultats démontrés

k	année	démontrés par	notes
1	-	-	trivial: tout t convient
2	-	-	trivial: t = 1 / (2 * (v₁-v₀))
3	-	-	Toute preuve pour k>3 prouve également le cas k=3
4	1972	Betke et Wills;^[4] Cusick^[5]	-
5	1984	Cusick et Pomerance;^[6] Bienia et al.^[3]	-
6	2001	Bohman, Holzman, Kleitman;^[7] Renault^[8]	-
7	2008	Barajas et Serra^[2]	-

Notes

↑ T. W. Cusick, « View-Obstruction problems », Aequationes Math., vol. 9, n^os 2–3,‎ 1973, p. 165–170 (DOI 10.1007/BF01832623)
↑ ^{a et b} J. Barajas and O. Serra, « The lonely runner with seven runners », The Electronic Journal of Combinatorics, vol. 15,‎ 2008, R48
↑ ^{a et b} W. Bienia et al., « Flows, view obstructions, and the lonely runner problem », Journal of combinatorial theory series B, vol. 72,‎ 1998, p. 1–9 (DOI 10.1006/jctb.1997.1770)
↑ DOI 10.1007/BF01322924
↑ T. W. Cusick, « View-obstruction problems in n-dimensional geometry », Journal of Combinatorial Theory, Series A, vol. 16, n^o 1,‎ 1974, p. 1–11 (DOI 10.1016/0097-3165(74)90066-1)
↑ DOI 10.1016/0022-314X(84)90097-0
↑ « {{{1}}} »
↑ DOI 10.1016/j.disc.2004.06.008

Arithmétique et théorie des nombres

[1] T. W. Cusick, « View-Obstruction problems », Aequationes Math., vol. 9, n^os 2–3,‎ 1973, p. 165–170 (DOI 10.1007/BF01832623)

[BarajasSerra2008-2] {a et b} J. Barajas and O. Serra, « The lonely runner with seven runners », The Electronic Journal of Combinatorics, vol. 15,‎ 2008, R48

[BienaEtAl1998-3] {a et b} W. Bienia et al., « Flows, view obstructions, and the lonely runner problem », Journal of combinatorial theory series B, vol. 72,‎ 1998, p. 1–9 (DOI 10.1006/jctb.1997.1770)

[4] DOI 10.1007/BF01322924

[5] T. W. Cusick, « View-obstruction problems in n-dimensional geometry », Journal of Combinatorial Theory, Series A, vol. 16, n^o 1,‎ 1974, p. 1–11 (DOI 10.1016/0097-3165(74)90066-1)

[6] DOI 10.1016/0022-314X(84)90097-0

[7] « {{{1}}} »

[8] DOI 10.1016/j.disc.2004.06.008

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]