Тайны чисел: Математическая одиссея

История мостов Кёнигсберга важна потому, что она дала математикам новый взгляд на геометрию и пространство. В этой новой перспективе важны не расстояния и углы, а то, как формы соединены друг с другом. Так зародилась топология, одна из наиболее влиятельных ветвей математики последнего столетия, которая рассматривалась в главе 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 миль или менее, который проходит через все точки на карте и возвращается в начальную точку?