Задача о четырех красках
История задачи о четырех красках уходит в XIX век. В 1852 году Фрэнсис Гатри, раскрашивая карту графств Англии, заметил, что ему хватает четырёх цветов, чтобы соседние области не имели одинаковой окраски. Он сообщил о вопросе своему брату Фредерику, а тот передал его математику Огастесу де Моргану. В 1878 году Артур Кэли публично сформулировал проблему для математического сообщества: доказать, что любую карту на плоскости или сфере можно правильно раскрасить четырьмя цветами.
Карта Европы, раскрашенная четырьмя красками
В 1890 г. английский математик Перси Хивуд доказал, что любую карту на плоскости можно раскрасить в пять цветов. Но проблема четырех красок решению не поддавалась. Сначала решения были частными. Так, в 1968 г. американские математики О. Оре и Г. Стемпл показали, что в четыре цвета можно раскрасить любую карту, на которой имеется не больше 40 стран.
Удовлетворительно доказать эту теорему (а это действительно теорема!) удалось американским ученым Кеннету Аппелю и Вольфгангу Хакену. Они использовали один компьютер, с помощью которого просмотрели 1936 типов карт. Для каждого из них осуществлялась проверка, можно ли обнаружить в нем карту меньшего размера, которая не раскрашивается в четыре цвета правильно. Для всех случаев был получен ответ: «Нет». Это была первая крупная задача, решенная с помощью компьютера. Необычная роль компьютера сначала вызвала споры о характере такого доказательства. В 1997 году Нил Робертсон, Дэниел Сандерс, Пол Сеймур и Робин Томас опубликовали более простое компьютерное доказательство; позднее теорема была также формально проверена средствами компьютерной проверки доказательств.
Задачу о четырех красках удалось решить только с помощью компьютера
В математике количество цветов, необходимых для закрашивания карты, называется хроматическим числом. Для односторонних поверхностей, таких как лента Мёбиуса или бутылка Клейна (о них будет рассказано ниже), оно не равняется четырем.
Игра в четыре краски
Решение задачи о четырех красках может быть очень увлекательной игрой
Популяризатор науки Стивен Барр придумал логическую игру для двух человек, которая называется «Четыре краски». Берутся четыре цветных карандаша и чистый лист бумаги. Первый игрок рисует пустую область и передает ход сопернику. Тот закрашивает ее, используя один из четырех карандашей, и рисует вторую пустую область. Первый игрок закрашивает область соперника и рисует свою. Так и продолжается игра. Тот, кто вынужден будет во время своего хода взять пятый карандаш, проигрывает. Проигрыш вовсе не означает, что теорема не верна, он лишь показывает, как трудно было ее доказать.