thumb|right|alt=Az n=6 esetet illusztráló animáció|Példa a magányosfutó-sejtésre 6 futóval A magányosfutó-sejtés (lonely runner conjecture, LRC) J. M. Wills több mint ötvenéves, számelméleti, közelebbről a diofantikus approximációval kapcsolatos sejtése. Folyományai a matematika több területén előfordulnak, köztük találhatók takarási problémák, illetve a távolsággráfok és cirkuláns (irányítatlan, ciklikus csoportot tartalmazó, csúcstranzitív gráfok) kromatikus számának meghatározása is. A sejtés szemléletes nevét L. Goddyntól kapta 1998-ban.
A sejtés Vegyünk egységnyi hosszú körpályát, rajta k futóval. A t = 0 időpillanatban elindul az összes futó, azonos kiindulási pontból, állandó, de páronként különböző sebességgel. Egy futót t időpillanatban „magányosnak” tekintünk akkor, ha legalább 1 / k távolságra van az összes többi futótól az adott t pillanatban. A magányosfutó-sejtés azt állítja, hogy minden futó magányos valamilyen időpillanatban. A probléma egy célszerű átfogalmazása felteszi, hogy a futók sebessége egész szám, nincs közös prímosztójuk és a magányosnak választott futó sebessége zérus. A sejtés ekkor úgy szól, hogy bármely k − 1 darab, 1 legnagyobb közös osztójú pozitív egész szám által alkotott D halmazt tekintve,
ahol ||x|| az x valós szám távolságát jelöli a legközelebbi egésztől. A sejtéssel ekvivalens feladatok között van az 1971-ben megfogalmazott takarási probléma (view obstruction problemT.W. Cusick: View-obstruction problems in n-dimensional geometry) is.
Alacsony k értékekre a feladat viszonylag egyszerű, de a futók számának növekedésével rendkívül bonyolulttá válik.
Eddigi eredmények
k bizonyítás éve szerzője jegyzet 1 - - triviális: t = 0; bármely t 2 - - triviális: t = 1 / (2 · (v1−v0)) 3 - - Bármely bizonyítás k>3-ra bizonyítja a k=3 esetet is 4 1972 Betke és Wills; Cusick - 5 1984 Cusick és Pomerance; Bienia et al. - 6 2001 Bohman, Holzman, Kleitman; Renault - 7 2008 Barajas és Serra -
Dubickas 2011-ben megmutatta, hogy elegendően nagy számú futó esetén, melyek sebességei , a magányosfutó-sejtés igaz, amennyiben .
Jegyzetek
További információk article in the Open Problem Garden Clayton Barnes II: The Lonely Runner Conjecture – A detailed survey of the Lonely Runner Conjecture and its connection between Diophantine approximation and View-obstruction problems Richard Green: The lonely runner conjecture
Kapcsolódó szócikkek A hosszútávfutó magányossága
Kategória:Sejtések