Раскрашивание карты. Если взять любую географическую карту и попытаться раскрасить страны так, чтобы никакие две граничащие страны не были закрашены одним и тем же цветом, этого всегда можно добиться, используя четыре цвета. Но нельзя ли обойтись всего тремя? И в этом случае единственный имеющийся у нас алгоритм, позволяющий определить, хватит ли трех цветов для раскрашивания карты, сводится к перебору всех возможных вариантов ее раскрашивания. Как и при решении судоку, можно начать закрашивать страны, а потом обнаружить, что сделанный ранее выбор цветов приводит к тому, что две соседние страны приходится закрасить одним и тем же цветом. Если на карте изображены
Тот факт, что для этого требуется не более четырех цветов, был предметом одной из величайших теорем, доказанных в XX веке. Еще в 1890 году теорема была доказана для пяти цветов. Это доказательство было не слишком сложным: оно было основано на шорткате, часто используемом математиками. Предположим, что существуют карты, которые невозможно раскрасить пятью цветами. Возьмем такую карту с наименьшим числом стран. Тогда при помощи некоторых хитроумных выкладок можно показать, что одна страна может быть удалена так, что и оставшуюся карту нельзя будет раскрасить пятью цветами. Но это противоречит исходному утверждению, что изначальная карта содержала наименьшее возможное количество стран.
Вот, кстати, пример несерьезного применения шортката, в котором мы рассматриваем наименьший экземпляр чего-либо, чтобы доказать, что такой объект не может существовать: доказательство невозможности существования неинтересных чисел. Предположим, что неинтересные числа существуют. Пусть
Досаднее всего было то обстоятельство, что этот изящный шорткат, по-видимому, не помогал доказать, что для раскрашивания карты достаточно четырех цветов. Математики не могли продемонстрировать, что после удаления с карты одной страны ее по-прежнему невозможно раскрасить. Но никто не мог предложить и примера, доказывающего обратное.
В конце концов доказательство теоремы о четырех цветах было найдено в 1976 году. Однако это доказательство уж точно не могло считаться шорткатом. Тысячи вариантов, перебрать которые человеку было бы не по силам, проверили методом грубой силы на компьютере. Это доказательство стало поворотной точкой в истории математики: путь к решению впервые был проложен с использованием вычислительной мощности компьютеров. Это было похоже на ситуацию, в которой мы оказались бы перед горным хребтом и не смогли найти пути, ведущего в долину, которая лежит за ним. Тогда мы просто взяли машину и пробурили гору насквозь.
Многие представители математического сообщества испытывали смешанные чувства по отношению к такому использованию компьютера для доказательства этой теоремы. Предполагалось, что доказательство должно позволить человеку понять, почему именно четырех цветов достаточно, а не просто установить, так ли это. Число связей, которые могут образоваться в мозге человека, ограниченно; именно поэтому мозгу так важно ощущать, что он понимает, почему тот или иной шорткат именно таков. Если доказывать приходится долгим, кружным путем, получается, что оно не может быть загружено в мозг, и у нас остается ощущение, что нам так и не дали по-настоящему понять его.
Родственная раскрашиванию карты задача связана с сетью, состоящей из точек, некоторые из которых соединены линиями. Линии подобны границам между странами. В задаче спрашивается, каково минимальное количество цветов, необходимое для раскрашивания точек, при котором никакие две точки, соединенные линией, не оказались бы одного и того же цвета.
Футбол. Наверное, мои самые любимые примеры задач, к которым мы не можем найти шорткаты, связаны с футболом. Не столько с самой игрой, сколько с теми восхитительными вопросами, которые начинают возникать ближе к концу сезона: существует ли еще математическая возможность победы моей команды в Премьер-лиге при ее нынешнем положении в турнирной таблице? Может показаться, что это очень простая задача. Нужно всего лишь предположить, что команда победит во всех матчах и получит за каждую победу по три очка, а затем проверить, хватит ли ей этого, чтобы занять первое место. Однако на самом деле беспокоиться нужно обо всех матчах между другими командами. Разумеется, хотелось бы, чтобы команда, занимающая сейчас верхнюю строчку таблицы, проиграла как можно больше матчей. Но это означает, что те команды, с которыми она будет играть, будут побеждать и зарабатывать очки. Что, если у них окажется слишком много очков и одна из них выйдет на первое место?
Получается еще одна задача, в которой необходимо учитывать множество разных комбинаций матчей и их результатов. Приписывая командам победы, поражения и ничьи, я снова и снова бываю вынужден возвращаться назад, как в судоку, потому что оказывается, что один из результатов, которые я приписал раньше, разрушает все с таким трудом выстроенное равновесие.
Если всего в турнире осталось сыграть
Но эта задача так нравится мне потому, что, когда я был школьником, такой алгоритм существовал. Что же случилось с тех пор? Нет, дело не в том, что мы утратили этот алгоритм, а в том, что изменились правила начисления очков. Раньше команды получали за победу всего лишь по два очка, а в случае ничьей – по одному каждая. Потом решили, что это побуждает футболистов сводить матчи к скучным ничьим. Поэтому в 1981 году было принято решение усилить привлекательность побед для команд. Вместо двух очков победившая в матче команда стала получать три. Это, казалось бы, безобидное новшество резко изменило ситуацию с точки зрения задачи о возможности выхода той или иной команды на верхнюю строчку турнирной таблицы Премьер-лиги.
Важнее всего то обстоятельство, что до 1981 года суммарное число очков, распределяющееся между командами, не зависело от того, кто выигрывает, проигрывает или заканчивает матч вничью. В турнире участвуют 20 команд; каждая из них встречается со всеми остальными по два раза, на своем поле и на выезде, то есть всего получается 20 × 19 матчей. В старой системе в каждом матче разыгрывались два очка, которые распределялись в зависимости от его исхода. Стало быть, суммарное число очков, распределенных между 20 командами к концу сезона, было равно 2 × 20 × 19 = 760.
Но теперь все совсем иначе. В каждом матче могут быть присуждены либо три очка – их получает победитель, – либо два, которые делят между собой команды, сыгравшие вничью. Если все матчи сезона будут сыграны вничью, сумма очков по-прежнему будет равна 760. Но, если не будет ни одной ничьей, сумма составит 3 × 20 × 19 = 1140 очков. Появление этих вариаций суммарного количества очков привело к тому, что действовавший до этого алгоритм, который позволял мне понять, остаются ли у моей команды математические шансы на победу в лиге, перестал работать.
Все эти задачи замечательны тем, что, если удается найти какое-нибудь решение, можно быстро проверить, действительно ли оно подходит к задаче. Я называю их «задачами об иголке в стоге сена»: сначала нужно проделать долгую, изнурительную работу, чтобы понять, где именно находится иголка, но как только вы ее нащупаете, не останется никаких сомнений, что вы ее нашли! Взломщик может долго возиться с сейфом, пробуя одну комбинацию за другой, но, как только комбинация окажется правильной, дверь тут же откроется.
У задач об иголке в стоге сена, или, если использовать их официальное название, NP-полных задач, есть одно довольно необычное свойство. Может показаться, что каждая из них требует своей, индивидуальной стратегии поисков алгоритма, который позволит решать ее за кратчайшее возможное время. Однако, если будет открыт алгоритм полиномиального времени, находящий кратчайший маршрут по любой карте, с которой может столкнуться пресловутый коммивояжер, это будет означать, что такие алгоритмы гарантированно существуют и для всех остальных таких задач. Хотя бы это дает шорткат к решению задачи поиска шорткатов. Если обнаружится, что существует шорткат к решению какой-нибудь из задач нашего списка, его можно будет преобразовать в шорткат к решению любой другой. Толкин сказал бы, что это один шорткат, чтоб все решить.
Я могу дать вам подсказку, которая показывает, почему это так: посмотрите, как некоторые из задач, которые я описал, можно преобразовывать друг в друга. Возьмем, например, задачу о расписании уроков. Там есть уроки, временные отрезки и накладки, которых необходимо избегать. Используя эту информацию, можно построить сеть, в которой каждый урок будет обозначен точкой, а накладки – линиями, каждая из которых соединяет два урока, между которыми возникает противоречие. Тогда распределение уроков по временным отрезкам превратится в задачу, точно совпадающую с задачей о раскрашивании точек графа таким образом, чтобы никакая линия не соединяла две точки одного и того же цвета.
Использование отсутствия шорткатов
Бывают такие ситуации, в которых важно, чтобы никаких шорткатов не было. Например, разработка нераскрываемых шифров. Разработчикам шифров выгодно такое положение вещей, когда взломать зашифрованное сообщение бывает, по-видимому, невозможно без полного перебора всех возможных вариантов. Взять, к примеру, кодовый замок. Если у него есть четыре колесика, на каждом из которых по десять цифр, то, чтобы его открыть, нужно перебрать 10 000 разных чисел, от 0000 до 9999. Некачественно изготовленные замки иногда выдают то положение, в котором замок открывается, потому что при установке правильной цифры в механизме замка происходит физический сдвиг, но в общем случае у взломщика нет никакого шортката, кроме перебора всех комбинаций.
Однако в других шифровальных системах обнаруживаются слабые места, которые можно использовать для создания шорткатов. Вот, например, классический «шифр Цезаря», он же шифр подстановки. Это код, в котором одни буквы алфавита систематически заменяют на другие. Например, каждая встречающаяся в сообщении буква
Если хакер перехватит закодированное сообщение, ему придется перебрать огромное количество разных комбинаций, чтобы его расшифровать. Но у этого шифра есть слабое место, которое обнаружил живший в IX веке ученый-энциклопедист Якуб аль-Кинди: некоторые буквы встречаются в текстах чаще, чем другие. Например, в любом тексте на английском языке чаще всего – в 13 процентах случаев – встречается буква