Interested Article - Гипотеза об одиноком бегуне

Animation illustrating the case of 6 runners — Пример гипотезы об одиноком бегуне с 6 бегущими

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

Гипотеза

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

Обычная формулировка задачи предполагает, что бегуны имеют скорости, выражаемые целыми числами, не делящимися на одно и то же простое число. Игрок, который должен быть одиноким, имеет нулевую скорость. Гипотеза утверждает, что если 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	1984	Кузик и Померанц; Бьенья и др.	-
6	2001	Бохман, Хольцман, Кляйтман; Рено	-
7	2008	Барайас и Серра	-

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

Замечания

T. W. Cusick. View-Obstruction problems // Aequationes Math.. — 1973. — Т. 9 , вып. 2—3 . — С. 165—170 . — doi : .
↑ 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 : .
, с. 407.
Betke U. , Wills J. M. (нем.) // Monatshefte für Mathematik. — 1972. — Juni ( Bd. 76 , Nr. 3 ). — S. 214—217 . — ISSN . — doi : . [ ]
T. W. Cusick. View-obstruction problems in n-dimensional geometry // Journal of Combinatorial Theory, Series A. — 1974. — Т. 16 , вып. 1 . — С. 1—11 . — doi : .
Cusick T.W. , Pomerance Carl. (англ.) // Journal of Number Theory. — 1984. — October ( vol. 19 , no. 2 ). — P. 131—139 . — ISSN . — doi : . [ ]
T. Bohman, R. Holzman, D. Kleitman. Six lonely runners // Electronic Journal of Combinatorics. — 2001. — Т. 8 , вып. 2 .
Renault Jérôme. (англ.) // Discrete Mathematics. — 2004. — October ( vol. 287 , no. 1-3 ). — P. 93—101 . — ISSN . — doi : . [ ]
Dubickas, A. The lonely runner problem for many runners (неопр.) // Glasnik Matematicki. — 2011. — Т. 46 . — С. 25—30 . — doi : .

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

от 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 : .

[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 : .

[_60b17030858f3b77-4] , с. 407.

[5] Betke U. , Wills J. M. (нем.) // Monatshefte für Mathematik. — 1972. — Juni ( Bd. 76 , Nr. 3 ). — S. 214—217 . — ISSN . — doi : . [ ]

[6] T. W. Cusick. View-obstruction problems in n-dimensional geometry // Journal of Combinatorial Theory, Series A. — 1974. — Т. 16 , вып. 1 . — С. 1—11 . — doi : .

[7] Cusick T.W. , Pomerance Carl. (англ.) // Journal of Number Theory. — 1984. — October ( vol. 19 , no. 2 ). — P. 131—139 . — ISSN . — doi : . [ ]

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

[9] Renault Jérôme. (англ.) // Discrete Mathematics. — 2004. — October ( vol. 287 , no. 1-3 ). — P. 93—101 . — ISSN . — doi : . [ ]

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

Interested Article - Гипотеза об одиноком бегуне

Содержание

Гипотеза

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

Замечания

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

Литература

Same as Гипотеза об одиноком бегуне

Документальная гипотеза

Гипотеза Зейферта

The title for the last searches