В 1852 году Фрэнсис Гатри занимался раскраской карты Англии: он хотел, чтобы соседние графства были разного цвета. В процессе он обнаружил закономерность: трех красок для этой задачи мало, пяти хватает с избытком, а четырех, судя по всему, достаточно для любой карты. При этом объяснить, почему так происходит, не получалось. Именно это наблюдение положило начало математической задаче, над которой ученые бились 124 года.
Гатри учился у известного математика Августа де Моргана в Университетском колледже Лондона и через брата Фредерика передал ему свой вопрос. Де Морган оказался в тупике. 23 октября 1852 года он написал письмо ирландскому математику Уильяму Гамильтону. Задача звучала почти как школьная загадка — и это стало ее главной ловушкой. Она привлекала всех подряд, создавала иллюзию близкого решения и отвергала любую попытку одну за другой.
Принципиальное ограничение задачи было в понятии «соседства». Два региона считаются соседними, только если они делят общую границу. Регионы, касающиеся в одной точке, соседями не считаются — одной точки для этого недостаточно. Это означает, что карта не может быть устроена как шахматная доска — там у каждого квадрата по восемь соседей, здесь структура проще. Именно эта простота долгое время казалась поводом думать, что задача может быть решена в кратчайшие сроки.
Одиннадцать лет триумфа
В 1879 году лондонский адвокат и математик-любитель Альфред Кемп объявил, что задача решена. Его доказательство вышло в журнале Nature — одном из самых авторитетных научных изданий эпохи. Метод опирался на то, что позже назвали «цепочками Кемпа»: связные группы регионов одного и того же цвета, которые можно перекрашивать, не нарушая правила соседства. Коллеги сочли идею изящной и убедительной и математическое сообщество приняло работу: задача Гатри считалась закрытой.
Кемп стал членом Лондонского королевского общества, а в 1912 году получил рыцарское звание. Одиннадцать лет никто в мире не находил изъяна в его рассуждениях. На самом деле изъян был — и он ждал своего часа.
Брешь в чужом аргументе
В 1890 году молодой математик из Дарема Перси Хивуд тщательно разобрал доказательство Кемпа и нашел конкретное место, где аргумент разваливался. Для карт, в которых у одного из регионов оказывается пять соседей, метод цепочек перестает работать: два цикла перекраски могут накладываться и аннулировать друг друга. Кемп не смог закрыть эту брешь.
Хивуд опубликовал разбор и доказал более слабое утверждение: пяти цветов для любой карты всегда достаточно. Хватит ли четырех — по-прежнему никто не знал. Спор, казавшийся закрытым, возобновился, но откуда брать новый ответ — было неясно.
Восемьдесят шесть лет перебора
Следующие восемьдесят шесть лет задача оставалась нерешенной. Американский математик Джордж Биркгоф ввел понятие «редуцируемой конфигурации» — фрагмента карты, который можно упростить. Это был правильный подход: если доказать, что любая карта обязательно содержит хотя бы одну из таких конфигураций, а каждую конфигурацию можно упростить и перекрасить, задача будет решена. Проблема оставалась в масштабе. Конфигураций нужны были тысячи, и проверить каждую вручную было нереально.
В 1969 году немецкий математик Генрих Хееш развил метод дальше и ввел технику «разряжения» — способ распределять некий формальный заряд по карте так, чтобы вычислить проблемные области. Хееш оценил, что для полного доказательства нужно проверить около 8900 конфигураций, — а сделать это вручную за разумное время не мог ни один человек: задача переросла в чистый перебор.
1200 машинных часов
К 1976 году математики Кеннет Аппель и Вольфганг Хакен из Иллинойского университета собрали полный набор из 1482 «неизбежных конфигураций» — фрагментов, хотя бы один из которых присутствует в любой возможной карте. Это доказали математически. Затем каждую конфигурацию проверили отдельно: любую из них можно было свести к более простой карте и перекрасить четырьмя цветами без нарушений. Этот шаг выполнил компьютер. Машина работала 1200 часов.
Логика такова: раз каждая карта содержит хотя бы одну неизбежную конфигурацию, а каждую из них можно упростить без проблем с раскраской, четырех цветов всегда достаточно. Аппель и Хакен объявили о доказательстве 21 июня 1976 года. От первого вопроса Гатри прошло 124 года.
Доказательство, которое нельзя проверить вручную
Но праздновать победу было рано. Математики привыкли к доказательствам, которые коллега может проверить шаг за шагом. Здесь это было невозможно: ключевая часть аргумента существовала только в машинной памяти, и воспроизвести ее вручную означало заново потратить тысячи часов машинного времени — а не просто перечитать текст.
Критики задавали прямой вопрос: откуда уверенность, что в программе нет ошибки? Авторы отвечали встречным: а откуда уверенность в ручном доказательстве длиной в сотни страниц — там тоже могут быть ошибки. Теорема стала первым крупным математическим результатом, доказанным с помощью компьютера, и подняла вопрос, на который тогда не было четкого ответа: что вообще считать полноценным доказательством в математике.
В 1997 году независимая команда — Нил Робертсон, Дэниел Сандерс, Пол Сеймур и Робин Томас — построила более простую версию доказательства с 633 конфигурациями и открытым программным кодом, который мог проверить любой желающий. Сомнения до конца не развеялись, но теорема вошла в учебники как доказанная.
2026: еще одно доказательство
В марте 2026 года группа математиков — датчане Миккель Труп и Карстен Томассен, японец Кен-ити Каварабайаши и канадец Бойян Мохар — опубликовала новое доказательство. Оно проверяет 8202 конфигурации — в тринадцать раз больше, чем версия 1997 года, — зато дает принципиально более быстрый алгоритм раскраски карт.
Предыдущий метод требовал число шагов, пропорциональное квадрату числа регионов: для карты из миллиона областей это примерно миллион операций на каждую область. Новый алгоритм справляется за число шагов, пропорциональное миллиону, умноженному на логарифм миллиона, — примерно в 50 000 раз меньше при том же масштабе карты.
Практическое применение у задачи Гатри есть: те же алгоритмы раскраски работают в задачах планирования частот радиосвязи, составления расписаний и распределения ресурсов процессора. Но главное значение теоремы — в другом. 124 года она показывала, что «очевидно» и «доказано» — не одно и то же. Студент Гатри был прав, когда задал свой вопрос в 1852 году. Между его наблюдением и доказательством пролегло столетие работы, один ложный триумф и первый в истории математики компьютерный аргумент.
Источник новости: hi-tech.mail.ru
