WikiSort.ru - Не сортированное

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

Гипотеза

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

Обычная формулировка задачи предполагает, что бегуны имеют скорости, выражаемые целыми числами, не делящимися на одно и то же простое число. Игрок, который должен быть одиноким, имеет нулевую скорость. Гипотеза утверждает, что если 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}},}$ то гипотеза выполнена^[10].

Замечания

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

• статья в «the Open Problem Garden»

Литература

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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка.