Распечатать запись Распечатать запись

Задача о восьмистах красках

Эта интересная топологическая задача о раскраске привлекает внимание логиков всего мира с начала семидесятых годов прошлого века. Известная как “теорема о раскраске карты в восемьсот цветов”, она звучит так: “Можно ли разбить карту Европы на государства и раскрасить их в восемьсот цветов так, чтобы каждое государство было покрашено в свой цвет и никакие два соседние государства не были покрашены в один цвет?”

Математики, которых интересует эта проблема, считают, что ответ на данный вопрос утвердительный, но они не уверены в этом. Вследствие чрезвычайной сложности формализации данной задачи, они начали проводить эксперименты. Несмотря на это, трудная задача нахождения красок или фломастеров, имеющих восемьсот различных цветовых оттенков, добавила проблеме остроты.

В 1974 г. Мартин Рендраг, коллега профессора Николя Бурбаки, предложил блестящий метод нумерации цветов, который позволил переформлировать проблему, так что получилось нечто вроде этого: “Можно ли разбить карту Европы на государства и перенумеровать их числами от единицы до восьмисот так, чтобы каждое государство имело свой номер и никакие два соседние государства не имели одинаковых номеров?” Эта новая формулировка не дает ничего нового, она только позволяет оттянуть время начала раскрашивания карты, следовательно, она не устраняет трудности подбора цветов. Однако она может служить прекрасной отправной точкой для поиска рационального ответа на вопрос.

Тем не менее, ни одному математику не удавалось решить проблему с помощью карандаша и бумаги до тех пор, пока в 1979 г. команда, возглавляемая доктором Гёте из МТИ, не получила частичное решение, основанное на переформулировке Рендрага: программируя машину отеля Touring Club Конечных Штатов, доктор Гёте разделил карту Европы на восемьсот государств так, чтобы выполнялись логические ограничения задачи. Для получения данного результата необходимо было посчитать независимыми государствами все французские регионы, швейцарские кантоны, итальянские провинции, включая Изернии и Ористано, а также некоторые испанские области, такие как Ла-Манча и Пенедес, а также Фарерские острова, Кабреру и Лампедузу.

На данный момент задача, значительно упрощенная, состоит в том, чтобы сопоставить каждому номеру один и только один цвет. Практические трудности очевидны: после нумерации десятка цветов возникают проблемы наименования, определения и сравнения цветов.

После попытки рационального строго натуралистического решения данной проблемы, основанного на различиях в оттенках лимонно-желтого, рыжевато-желтого, цыплячье-желтого, цвета зеленого горошка, зеленого цвета надежды, бутылочно-зеленого, изумрудно-зеленого, цвета зеленой ящерицы, табачно-зеленого, цвета белого единорога и т.д., необходимо было признать провал эксперимента. Было на самом установлено, что лимоны отличаются интенсивностью цвета, их цвет меняется в зависимости от множества факторов, зачастую непредсказуемых: погоды, широты, высоты над уровнем моря, атмосферного давления, степени зрелости, состояния хранения, использования консервантов и многого другого. И то же самое относится к цыплятам, не говоря уже о горошке, ящерицах и табаке.

Если к тому же принять в расчет, что некоторые сицилианские лимоны имеют те же оттенки цвета, что и португальские цыплята, то немедленно убедимся, что натуралистическому методу нумерации цветов доверять нельзя.

Кроме того, необходимо учитывать, что карта не может быть доступна дальтоникам, а также некоторым родам и видам животных, имеющим особым образом устроенные органы зрения, а именно ослам, мулам и другим непарнокопытным.

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

Кроме того, в этом случае целесообразно проводить эмпирические доказательства, учитывая сложность сравнения друг с другом восьмисот чисел. На сегодняшний день не получено полного и исчерпывающего доказательства теоремы о восьмистах красках. К сожалению, вопрос о ее доказательстве остается открытым.

Источник: http://www.divulgamat.net/index.php?option=com_content&view=article&id=17332&Itemid=400016

Один комментарий

  1. 1 Александр:

    Вот это головоломка. Раньше смотрел себе на карту спокойно и не думал о красках, а сейчас, пожалуй, буду разглядывать глобус дольше обычного. Вдруг решение в голову придет?

    [Ответить]

Оставьте свой отзыв

Добавить изображение