„Magányosfutó-sejtés” változatai közötti eltérés
Syp (vitalap | szerkesztései) Új oldal, tartalma: „thumb|right|alt=Az n=6 esetet illusztráló animáció|Példa a magányos futó-sejtésre 6 futóval A '''„magányos futó”-sejtés''' ''…” |
(Nincs különbség)
|
A lap 2014. április 29., 21:41-kori változata
A „magányos futó”-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 a 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
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ányos futó”-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 lnko-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
| 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] | - |
Jegyzetek
- ↑ 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.
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