Немногие математические теоремы когда-либо освещались и публиковались для широкой (то есть неакадемической) публики. Иногда потому, что математика скучна и неинтересна для многих людей, но, главным образом, потому, что многие из этих теорем очень запутаны и излишне трудны для понимания. Баланс между простотой и интересностью редко встречается в общем учебнике нерешенных математических задач, однако тема этой статьи является одним из немногих редких исключений, которые действительно соблюдают этот баланс.
Теорема о четырёх красках в ее простейшей форме гласит, что для раскрашивания областей любой карты требуется не более четырех цветов, чтобы никакие две смежные области не имели одинакового цвета. Как и было обещано, эту теорему может понять любой ученик начальной школы. При этом области могут быть как односвязными и многосвязными (в них также могут быть «пробелы»), а под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке не считаются общей границей для них. Задача раскраски карты на плоскости эквивалентна задаче на сфере.
Эта теорема была сформулирована Фрэнсисом Гатри в 1852 году, однако доказать её долгое время не удавалось. За дело взялся его младший брат Фредерик Гатри, ученик знаменитого математика Августа Де Моргана, когда Фрэнсис поделился с Фредериком своими первоначальными наблюдениями, а также своими бесплодными попытками. Августа также заинтересовала данная теорема, однако Де Морган не смог дать ответ, поскольку он сразу же попался на крючок. Так эта проблема обрела популярность. И лишь после ее точной формулировки другим английским математиком Артуром Кэли, 1878 год стал считаться годом рождения проблемы четырёх красок. Её доказательство длилось более 100 лет. Ее неприступность объяснялась тем, что с ростом числа рассматриваемых стран на карте стремительно росло число вариантов их раскраски, что затрудняло проверку правильности решения. И только в 1976 году Кеннет Аппель и Вольфганг Хакен из Иллинойского университета смогли доказать гипотезу с помощью компьютеров.
Первым шагом доказательства была демонстрация того, что существует определённый набор из 1936 карт, ни одна из которых не может содержать карту меньшего размера, которая опровергала бы теорему. Авторы использовали специальную компьютерную программу, чтобы доказать это свойство для каждой из 1936 карт. Доказательство этого факта заняло сотни страниц. После этого Аппель и Хакен пришли к выводу, что не существует наименьшего контр-примера к теореме, потому что иначе он должен бы содержать какую-нибудь из этих 1936 карт, чего нет. Это противоречие говорит о том, что контр-примера нет вообще.
Задача о четырёх красках стала первой задачей, в доказательстве которой применили неклассическое доказательство (было рассмотрено 1936 карт, 400 страниц вычислений). В честь такого события, Почтой США была выпущена Марка с фразой "Четырёх цветов достаточно".
И так как классического её доказательства до сих пор ещё нет (доказано пока для 41 страны), то проблема четырех красок попала в число семи математических задач тысячелетия, за решение которых Институт Клэя предлагает приз в 1 млн долларов.
Статья подошла к концу, спасибо вам за прочтение! Хотите углубиться в математику? Наш сайт вам в помощь!