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

 В теории игр, особенно при изучении диофантовых приближений,гипотеза об одиноком бегуне — это гипотеза, выдвинутаяУиллсом (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 *(v\textsubscript1-v\textsubscript0))
3--Любое доказательство для k\textgreater3 такжедоказывает k=3
41972Бетке и Виллс; Кузик-
51984Кузик и Померанц; Бьенья и др.-
62001Бохман, Хольцман, Кляйтман; Рено-
72008Барайас и Серра-

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

Замечания


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