«Вызов подземки» не является первым в своем роде. Он представляет более сложный вариант игры, популярной в прусском городе Кёнигсберг в XVIII в. В центре города находится остров, омываемый двумя рукавами реки Прегель, далее река течет на запад и впадает в Балтийское море. В XVIII в. через Прегель было перекинуто семь мостов, и горожане заполняли свой воскресный досуг тем, что пытались пройти по всем по ним, побывав на каждом мосту только один раз. В отличие от «Вызова подземки» главное при этом не скорость, а то, возможен ли такой маршрут вообще. Как ни старались жители Кёнигсберга, они не могли решить эту задачу. Была ли эта миссия на самом деле невыполнима, или все же имелся путь, не найденный горожанами, который проходил по семи мостам по одному разу?
Проблема была окончательно решена Леонардом Эйлером, швейцарским математиком, работавшим в Петербургской академии наук в 800 км к северо-востоку от Кёнигсберга (ранее обсуждалась его задача о греко-латинских квадратах). Эйлер совершил важнейший концептуальный скачок. Он понял, что фактические размеры города были совершенно не важны: значимо было то, как мосты соединялись друг с другом (тот же принцип применяется при составлении топологической карты лондонского метро). Каждый из четырех участков земли, соединяемых мостами Кёнигсберга, может быть сжат в точку, называемую вершиной. Мостам при этом соответствуют линии, соединяющие вершины. В результате получается карта мостов Кёнигсберга, несколько напоминающая значительно упрощенную карту лондонского метро (рис. 3.13).
Рис. 3.13
Задача о прохождении мостов сводится к тому, возможно ли начертить эту карту, не отрывая карандаша от бумаги и не проводя по одной и той же линии дважды (одним росчерком). Благодаря новой математической перспективе Эйлер сумел понять, что невозможно пройти по всем семи мостам, побывав на каждом из них только один раз.
Но почему же это невозможно? При рисовании карты каждая вершина, которую вы посетили в середине путешествия, должна иметь одну входящую и одну выходящую линию. Если вы оказываетесь в этой вершине снова, значит, вы пришли в нее по новому «мосту» и так же должны выйти из нее через новый «мост». Значит, в каждой вершине должно сходиться четное число линий, за исключением начала и конца путешествия.
Если мы поглядим на план семи мостов Кёнигсберга, то увидим, что в каждой из его четырех вершин сходится нечетное число линий – и это говорит нам, что не существует маршрута по городу, проходящего по каждому из мостов только один раз. Эйлер пошел в своем анализе дальше. Если на карте имеется ровно две вершины с нечетным числом линий, такую карту можно нарисовать одним росчерком. Чтобы сделать это, нужно начать рисование с одной из точек с нечетным числом линий, а закончить его в другой вершине с нечетным числом линий.
Рис. 3.14. Теорема Эйлера утверждает, что эту карту можно нарисовать одним росчерком
Существует второй вид карт, который можно обойти по пути, называемому математиками наших дней Эйлеровым: такой, в каждой вершине которого сходится четное число линий. На подобной карте можно начать рисование в любой вершине, потому что путь должен начаться и закончиться в одной и той же вершине, чтобы получилась замкнутая петля. Хотя у вас и могут быть сложности с нахождением нужного пути, теорема Эйлера говорит вам, что, если карта принадлежит к одному из двух описанных мной типов, такой путь должен иметься. Такова сила математики: довольно часто она говорит вам о существовании чего-то, не прибегая к фактическому построению.
Чтобы доказать существование пути, воспользуемся классическим оружием из математического арсенала – индукцией. Она чем-то напоминает способ, посредством которого я борюсь со страхом высоты при подъеме на высокие лестницы или спуске по веревке с вершины водопада: делая раз за разом маленький шажок.
Начните с предположения, что вы умеете рисовать все карты с определенным числом ребер одним росчерком. А теперь представьте, что вам дана карта, у которой на одно ребро больше, чем было до того. Как можно понять, что вы по-прежнему сумеете нарисовать эту новую карту?
Давайте предположим, что у этой карты в двух вершинах сходится нечетное число ребер. Назовем эти вершины A и В. Трюк состоит в том, чтобы удалить одно из ребер, исходящих из вершин с нечетным числом ребер. Давайте удалим ребро, соединяющее B с другой вершиной С. На этой новой карте с одним удаленным ребром по-прежнему только две вершины, в которых сходится нечетное количество ребер: A и C. (Вершина B теперь характеризуется четным числом ребер, потому что мы только что удалили одну исходящую из нее линию; у вершины C теперь нечетное число, потому что мы удалили линию, соединяющую ее с В.) У этой новой карты достаточно малое число ребер, и мы можем ее нарисовать одним росчерком, начиная с вершины А и заканчивая в вершине С. Бо́льшую карту также нетрудно нарисовать: просто соедините С и В, добавив ребро, которое мы устранили ранее. Бинго!
Для полноты нам необходимо проанализировать еще несколько случаев. Например, что будет, если из B исходит только одна линия, которая соединяет ее с А, так что вершины А и С совпадают? Но мы можем видеть, что в основе доказательства существования Эйлерова пути лежит красивая идея продвижения шаг за шагом. Подобно тому как я методично поднимаюсь вверх по лестнице, я могу воспользоваться данным приемом для сколь угодно большой карты.
Чтобы увидеть мощь теоремы Эйлера, скажите вашему другу нарисовать настолько сложную карту, насколько он пожелает. Затем просто сосчитайте количество точек, где сходится нечетное число линий, и благодаря теореме Эйлера вы можете тут же сказать, удастся ли нарисовать эту карту одним росчерком.
Я недавно совершил паломничество в Кёнигсберг, который был переименован в Калининград после Второй мировой войны. Город неузнаваемо изменился со времен Эйлера – он был разрушен бомбардировками союзников. Однако три довоенных моста по-прежнему на месте: Деревянный мост (Holzbrücke), Медовый мост (Honigbrücke) и Высокий мост (Hohebrücke). Два моста исчезли полностью: Потроховой мост (Köttelbrücke) и Кузнечный мост (Schmiedebrücke). Оставшиеся мосты – Зеленый мост (Grünebrücke) и Лавочный мост (Krämerbrücke) – также были разрушены во время войны, но были перестроены и стали частью гигантской автострады с четырьмя полосами движения, проходящей через город.
Новый железнодорожный мост, по которому также могут ходить пешеходы, соединяет два берега Прегеля к западу от города. Также новый пешеходный Юбилейный мост, построенный на опорах разрушенного Императорского моста, позволил мне перейти реку подобно старому Высокому мосту. Я всегда думаю как математик и первым делом задался вопросом, можно ли совершить путешествие по сегодняшним мостам в духе игры XVIII в.
Рис. 3.15. Мосты Кёнигсберга XVIII в.
Рис. 3.16. Мосты Калининграда XXI в.
Математический анализ Эйлера подсказал мне, что если есть ровно два места, от которых отходит нечетное число мостов, то существует Эйлеров путь: вы начинаете движение в одном месте с нечетным числом и заканчиваете движение во втором. Посмотрев на план мостов сегодняшнего Калининграда, я обнаружил, что такой маршрут действительно возможен.
История мостов Кёнигсберга важна потому, что она дала математикам новый взгляд на геометрию и пространство. В этой новой перспективе важны не расстояния и углы, а то, как формы соединены друг с другом. Так зародилась топология, одна из наиболее влиятельных ветвей математики последнего столетия, которая рассматривалась в главе 2. Задача о мостах Кёнигсберга способствовала возникновению математики, лежащей в основе поисковых систем интернета вроде Google. Они стремятся как можно к более эффективной навигации по Сети. Задача о мостах также может быть полезна при планировании посещения станций лондонского метро, если у вас возникло искушение дать свой ответ на «Вызов подземки».
Как премьер-лига может принести вам «математический миллион»?
В середине сезона ваша команда томится в нижней половине турнирной таблицы, и вы хотите понять, остались ли у нее математические шансы стать чемпионом. Интересно, что математика, лежащая в основе попыток ответа на данный вопрос, напрямую связана с задачей на миллион долларов этой главы.
Чтобы разобраться, возможно ли это математически, вы начинаете с предположения, что ваша команда выиграет все оставшиеся матчи. Это даст ей три очка за каждую игру. Проблемы начинаются, когда вы пытаетесь проследить за необходимым распределением всех остальных очков в турнирной таблице. Вы желаете достаточного количества проигрышей командам, находящимся выше, чтобы ваша команда обошла их. Но не получится так, чтобы все проигрывали, ведь другие команды играют и между собой. Значит, вам необходимо найти правильный способ распределения очков в оставшихся матчах и надеяться, что одна из допустимых комбинаций выведет вас наверх таблицы. Наверняка должен быть более элегантный способ определить, существует ли такая выигрышная комбинация.
Вам необходимо найти хитроумный прием наподобие того, который использовал Эйлер для рисования карт, – он означал бы, что вам не требуется разбирать все возможные сценарии результатов предстоящих матчей. К несчастью, в настоящее время мы не знаем, существует ли такой прием. Миллион долларов получит первый человек, который либо найдет этот прием, либо докажет, что у этой задачи есть некоторая неотъемлемая сложность, из-за которой полный перебор является единственной возможностью решить задачу.
Любопытно, что до 1981 г. существовала эффективная программа, которой вы могли воспользоваться в середине сезона для проверки того, остается ли у вашей команды шанс выиграть премьер-лигу. До 1981 г. команде присуждались лишь два очка за победу, и эти же два очка делились между соперниками в случае ничьей. Это очень существенно с математической точки зрения, поскольку означает, что полное число очков, разыгранных в сезоне, фиксированно. Например, в лиге с 20 командами, такой как премьер-лига, каждая команда играет 38 матчей (один матч дома и один матч на выезде против каждой из остальных 19 команд). Итак, получается 20 × 38 матчей… за исключением того, что я учел каждый матч дважды. Ведь матч «Арсенала» против «Манчестер Юнайтед» – это также матч «Манчестер Юнайтед» против «Арсенала». Итак, в общей сложности получается 10 × 38 = 380 матчей. Система подсчета очков, применявшаяся до 1981 г., означала, что полное количество очков в конце сезона будет равняться 2 × 380 = 760, и эти очки будут распределены между 20 командами. Это обстоятельство было ключевым для эффективной программы, которой можно было воспользоваться в середине сезона, чтобы понять, остался ли у вашей команды шанс выиграть титул.