Эта задача звучит как загадка для школьников — но лучшие математики мира не могли решить её 20 лет. Справился второкурсник

Задача об одиноком бегуне формулируется очень просто. Несколько человек стартуют из одной точки на круговой дорожке и бегут с разными постоянными скоростями. Математики спрашивают: найдётся ли для каждого бегуна момент, когда между ним и любым другим участником по дорожке будет не меньше 1/N круга, где N - общее число бегунов? Если такой момент наступает, бегун считается одиноким. Несмотря на простую постановку, чем больше участников, тем труднее доказать, что условие будет одновременно верно для каждого.

Тот же вопрос возникает и в других разделах математики. Его можно переформулировать на языке теории чисел, геометрии и теории графов. В одной версии речь идёт о прямой, проходящей через бесконечную сетку препятствий. В другой - о траекториях на бильярдном столе. В третьей о свойствах графов и сетевых структур. Поэтому задача про бегунов давно стала точкой пересечения нескольких математических направлений.

Интересно, что история началась вовсе не с бега. В 1960-е годы математиков интересовала задача о приближении иррациональных чисел, например числа π, рациональными дробями. Такая тема важна для теории чисел и её приложений. Тогда аспирант Йорг Вилльс высказал гипотезу: один старый способ таких приближений уже оптимален, и улучшить его нельзя. В 1998 году другие математики переписали ту же идею в форме задачи про бегунов. Так появилась современная версия гипотезы.

Позже выяснилось, что у неё есть и ещё одна эквивалентная формулировка. Нужно представить бесконечную клетчатую плоскость. В центре каждой клетки расположен маленький квадрат. Из одного из узлов сетки проводится прямая, не строго вертикальная и не строго горизонтальная. Дальше возникает вопрос: насколько большими могут быть такие квадраты, прежде чем любая такая прямая обязательно заденет один из них? По сути, речь идёт о том же самом вопросе, что и в задаче об одиноком бегуне.

Для малого числа участников задача решается сравнительно легко. Случаи с двумя и тремя бегунами доказываются элементарно. Для четырёх участников доказательство получили ещё в 1970-е годы. Дальше продвижение шло медленно, и к 2007 году математики сумели закрыть случаи до семи бегунов включительно. После этого наступил долгий перерыв. Почти двадцать лет никто не мог сделать следующий шаг.

Для отдельных случаев математики придумывали остроумные приёмы, но общего метода долго не было. В одном доказательстве помогали инструменты теории чисел, в другом геометрия, в третьем теория графов. Подход, который работал для одного значения, мог оказаться бесполезным для следующего. Поэтому каждое новое продвижение почти всегда требовало отдельного решения.

К середине 2000-х удалось хотя бы сократить число случаев, которые нужно проверять. Исследователи поняли, что не обязательно разбирать все возможные скорости, включая дробные и иррациональные. Достаточно доказать гипотезу для целых скоростей, и тогда общий случай последует автоматически. Такая замена сильно упростила задачу, но не сняла проблему полностью, потому что даже целочисленных наборов остаётся бесконечно много.

В 2015 году важный шаг сделал Теренс Тао. Он показал, что для фиксированного числа бегунов не нужно отдельно рассматривать очень большие скорости. Если гипотеза верна для скоростей до определённого порога, то она верна вообще для всех скоростей. Тем самым задача хотя бы теоретически сводилась к конечному числу проверок.

Однако на практике и такое упрощение почти не помогало. Даже после ограничения сверху число возможных наборов скоростей оставалось огромным. Перебор всех вариантов был слишком тяжёлым. Нужно было не просто сократить список, а резко сузить круг действительно важных случаев.

Именно это в прошлом году сделал Матьё Розенфельд из лаборатории информатики, робототехники и микроэлектроники в Монпелье. Он посмотрел на задачу с другой стороны. Вместо попытки сразу доказать гипотезу исследователь спросил: какими должны быть скорости, если гипотеза неверна? Иначе говоря, как выглядел бы контрпример, в котором хотя бы один бегун никогда не оказывается одиноким?

Выяснилось, что такой гипотетический контрпример должен удовлетворять очень жёстким арифметическим условиям. Розенфельд с помощью компьютерной программы и методов теории чисел показал: если взять произведение всех скоростей, то для контрпримера это произведение должно делиться на определённый набор простых чисел. Такой результат резко ограничил число возможных плохих случаев.

Дальше Розенфельд объединил этот вывод с идеей Тао о пороге. Он переписал условие уже через произведение скоростей. Получилось следующее: если гипотеза верна для всех произведений до некоторой границы, то она верна вообще всегда. Значит, любой контрпример, если бы он существовал, пришлось бы искать ниже этого порога. Но ранее уже было показано, что произведение скоростей в контрпримере должно делиться на слишком большой набор простых чисел, а значит, само это произведение неизбежно выходит далеко за пределы допустимой границы.

В результате возникло противоречие. Контрпример должен был бы одновременно быть и сравнительно маленьким, и очень большим. Такое невозможно. Значит, для восьми бегунов контрпримеров нет, и гипотеза верна. Так математики впервые за много лет продвинулись дальше случая с семью участниками.

На этом развитие не остановилось. Работу Розенфельда увидел Ноа Кравиц из Оксфорда и показал статью студенту второго курса Полу Тракултонгчаю, с которым занимался. Кравиц предложил ему рассмотреть следующий случай, то есть девять бегунов. Тракултонгчай взял за основу общий подход Розенфельда, но сумел заметно улучшить вычислительную часть.

Он разработал более эффективный способ находить простые делители, которые должен был бы иметь любой контрпример. Благодаря этому удалось быстрее исключить все возможные плохие случаи не только для девяти, но и сразу для десяти бегунов. В обоих вариантах гипотеза тоже оказалась верной. При этом Розенфельд независимо получил доказательство для девяти участников почти одновременно, всего через несколько дней после молодого коллеги из Оксфорда.

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

Полного доказательства для любого числа участников пока нет. Более того, нынешние методы уже упираются в пределы вычислительных возможностей. Для одиннадцати бегунов подход Розенфельда и Тракултонгчая оказывается слишком тяжёлым. Сами авторы новых результатов считают, что для следующего шага, скорее всего, понадобится другой взгляд на задачу.

Осторожность сохраняется и по другой причине. Хотя гипотеза подтверждена для всё большего числа случаев, математики пока не могут с уверенностью сказать, что она верна для любого N. Цепочка частных доказательств выглядит впечатляюще, но общего ответа всё ещё нет. В подобных задачах именно здесь проходит граница между серьёзным прогрессом и окончательным решением.

Тем не менее ситуация явно изменилась. После долгого застоя появились новые доказательства, новый метод и ощущение, что задача снова сдвинулась с места. Осенью в Ростоке планируют специальный семинар по гипотезе одинокого бегуна. Организаторы хотят собрать специалистов из разных областей, где возникает эта проблема, чтобы свести вместе подходы теории чисел, геометрии, теории графов и вычислительной математики.