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

Пример гипотезы об одиноком бегуне с 6 бегущими

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

Гипотеза

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

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

$\mathrm{\exists }t\in ℝ\mathrm{\forall }d\in D||td||\ge \frac{1}{k},$

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

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

k	год доказательства	кем доказано	замечания
1	-	-	тривиально: t = 0; для любого t
2	-	-	тривиально: t = 1 / (2 * (v1-v0))
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}\ge 1+\frac{33\log (k)}{k},$ то гипотеза выполнена.

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

• статья в «the Open Problem Garden» Шаблон:Wayback

Литература

• Шаблон:Книга