Magányosfutó-sejtés
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,[1] 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.[2] A sejtés szemléletes nevét L. Goddyntól kapta 1998-ban.[3]
A sejtés[szerkeszté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 problem[4]) 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[szerkesztés]
| 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;[5] Cusick[6] | - |
| 5 | 1984 | Cusick és Pomerance;[7] Bienia et al.[3] | - |
| 6 | 2001 | Bohman, Holzman, Kleitman;[8] Renault[9] | - |
| 7 | 2008 | Barajas és Serra[2] | - |
Dubickas 2011-ben megmutatta,[10] hogy elegendően nagy számú futó esetén, melyek sebességei , a magányosfutó-sejtés igaz, amennyiben .
Jegyzetek[szerkesztés]
- ↑ T. W. Cusick (1973). „View-Obstruction problems”. Aequationes Math. 9 (2–3), 165–170. o. DOI:10.1007/BF01832623.
- ↑ a b J. Barajas and O. Serra (2008). „The lonely runner with seven runners”. The Electronic Journal of Combinatorics 15, R48. o.
- ↑ a b W. Bienia et al. (1998). „Flows, view obstructions, and the lonely runner problem”. Journal of combinatorial theory series B 72, 1–9. o. DOI:10.1006/jctb.1997.1770.
- ↑ T.W. Cusick: View-obstruction problems in n-dimensional geometry
- ↑ (1972) „Untere Schranken für zwei diophantische Approximations-Funktionen”. Monatshefte für Mathematik 76 (3), 214. o. DOI:10.1007/BF01322924.
- ↑ T. W. Cusick (1974). „View-obstruction problems in n-dimensional geometry”. Journal of Combinatorial Theory, Series A 16 (1), 1–11. o. DOI:10.1016/0097-3165(74)90066-1.
- ↑ (1984) „View-obstruction problems, III”. Journal of Number Theory 19 (2), 131–139. o. DOI:10.1016/0022-314X(84)90097-0.
- ↑ Bohman, T.; Holzman, R. & Kleitman, D. (2001), "Six lonely runners", Electronic Journal of Combinatorics 8 (2)
- ↑ (2004) „View-obstruction: A shorter proof for 6 lonely runners”. Discrete Mathematics 287, 93–101. o. DOI:10.1016/j.disc.2004.06.008.
- ↑ (2011) „The lonely runner problem for many runners”. Glasnik Matematicki 46, 25–30. o. DOI:10.3336/gm.46.1.05.
További információk[szerkesztés]
- 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