Тайны чисел. Математическая одиссея - Маркус Дю Сотой

Одним из соревнований, за которым Книга рекордов следит с 1961 г., является посещение всех станций лондонского метро за самое короткое время. Оно называется «Вызовом подземки» (Tube Challenge), и рекорд на конец 2009 г. составлял 6 часов 44 минуты 16 секунд. Он был установлен Мартином Хэзелом, Стивом Уилсоном и Энди Джеймсом 14 декабря того же года. Кто-то может сказать, что это мучительная гонка, но если вы хотите попытаться побить их рекорд, то математический анализ карты метро может дать вам преимущество в нахождении самого короткого маршрута, гарантированно включающего все станции метро хотя бы один раз.

«Вызов подземки» не является первым в своем роде. Он представляет более сложный вариант игры, популярной в прусском городе Кёнигсберг в 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) – также были разрушены во время войны, но были перестроены и стали частью гигантской автострады с четырьмя полосами движения, проходящей через город.