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

Новый железнодорожный мост, по которому также могут ходить пешеходы, соединяет два берега Прегеля к западу от города. Также новый пешеходный Юбилейный мост, построенный на опорах разрушенного Императорского моста, позволил мне перейти реку подобно старому Высокому мосту. Я всегда думаю как математик и первым делом задался вопросом, можно ли совершить путешествие по сегодняшним мостам в духе игры XVIII в.

Рис. 3.15. Мосты Кёнигсберга XVIII в.

Рис. 3.16. Мосты Калининграда XXI в.

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

История мостов Кёнигсберга важна потому, что она дала математикам новый взгляд на геометрию и пространство. В этой новой перспективе важны не расстояния и углы, а то, как формы соединены друг с другом. Так зародилась топология, одна из наиболее влиятельных ветвей математики последнего столетия, которая рассматривалась в главе 2. Задача о мостах Кёнигсберга способствовала возникновению математики, лежащей в основе поисковых систем интернета вроде Google. Они стремятся как можно к более эффективной навигации по Сети. Задача о мостах также может быть полезна при планировании посещения станций лондонского метро, если у вас возникло искушение дать свой ответ на «Вызов подземки».

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

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

Вам необходимо найти хитроумный прием наподобие того, который использовал Эйлер для рисования карт, – он означал бы, что вам не требуется разбирать все возможные сценарии результатов предстоящих матчей. К несчастью, в настоящее время мы не знаем, существует ли такой прием. Миллион долларов получит первый человек, который либо найдет этот прием, либо докажет, что у этой задачи есть некоторая неотъемлемая сложность, из-за которой полный перебор является единственной возможностью решить задачу.

Любопытно, что до 1981 г. существовала эффективная программа, которой вы могли воспользоваться в середине сезона для проверки того, остается ли у вашей команды шанс выиграть премьер-лигу. До 1981 г. команде присуждались лишь два очка за победу, и эти же два очка делились между соперниками в случае ничьей. Это очень существенно с математической точки зрения, поскольку означает, что полное число очков, разыгранных в сезоне, фиксированно. Например, в лиге с 20 командами, такой как премьер-лига, каждая команда играет 38 матчей (один матч дома и один матч на выезде против каждой из остальных 19 команд). Итак, получается 20 × 38 матчей… за исключением того, что я учел каждый матч дважды. Ведь матч «Арсенала» против «Манчестер Юнайтед» – это также матч «Манчестер Юнайтед» против «Арсенала». Итак, в общей сложности получается 10 × 38 = 380 матчей. Система подсчета очков, применявшаяся до 1981 г., означала, что полное количество очков в конце сезона будет равняться 2 × 380 = 760, и эти очки будут распределены между 20 командами. Это обстоятельство было ключевым для эффективной программы, которой можно было воспользоваться в середине сезона, чтобы понять, остался ли у вашей команды шанс выиграть титул.

В 1981 г. все изменилось математически. Когда за победу даются три очка и в общей сложности два очка за ничью (по одному каждой из команд), нельзя сказать заранее, каким будет полное количество очков в конце сезона. Если каждый матч завершится вничью, то полное количество очков будет снова 760. Но если в каждом матче будет победитель, то полное количество очков будет 1140. Это изменение сделало задачу о премьер-лиге трудноразрешимой.

Имеется множество иных вариантов задачи о премьер-лиге, за которые можно взяться, если вы не футбольный болельщик. Классический вариант называется задачей коммивояжера. В качестве примера такой задачи разберитесь со следующим: вы коммивояжер, и вам необходимо посетить 10 клиентов, причем все они находятся в разных городах. Эти города соединены дорогами, как показано на приведенной карте, – но топлива у вас хватит лишь на 238 миль.

Рис. 3.17. Пример задачи коммивояжера. Можете ли вы найти маршрут протяженностью 238 миль или менее, который проходит через все точки на карте и возвращается в начальную точку?

Расстояние между городами задается числом на дороге, соединяющей их. Можете ли вы найти маршрут, позволяющий вам посетить всех 10 клиентов и затем вернуться домой на имеющемся топливе? (Решение приведено в конце главы.) В данной версии задачи миллион предлагается тому, кто найдет общий алгоритм или напишет компьютерную программу, которая выдаст кратчайший путь для любой задаваемой карты и будет при этом существенно быстрее перебора всех вариантов. Число возможных маршрутов экспоненциально растет с ростом числа городов, поэтому поиск методом полного перебора вскоре становится практически невозможен. Или же вы сумеете доказать, что такой быстрой программы не может быть?

Среди математиков преобладает мнение, что задачи этого вида имеют встроенную сложность, что означает отсутствие какого-то умного способа для поиска решения. Я обычно называю эти задачи иголкой в стоге сена, потому что, по существу, имеется много возможных решений, и вы стараетесь найти особенное из них. Техническое название для них – NP-полные задачи.

Как только вы нашли иголку, легко проверить, что она является требуемым результатом, – это одна из ключевых характеристик данных головоломок. Например, вы понимаете, что задача решена, как только вы нашли маршрут на карте, не превосходящий 238 миль. Подобным образом, если вы находите нужную комбинацию результатов на остаток футбольного сезона, вы мгновенно видите, что у вашей команды еще остается математическая возможность стать чемпионами. Задачами класса P в математике называют те, для которых существуют эффективные программы по поиску решения. Задача на миллион долларов может быть сформулирована так: являются ли NP-полные задачи в действительности задачами класса P? Математики говорят об этом как о соотношении классов P и NP.