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

Гипотеза

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

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

${\displaystyle \exists t\in \mathbb {R} \quad \forall d\in D\quad ||td||\geq {\frac {1}{k}},}$

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

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

Нерешённые проблемы математики : Можно ли доказать гипотезу об одиноком бегуне для k≥8?

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

Замечания

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

• от 9 ноября 2020 на Wayback Machine

Литература

• Иэн Стюарт . «Величайшие математические задачи». — М. : « Альпина нон-фикшн », 2015. — 460 с. — ISBN 978-5-91671-318-3 .