Это база: Зачем нужна математика в повседневной жизни - Йэн Стюарт Страница 21

Легенда гласит, что граждан Кёнигсберга давно интересовал вопрос, можно ли совершить пешую прогулку по городу, пройдя по каждому из мостов ровно один раз. Это была простенькая головоломка из разряда тех, что можно увидеть на странице газеты или ее электронного эквивалента. Эксперименты с различными маршрутами не помогают ее решить – попробуйте сами. Однако аналогичные задачи имеют решение, причем иногда найти их непросто. Более того, число маршрутов, которые вы можете выбрать, бесконечно, хотя бы потому, что существует бесконечно много способов переходить с одной стороны улицы на другую или двигаться вперед и назад. Именно поэтому невозможно найти решение или доказать, что такового не существует, путем рассмотрения всех возможных маршрутов.

Можно, конечно, решить эту головоломку, придумав какую-нибудь хитрость. Например, зайти на мост, прогуляться по нему до противоположного берега и, не сходя на берег, развернуться и пойти назад, сказав при этом, что «прошел» по мосту. Но условие «прохождения» по мосту должно быть таким, чтобы исключать подобные фокусы. Аналогично «пешая прогулка» подразумевает, что нельзя проделать часть пути вплавь, на лодке, на воздушном шаре или принадлежащей доктору Кто машине TARDIS. Или пройти вверх по реке до какого-нибудь моста, который не вошел в схему Эйлера. Хотя «стряпать» головоломки таким образом может быть интересно и даже требовать немалой изобретательности, понятно, что это все же жульничество. Я не собираюсь тщательно формулировать все до единого условия, необходимые, чтобы исключить стряпню подобного рода. Меня гораздо больше интересует, как, переведя эту головоломку на язык математики, доказать невозможность отыскания ее решения, не прибегая к стряпне. Стряпня здесь заключается в формулировании этой задачи, а не в ее решении или доказательстве невозможности найти решение, если она уже сформулирована.

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

Эйлер переехал в Россию, в Санкт-Петербург, в 1727 году, когда в России правила императрица Екатерина I, чтобы стать придворным математиком. Муж Екатерины император Петр I основал Санкт-Петербургскую академию (Academia Scientiarum Imperialis Petropolitinae) в 1724–1725 годах, но умер прежде, чем она успела полностью сформироваться и заработать. Эйлер представил свою работу в Академии в 1735 году, и через год она была опубликована. Будучи математиком, причем, по мнению многих, самым плодовитым в истории, Эйлер извлек из головоломки так много, как только смог: он нашел необходимые и достаточные условия для существования решения, не только для кёнигсбергских мостов, но и для любой задачи подобного рода. Вы можете взять 50 000 мостов, связывающих друг с другом 40 000 островов гигантского комплекса, и теорема Эйлера без проблем скажет вам, существует ли для них решение. Если как следует вникнуть в доказательство, оно даже скажет, как это решение найти, – правда, после некоторой возни. Свое доказательство Эйлер изложил довольно схематично, и прошло почти 150 лет, прежде чем кто-то разобрался во всех его деталях, хотя само по себе доказательство не было слишком сложным.

В настоящее время многие книги по теории графов говорят о том, что Эйлер доказал отсутствие у головоломки решения, сведя ее к более простому вопросу о графах. Граф в этом смысле – это множество точек (называемых вершинами), соединенных линиями (их называют ребрами), и все это вместе образует своего рода сеть{34}. Переформулирование с использованием графов превращает головоломку кёнигсбергских мостов в задачу нахождения пути на конкретном графе, в котором каждое ребро используется ровно один раз. Именно так мы решаем эту задачу сегодня, но Эйлер делал не совсем так. В истории это случается часто. Историки математики с удовольствием рассказывают о том, как все происходило на самом деле, в отличие от общепринятого варианта. В реальности Эйлер решил задачу символически{35}.

Он обозначил каждый участок суши (остров или берег реки) и каждый мост буквой. Суше достались заглавные буквы A, B, C, D, а мостам – строчные a, b, c, d, e, f, g. Каждый мост соединяет друг с другом два участка суши, например, мост f соединяет A и D. Прогулка начинается в некоторой области и может быть описана последовательным перечислением преодоленных участков и мостов до последнего участка суши. В большей части статьи Эйлер описывает маршруты словесно и в основном работает с последовательностью участков суши. Не имеет значения, по какому мосту вы перейдете с A на B, если число сочетаний AB будет равно числу таких мостов. Или можно, наоборот, использовать последовательность мостов – достаточно обозначить точку начала и подсчитать, сколько раз вы посетите заданный участок. Не исключено, что так было бы проще. Ближе к концу статьи Эйлер использует те и другие символы и приводит пример последовательности

EaFbBcFdAeFfCgAhCiDkAmEnApBoElD,

соответствующий более сложной схеме{36}.

В такой формулировке конкретный путь, по которому идет пешеход на каждом участке или по каждому мосту, не имеет значения. Единственное, за чем нужно следить, – это последовательность, в которой посещаются участки и проходятся мосты. Проход по мосту подразумевает, что «две заглавные буквы с обеих его сторон различны». Это исключает возможность зайти на мост и возвратиться на ту же сторону. Решение – последовательность чередующихся заглавных и строчных букв A–D и a–g, в которой каждая строчная буква появляется ровно один раз, а заглавные буквы до и после любой заданной строчной соответствуют тем двум участкам берега, которые связаны данным мостом.

Мы можем составить список связей для каждой строчной буквы:

Допустим, мы начинаем с участка B. Три моста связывают B с другими участками: a, b и f. Предположим, мы выбираем f, тогда наша последовательность начинается с Bf. На другом конце моста f находится участок D, так что мы получаем Bf