Гипотеза об одиноком бегуне: различия между версиями
Jumpow (обсуждение | вклад) Переведена статья "Lonely runner conjecture" |
(нет различий)
|
Версия от 18:59, 10 ноября 2014
![Animation illustrating the case of 6 runners](http://upload.wikimedia.org/wikipedia/commons/thumb/3/33/Lonely_runner.gif/220px-Lonely_runner.gif)
В теории игр, особенно при изучении диофантовых приближений, гипотеза об одиноком бегуне — это гипотеза, выдвинутая Виллсом (J. M. Wills) в 1967. Приложения гипотезы широко представлены в математике, они включают задачи ограничения обзора[1] и вычисления хроматического числа дистанционных и циркулянтных графов.[2] Гипотеза получила образное имя благодаря Годину (L. Goddyn) в 1998.[3]
Гипотеза
Пусть k бегунов бегут по круговому треку единичной длины. В момент t = 0 все бегуны находились в одной точке и начали забег. Скорость бегунов попарно различна. Говорят, что бегун A одинок в момент t, если он находится на расстоянии по меньшей мере 1/k от всех остальных бегунов. Гипотеза утверждает, что каждый игрок будет одиноким в некоторый момент времени.
Обычная формулировка задачи предполагает, что бегуны имеют скорости, выражаемые целыми числами, не делящимися на одно и то же простое число. Игрок, который должен быть одиноким, имеет нулевую скорость. Гипотеза утверждает, что для любого набора положительных чисел D размером k − 1 с НОД = 1,
где ||x|| означает расстояние числа x к ближайшему целому.
Известные результаты
k | год доказательства | кем доказано | замечания |
---|---|---|---|
1 | - | - | тривиально: t = 0; для любого t |
2 | - | - | тривиально: t = 1 / (2 * (v1-v0)) |
3 | - | - | Любое доказательство для k>3 также доказывает k=3 |
4 | 1972 | Бетке и Виллс;[4] Кузик[5] | - |
5 | 1984 | Кузик и Померанц;[6] Бьенья и др.[3] | - |
6 | 2001 | Бохман, Хольцман, Кляйтман;[7] Рено[8] | - |
7 | 2008 | Барайас и Серра[2] | - |
Замечания
- ↑ T. W. Cusick. View-Obstruction problems // Aequationes Math.. — 1973. — Т. 9, вып. 2–3. — С. 165–170. — doi:10.1007/BF01832623.
- ↑ 1 2 J. Barajas and O. Serra. The lonely runner with seven runners // The Electronic Journal of Combinatorics. — 2008. — Т. 15. — С. R48.
- ↑ 1 2 W. Bienia et al. Flows, view obstructions, and the lonely runner problem // Journal of combinatorial theory series B. — 1998. — Т. 72. — С. 1–9. — doi:10.1006/jctb.1997.1770.
- ↑ Betke U., Wills J. M. Untere Schranken für zwei diophantische Approximations-Funktionen (нем.) // Monatshefte für Mathematik. — 1972. — Juni (Bd. 76, Nr. 3). — S. 214—217. — ISSN 0026-9255. — doi:10.1007/BF01322924.
- ↑ T. W. Cusick. View-obstruction problems in n-dimensional geometry // Journal of Combinatorial Theory, Series A. — 1974. — Т. 16, вып. 1. — С. 1–11. — doi:10.1016/0097-3165(74)90066-1.
- ↑ Cusick T.W., Pomerance Carl. View-obstruction problems, III (англ.) // Journal of Number Theory. — 1984. — October (vol. 19, no. 2). — P. 131—139. — ISSN 0022-314X. — doi:10.1016/0022-314X(84)90097-0.
- ↑ T. Bohman, R. Holzman, D. Kleitman. Six lonely runners // Electronic Journal of Combinatorics. — 2001. — Т. 8, вып. 2.
- ↑ Renault Jérôme. View-obstruction: a shorter proof for 6 lonely runners (англ.) // Discrete Mathematics. — 2004. — October (vol. 287, no. 1-3). — P. 93—101. — ISSN 0012-365X. — doi:10.1016/j.disc.2004.06.008.
Внешние ссылки
Для улучшения этой статьи желательно:
|