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

С судоку связаны несколько интересных математических вопросов. Один из них: сколькими различными способами можно расположить числа на сетке 9 × 9, чтобы удовлетворить правилам судоку? (Опять-таки под различными мы имеем в виду «существенно» различные: мы считаем два расположения одинаковыми, если одно из них переходит в другое вследствие простой симметрии, например перестановки строк.) Ответ был найден в 2006 г. Эдом Расселом и Фрэзером Джарвисом: 5 472 730 538. Этого вполне достаточно, чтобы газеты продолжали выходить еще какое-то время.

Однако другая математическая задача, связанная с этими головоломками, не была решена полностью. Какое минимальное количество чисел должно быть вначале нанесено на сетку, чтобы судоку решалось только одним способом? Понятно, что если этих чисел будет мало – скажем, 3, то головоломку можно будет решить многими способами, имеющейся вначале информации будет недостаточно для однозначного решения. Считается, что необходимо по крайней мере 17 чисел, чтобы судоку решалось только одним способом. Этот вопрос выходит за рамки головоломок, решаемых на досуге. У математики, лежащей в основе судоку, имеются важные следствия для кодов с коррекцией ошибок, с которыми мы познакомимся в следующей главе.

Как математика может вам помочь попасть в Книгу рекордов Гиннесса?

Имеется множество безумных способов попасть в Книгу рекордов Гиннесса. Итальянский бухгалтер Микеле Сантелиа оказался там, напечатав 64 книги на языке оригинала в обратном порядке (3 361 851 слово, 19 549 382 символа). Среди них были Одиссея, «Макбет», латинская Библия (Вульгата) и Книга рекордов Гиннесса за 2002 г. Кен Эдвардс из Глоссопа, графство Дербишир, является обладателем мирового рекорда по скорости поедания тараканов – 36 за одну минуту. А американцу Ашрите Фурману понадобилось 12 часов 27 минут, чтобы пропрыгать на пого-стике («кузнечике») рекордное расстояние 37,18 км. У него также рекорд по самому большому количеству рекордов! Но поможет ли математика в ваших попытках оказаться в зале славы Гиннесса?

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

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

Проблема была окончательно решена Леонардом Эйлером, швейцарским математиком, работавшим в Петербургской академии наук в 800 км к северо-востоку от Кёнигсберга (ранее обсуждалась его задача о греко-латинских квадратах). Эйлер совершил важнейший концептуальный скачок. Он понял, что фактические размеры города были совершенно не важны: значимо было то, как мосты соединялись друг с другом (тот же принцип применяется при составлении топологической карты лондонского метро). Каждый из четырех участков земли, соединяемых мостами Кёнигсберга, может быть сжат в точку, называемую вершиной. Мостам при этом соответствуют линии, соединяющие вершины. В результате получается карта мостов Кёнигсберга, несколько напоминающая значительно упрощенную карту лондонского метро (рис. 3.13).

Рис. 3.13

Задача о прохождении мостов сводится к тому, возможно ли начертить эту карту, не отрывая карандаша от бумаги и не проводя по одной и той же линии дважды (одним росчерком). Благодаря новой математической перспективе Эйлер сумел понять, что невозможно пройти по всем семи мостам, побывав на каждом из них только один раз.

Но почему же это невозможно? При рисовании карты каждая вершина, которую вы посетили в середине путешествия, должна иметь одну входящую и одну выходящую линию. Если вы оказываетесь в этой вершине снова, значит, вы пришли в нее по новому «мосту» и так же должны выйти из нее через новый «мост». Значит, в каждой вершине должно сходиться четное число линий, за исключением начала и конца путешествия.