Показать меню

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

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

Гипотеза

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

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

∃ t ∈ R ∀ d ∈ D | | t d | | ≥ 1 k , {displaystyle exists tin mathbb {R} quad forall din Dquad ||td||geq {frac {1}{k}},}

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

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

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

Замечания

  • T. W. Cusick. View-Obstruction problems // Aequationes Math.. — 1973. — Т. 9, вып. 2—3. — С. 165—170. — doi:10.1007/BF01832623.
  • 1 2 J. Barajas and O. Serra. The lonely runner with seven runners // The Electronic Journal of Combinatorics. — 2008. — Т. 15. — С. R48.
  • 1 2 W. Bienia et al. Flows, view obstructions, and the lonely runner problem // Journal of combinatorial theory series B. — 1998. — Т. 72. — С. 1—9. — doi:10.1006/jctb.1997.1770.
  • ↑ Стюарт, 2015, с. 407.
  • Betke U., Wills J. M. Untere Schranken für zwei diophantische Approximations-Funktionen (нем.) // Monatshefte für Mathematik. — 1972. — Juni (Bd. 76, Nr. 3). — S. 214—217. — ISSN 0026-9255. — doi:10.1007/BF01322924.
  • T. W. Cusick. View-obstruction problems in n-dimensional geometry // Journal of Combinatorial Theory, Series A. — 1974. — Т. 16, вып. 1. — С. 1—11. — doi:10.1016/0097-3165(74)90066-1.
  • Cusick T.W., Pomerance Carl. View-obstruction problems, III (англ.) // Journal of Number Theory. — 1984. — October (vol. 19, no. 2). — P. 131—139. — ISSN 0022-314X. — doi:10.1016/0022-314X(84)90097-0.
  • T. Bohman, R. Holzman, D. Kleitman. Six lonely runners // Electronic Journal of Combinatorics. — 2001. — Т. 8, вып. 2.
  • Renault Jérôme. View-obstruction: a shorter proof for 6 lonely runners (англ.) // Discrete Mathematics. — 2004. — October (vol. 287, no. 1-3). — P. 93—101. — ISSN 0012-365X. — doi:10.1016/j.disc.2004.06.008.
  • Dubickas, A. The lonely runner problem for many runners (неопр.) // Glasnik Matematicki. — 2011. — Т. 46. — С. 25—30. — doi:10.3336/gm.46.1.05.
  • Внешние ссылки

    • статья в «the Open Problem Garden» Архивная копия от 9 ноября 2020 на Wayback Machine
    Еще по этой теме:
    Сведение (теория сложности вычислений)
    13:00, 17 апрель
    Сведение (теория сложности вычислений)
    Сведение в теории сложности вычислений — преобразование одной задачи к другой. В общем случае, для алгоритма, преобразующего экземпляры задачи P
    Гипотеза об одиноком бегуне
    04:02, 14 октябрь
    Гипотеза об одиноком бегуне
    В теории игр, особенно при изучении диофантовых приближений, гипотеза об одиноком бегуне — это гипотеза, выдвинутая Уиллсом (J. M. Wills) в 1967. Приложения гипотезы широко представлены в
    Урало-алтайская гипотеза
    22:31, 15 декабрь
    Урало-алтайская гипотеза
    Урало-алтайские языки — гипотеза, весьма популярная в конце XIX — начале XX веков. В рамках данной гипотезы предполагалось общее происхождение уральских и алтайских языков. Гипотезу выдвинул в 1844
    Дзета-функция Дедекинда
    07:29, 05 декабрь
    Дзета-функция Дедекинда
    Дзета-функция Дедекинда ζ K ( s ) {displaystyle zeta _{K}(s)} — это
    Бог: неудачная гипотеза
    05:03, 03 декабрь
    Бог: неудачная гипотеза
    «Бог: неудачная гипотеза» (англ. God: The Failed Hypothesis) — научно-популярная книга американского физика Виктора Стенджера, вышедшая в 2007 году, в которой он утверждает, что не существует
    Происхождение гумусовых веществ в торфяных почвах
    12:47, 13 март
    Происхождение гумусовых веществ в торфяных почвах
    Постоянной составной частью торфа являются гумусовые вещества. В этом состоит главное принципиальное отличие органического вещества торфа от органического вещества растений-торфообразователей, в
    Комментарии:
    Добавить комментарий
    Ваше Имя:
    Ваш E-Mail: