Гипотеза об одиноком бегуне (Inhkmy[g kQ k;nuktkb Qyiruy)

В теории игр, особенно при изучении диофантовых приближений, гипотеза об одиноком бегуне — это гипотеза, выдвинутая Уиллсом (J. M. Wills) в 1967. Приложения гипотезы широко представлены в математике, они включают задачи ограничения обзора^[1] и вычисления хроматического числа дистанционных и циркулянтных графов^[2]. Гипотеза получила образное имя благодаря Годдину (L. Goddyn) в 1998^[3].

Гипотеза

Пусть k бегунов бегут по круговой дорожке единичной длины. В момент t = 0 все бегуны находились в одной точке и начали забег. Скорость бегунов попарно различна. Говорят, что бегун A одинок в момент t, если он находится на расстоянии по меньшей мере 1/k от всех остальных бегунов. Гипотеза утверждает, что каждый игрок будет одиноким в некоторый момент времени.^[4]

Обычная формулировка задачи предполагает, что бегуны имеют скорости, выражаемые целыми числами, не делящимися на одно и то же простое число. Игрок, который должен быть одиноким, имеет нулевую скорость. Гипотеза утверждает, что если D – произвольный набор целых положительных чисел, который содержит ровно $k-1$ число, с наибольшим общим делителем равным 1, тогда

\exists t\in \mathbb {R} \quad \forall d\in D\quad ||td||\geq {\frac {1}{k}},

где $||x||$ означает расстояние от числа x до ближайшего целого.

Известные результаты

Нерешённые проблемы математики: Можно ли доказать гипотезу об одиноком бегуне для k≥8?

k	год доказательства	кем доказано	замечания
1	-	-	тривиально: t = 0; для любого t
2	-	-	тривиально: t = 1 / (2 * (v₁-v₀))
3	-	-	Любое доказательство для k>3 также доказывает k=3
4	1972	Бетке и Виллс;^[5] Кузик^[6]	-
5	1984	Кузик и Померанц;^[7] Бьенья и др.^[3]	-
6	2001	Бохман, Хольцман, Кляйтман;^[8] Рено^[9]	-
7	2008	Барайас и Серра^[2]	-

В 2011 году было доказано, что для достаточно большого количества бегунов с скоростями $v_{1}<v_{2}<...<v_{k}$ , если ${\frac {v_{i+1}}{v_{i}}}\geq 1+{\frac {33\log(k)}{k}},$ то гипотеза выполнена^[10].

Замечания

↑ T. W. Cusick. View-Obstruction problems // Aequationes Math.. — 1973. — Т. 9, вып. 2—3. — С. 165—170. — doi:10.1007/BF01832623.
↑ ¹ ² J. Barajas and O. Serra. The lonely runner with seven runners // The Electronic Journal of Combinatorics. — 2008. — Т. 15. — С. R48.
↑ ¹ ² 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.
↑ Стюарт, 2015, с. 407.
↑ 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. [исправить]
↑ Dubickas, A. The lonely runner problem for many runners (неопр.) // Glasnik Matematicki. — 2011. — Т. 46. — С. 25—30. — doi:10.3336/gm.46.1.05.

Внешние ссылки

статья в «the Open Problem Garden» Архивная копия от 9 ноября 2020 на Wayback Machine

Литература

Иэн Стюарт. «Величайшие математические задачи». — М.: «Альпина нон-фикшн», 2015. — 460 с. — ISBN 978-5-91671-318-3.

[1] T. W. Cusick. View-Obstruction problems // Aequationes Math.. — 1973. — Т. 9, вып. 2—3. — С. 165—170. — doi:10.1007/BF01832623.

[BarajasSerra2008-2] ¹ ² J. Barajas and O. Serra. The lonely runner with seven runners // The Electronic Journal of Combinatorics. — 2008. — Т. 15. — С. R48.

[BienaEtAl1998-3] ¹ ² 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.

[_60b17030858f3b77-4] Стюарт, 2015, с. 407.

[5] 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. [исправить]

[6] 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.

[7] 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. [исправить]

[8] T. Bohman, R. Holzman, D. Kleitman. Six lonely runners // Electronic Journal of Combinatorics. — 2001. — Т. 8, вып. 2.

[9] 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. [исправить]

[10] Dubickas, A. The lonely runner problem for many runners (неопр.) // Glasnik Matematicki. — 2011. — Т. 46. — С. 25—30. — doi:10.3336/gm.46.1.05.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]