Искусство мыслить рационально. Шорткаты в математике и в жизни - [104]

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

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

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

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

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

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

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

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

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

Футбол. Наверное, мои самые любимые примеры задач, к которым мы не можем найти шорткаты, связаны с футболом. Не столько с самой игрой, сколько с теми восхитительными вопросами, которые начинают возникать ближе к концу сезона: существует ли еще математическая возможность победы моей команды в Премьер-лиге при ее нынешнем положении в турнирной таблице? Может показаться, что это очень простая задача. Нужно всего лишь предположить, что команда победит во всех матчах и получит за каждую победу по три очка, а затем проверить, хватит ли ей этого, чтобы занять первое место. Однако на самом деле беспокоиться нужно обо всех матчах между другими командами. Разумеется, хотелось бы, чтобы команда, занимающая сейчас верхнюю строчку таблицы, проиграла как можно больше матчей. Но это означает, что те команды, с которыми она будет играть, будут побеждать и зарабатывать очки. Что, если у них окажется слишком много очков и одна из них выйдет на первое место?