Эта интересная топологическая задача о раскраске привлекает внимание логиков всего мира с начала семидесятых годов прошлого века. Известная как “теорема о раскраске карты в восемьсот цветов”, она звучит так: “Можно ли разбить карту Европы на государства и раскрасить их в восемьсот цветов так, чтобы каждое государство было покрашено в свой цвет и никакие два соседние государства не были покрашены в один цвет?”
Математики, которых интересует эта проблема, считают, что ответ на данный вопрос утвердительный, но они не уверены в этом. Вследствие чрезвычайной сложности формализации данной задачи, они начали проводить эксперименты. Несмотря на это, трудная задача нахождения красок или фломастеров, имеющих восемьсот различных цветовых оттенков, добавила проблеме остроты.
В 1974 г. Мартин Рендраг, коллега профессора Николя Бурбаки, предложил блестящий метод нумерации цветов, который позволил переформлировать проблему, так что получилось нечто вроде этого: “Можно ли разбить карту Европы на государства и перенумеровать их числами от единицы до восьмисот так, чтобы каждое государство имело свой номер и никакие два соседние государства не имели одинаковых номеров?” Эта новая формулировка не дает ничего нового, она только позволяет оттянуть время начала раскрашивания карты, следовательно, она не устраняет трудности подбора цветов. Однако она может служить прекрасной отправной точкой для поиска рационального ответа на вопрос.
Тем не менее, ни одному математику не удавалось решить проблему с помощью карандаша и бумаги до тех пор, пока в 1979 г. команда, возглавляемая доктором Гёте из МТИ, не получила частичное решение, основанное на переформулировке Рендрага: программируя машину отеля Touring Club Конечных Штатов, доктор Гёте разделил карту Европы на восемьсот государств так, чтобы выполнялись логические ограничения задачи. Для получения данного результата необходимо было посчитать независимыми государствами все французские регионы, швейцарские кантоны, итальянские провинции, включая Изернии и Ористано, а также некоторые испанские области, такие как Ла-Манча и Пенедес, а также Фарерские острова, Кабреру и Лампедузу. Читать полностью ‘Задача о восьмистах красках’ »