Гипотеза об одиноком бегуне — гипотеза, выдвинутая в 1967. Приложения включают задачи ограничения обзора и вычисления хроматического числа дистанционных и циркулянтных графов. Гипотеза получила образное имя благодаря Годдину (L. Goddyn) в 1998.
Формулировка
Пусть k бегунов бегут по круговой дорожке единичной длины. В момент t = 0 все бегуны находились в одной точке и начали забег. Скорость бегунов попарно различна. Говорят, что бегун A одинок в момент t, если он находится на расстоянии по меньшей мере 1/k от всех остальных бегунов. Гипотеза утверждает, что каждый игрок будет одиноким в некоторый момент времени.
Обычная формулировка задачи предполагает, что бегуны имеют скорости, выражаемые целыми числами, не делящимися на одно и то же простое число. Игрок, который должен быть одиноким, имеет нулевую скорость. Гипотеза утверждает, что если D – произвольный набор целых положительных чисел, который содержит ровно число, с наибольшим общим делителем равным 1, тогда
где означает расстояние от числа 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 году литовским математиком было доказано, что для достаточно большого количества бегунов со скоростями , если гипотеза выполнена.
Замечания
Внешние ссылки статья в «the Open Problem Garden»
Литература
Категория:Теория чисел Категория:Диофантовы уравнения Категория:Гипотезы Категория:Математические гипотезы