Он всегда с нетерпением ждал этого момента. Всё застывает в ожидании выстрела стартового пистолета. Звуки и краски внешнего мира уходят на второй план. Весь организм замирает, как сильно сжатая пружина. Время становится долгим и тягучим, течёт всё медленнее и неохотнее. Проходит целая вечность, прежде чем раздаётся наконец резкий стартовый выстрел. Мозг ещё не успевает ничего понять и осознать, а тренированное тело уже привычно распрямляется и мчится вперёд. На соседних дорожках летят соперники. Они всегда рядом, слишком близко, никуда от них не деться, не оторваться в отчаянном рывке. Обычно силы почти равны. Всё решают миллисекунды, миллиметры и фотофиниш. Но не в этот раз...
Заклинившая гайка
Математики — удивительные люди. Они обожают неразрешимые проблемы и недоказуемые гипотезы. Их хлебом не корми, дай только придумать какую-нибудь заковыристую задачу и дать ей какое-нибудь удивительное название. И ладно бы, если эти задачи были просто абстрактными упражнениям для ума. Но ведь как-то так получается, что многие из них имеют принципиальное значение для развития науки. Как заклинившая гайка — пока не открутишь, дальше не попадёшь.
Вот и гипотеза об одиноком бегуне оказалась одной из таких задач. Её сформулировал в 1967 году математик Йорг Виллс (J. M. Wills). Правда, в то время эта гипотеза ещё не получила своё поэтическое название. Об этом позаботился в 1998 году Луис Годдин (L. Goddyn).
Суть гипотезы
Предположим, что n бегунов бегают по кольцевой дорожке. Длина дорожки условно равна 1. Стартуют все бегуны в одной точке, но скорость у всех разная. Бегун считается одиноким, если в какой-то момент времени он находится на расстоянии по меньшей мере 1/n от любого другого бегуна.
Можно ли при таких условиях утверждать, что каждый из бегунов рано или поздно окажется одиноким (каждый в своё время)? Вроде как да, можно. Но никто пока так и не смог доказать это утверждение для любого количества бегунов. В общем, знаменитые строчки «Красота! Среди бегущих первых нет и отстающих» — это не про наш случай.
В строгой формулировке гипотезы указано, что скорости бегунов должны быть выражены целыми числами, которые не делятся на одно и то же простое число. Одинокий бегун при этом будет иметь нулевую скорость. Если D — произвольный набор целых положительных чисел, который содержит ровно k−1 число, с наибольшим общим делителем, равным 1, тогда:
Здесь запись ||x|| означает расстояние от числа x до ближайшего целого.
Странный эксперимент
…В этом странном экспериментальном забеге всё было не так, как обычно. Взять хотя бы коридор, по которому ему предстояло бежать. Ни одного прямого участка, где можно было бы как следует разогнаться. Только плавно изгибающийся гигантский круг. Поворот почти незаметен, но он всегда есть. И это здорово раздражало — как маленький битый пиксель посреди идеально чистого экрана. Да и выбор соперников по забегу был, мягко говоря, странным. Толпа спортсменов на старте состояла из представителей всех возрастов и групп населения: от школьников-юниоров до бодрых пенсионеров. Были здесь и хорошо знакомые ему бегуны, с которыми он не раз встречался на международных стартах. Он хорошо знал, что с ними ему тягаться в скорости пока рановато.
После выстрела стартового пистолета вся эта пёстрая толпа ломанулась по коридору и быстро растянулась в длинный хвост. Хорошо тренированные спортсмены вырвались далеко вперёд, слабые бегуны тут же отстали. Он знал, что по условиям эксперимента бежать ему предстоит не один круг, поэтому двигался в комфортном, спокойном темпе — экономил силы, но и не филонил понапрасну. Вскоре он сделал почти полный круг и нагнал безнадёжно отставших. Но и его самого к этому времени начали один за другим опережать прыткие чемпионы...
Пока их только семеро
Как это водится, для подобных гипотез существует ряд подтверждений для отдельных частных условий. Гипотеза об одиноком бегуне подтверждена для тех случаев, когда количество бегунов n меньше 8. Точнее, для n = 1 её вообще подтверждать не нужно.
Единственный грустный бегун одинок по определению прямо на старте.
Для n = 2 время наступления одиночества для бегуна можно вычислить по формуле:
Например, если скорость одного бегуна равна 1, а другого 2, то рано или поздно они окажутся на противоположных частях дорожки и будут, если можно так выразиться, взаимно одинокими.
Для n = 3 у математиков есть хитрая «отмазка». Считается, что любое доказательство для n > 3 автоматически подтверждает и верность гипотезы для n = 3.
А вот дальше дело стало продвигаться медленнее, чем хотелось. Вот хроника появления доказательств для разных значений n:
4 — 1972 год;
5 — 1984 год;
6 — 2001 год;
7 — 2008 год.
Все эти доказательства — довольно объёмные труды со множеством расчётов. Для n > 7 доказательств верности гипотезы до сих пор не существует. Правда, в 2011 году учёные получили формулу для определения скоростей, при которых гипотеза подтверждается для любого достаточно большого количества бегунов. Однако формула для конкретных скоростей — ещё не доказательство всей гипотезы. Ведь в итоге нужно доказать, что гипотеза верна для любого n безо всяких условий и дополнительных оговорок.
Внезапное исчезновение
…В этот раз никто не бежал рядом, у всех соперников были разные скорости. Но в то же время впереди и позади него всегда кто-то был. Ширина коридора позволяла спортсменам легко обгонять друг друга. Довольно быстро он привык к этому и методично опережал соперников одного за другим. Некоторых он стал узнавать в лицо, пару раз даже поприветствовал кого-то из них на очередном круге. Иногда он сторонился и давал обогнать себя более опытным спортсменам.
Но вдруг произошло что-то странное. Он внезапно осознал, что впереди не осталось ни одного бегуна. На всём протяжении своей видимой части коридор был абсолютно пуст. Ничего особенного в этом не было, но ему вдруг стало крайне неуютно. Внезапное исчезновение других бегунов было настолько необычно, что он нервно сглотнул и оглянулся. Этого можно было и не делать — он уже знал, что и сзади тоже не будет ни души. Внезапно он оказался в полном одиночестве в этом странном плавно изгибающемся коридоре. Вокруг стало неестественно тихо. Он машинально продолжал бежать, и звук его шагов гулким эхом отражался от стен…
Зачем нужна вся эта беготня
У кого-то уже вертится в голове вполне закономерный вопрос: «А зачем всё это нужно?». Почему так важно доказать какую-то абстрактную гипотезу о бегунах, которые нарезают круги в совершенно неестественных условиях. Всё дело в том, что часто подобные математические задачи — это красивое изложение серьёзных проблем, которые лежат в корне более сложных задач. Гипотеза об одиноком бегуне берёт своё начало в теории чисел и исследованиях диофантовых уравнений. Гипотеза связана с задачей вычисления хроматического числа дистанционных и циркулянтных графов. А уж эта задача имеет самое что ни на есть практическое применение (UPD). Математика — она такая: если какая-то её часть кажется бесполезной, значит мы ещё пока просто не знаем, как её можно использовать.
Математику уже затем учить надо, что она ум в порядок приводит.
М. В. Ломоносов
…Прошло несколько мучительных секунд и наваждение прошло. Сзади его догнали более тренированные спортсмены, спереди из-за поворота показался очередной медленный бегун. Он снова был среди людей, снова участвовал в бесконечной гонке. Эксперимент был окончен. Учёные сделали свои выводы: сколько бы бегунов ни участвовало в забеге, каждый из них рано или поздно может оказаться в одиночестве. Но одинокий бегун точно знал — там, за поворотом, всегда обязательно кто-то есть.
Ещё почитать: