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

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

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

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

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

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

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

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

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

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




Поделиться ссылкой