Задача о четырех красках

История задачи о четырех красках уходит в XIX в. В 1850 г. шотландский физик Фредерик Гутри обнаружил, что лондонские студенты-математики увлекаются играми по раскрашиванию карт, а двумя годами позже его брат Фрэнсис Гутри раскрасил карту Англии в четыре цвета и предположил, что такого количества красок хватит, чтобы раскрасить любую карту. Но только в 1878 или 1879 г. математик Артур Кэли сформулировал следующую задачу: «Доказать, что любую географическую карту на плоскости (или на глобусе) можно правильно закрасить четырьмя красками». Правильной он назвал раскраску, когда любые две страны с общей границей окрашены в разные цвета. С этого времени многие крупные математики занялись данной проблемой.

Карта Европы, раскрашенная четырьмя красками

В 1890 г. английский математик Перси Хивуд доказал, что любую карту на плоскости можно раскрасить в пять цветов. Но проблема четырех красок решению не поддавалась. Сначала решения были частными. Так, в 1968 г. американские математики О. Оре и Г. Стемпл показали, что в четыре цвета можно раскрасить любую карту, на которой имеется не больше 40 стран.

Удовлетворительно доказать эту теорему (а это действительно теорема!) удалось американским ученым Кеннету Аппелю и Вольфгангу Хакелю. Они использовали один компьютер, с помощью которого просмотрели 1936 типов карт. Для каждого из них осуществлялась проверка, можно ли обнаружить в нем карту меньшего размера, которая не раскрашивается в четыре цвета правильно. Для всех случаев был получен ответ: «Нет». Это была первая крупная задача, решенная с помощью компьютера. Правда, далеко не все математики признали это решение. В 1997 и в 2005 гг. данная задача была решена другими способами, но также с помощью компьютеров.

Задачу о четырех красках удалось решить только с помощью компьютера

В математике количество цветов, необходимых для закрашивания карты, называется хроматическим числом. Для односторонних поверхностей, таких как лента Мёбиуса или бутылка Клейна (о них будет рассказано ниже), оно не равняется четырем.

Игра в четыре краски

Решение задачи о четырех красках может быть очень увлекательной игрой

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