Раскрашивание карты. Если взять любую географическую карту и попытаться раскрасить страны так, чтобы никакие две граничащие страны не были закрашены одним и тем же цветом, этого всегда можно добиться, используя четыре цвета. Но нельзя ли обойтись всего тремя? И в этом случае единственный имеющийся у нас алгоритм, позволяющий определить, хватит ли трех цветов для раскрашивания карты, сводится к перебору всех возможных вариантов ее раскрашивания. Как и при решении судоку, можно начать закрашивать страны, а потом обнаружить, что сделанный ранее выбор цветов приводит к тому, что две соседние страны приходится закрасить одним и тем же цветом. Если на карте изображены N стран, существует 3^N способов раскраски этих стран тремя цветами, что означает, что число возможных вариантов растет экспоненциально.

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

Вот, кстати, пример несерьезного применения шортката, в котором мы рассматриваем наименьший экземпляр чего-либо, чтобы доказать, что такой объект не может существовать: доказательство невозможности существования неинтересных чисел. Предположим, что неинтересные числа существуют. Пусть N – наименьшее неинтересное число. Но сам тот факт, что это наименьшее неинтересное число, делает его интересным.

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

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