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

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

Гипотеза


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

\existtRdD||td||1k,
  где ||x|| означает расстояние от числа x до ближайшего целого.

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


kгод доказательствакем доказанозамечания
1--тривиально: t = 0; для любого t
2--тривиально: t = 1 / (2 * (v1-v0))
3--Любое доказательство для k\textgreater3 также доказывает k=3
41972Бетке и Виллс; Кузик-
51984Кузик и Померанц; Бьенья и др.-
62001Бохман, Хольцман, Кляйтман; Рено-
72008Барайас и Серра-

 В 2011 году было доказано, что для достаточно большого количества бегунов с скоростями v1<v2<...<vk, если vi+1vi1+33log(k)k, то гипотеза выполнена.

Замечания


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