Журнал удивительных идей


Совместный проект учителей и учеников 192 школы










Раскрасим тор

Оказывается, что для тора

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

А сможете придумать такую карту, которую нельзя покрасить даже в пять цветов. А в шесть?

Листая старые страницы

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

А ещё я всё хочу поделиться с Вами решением задачи о 5 красках, которое я получил, действуя алгоритмически, и мне даже в конце не потребовалось ничего перекрашивать - всё сошлось сразу, плюс решение получилось довольно-таки симметричным. Я попытался красить карту тремя цветами: красным, зелёным и синим, пока это будет возможно (начал с правой верхней страны, потом покрасил всю верхнюю часть, потом двигался сверху вниз). В итоге получилось, что пробелов осталось немного, и я их легко покрасил жёлтым. Вот, что получилось:

Быть может, это ещё и решение, в котором один из цветов использован по минимуму.

А что, интересная задача. Сможете ли вы раскрасить "ту самую карту", используя какой-нибудь цвет меньше девяти раз?

Понимая, что многие захотят для решения этой и других задач, связанных с той самой картой, использовать компьютер мы предлагаем скачать карту в текстовом формате (1 - черный пиксель, 0 - белый).

Мы пронумеровали области.

И для такой нумерации подготовили файл с данными о карте с координатами точек внутри каждой области, а также матрицей смежности и списком ребер графа (если представить области как вершины графа, а общие границы ребрами).

Оказалось, что матрица смежности (таблица, в которой 1 - есть ребро между вершинами и 0, если нет) выглядит удивительно! В уменьшенном виде получается такой рисунок (для контрастности единицы заменены на пробелы):

Диагонали легко объяснить - это смежные зоны с близкими номерами, но вот откуда четыре параболы?

Редакция

М
а
т
е
м
а
т
и
к
а
Ф
и
з
и
к
а
Х
и
м
и
я
Б
и
о
л
о
г
и
я
И
н
ф
о
р
м
а
т
и
к
а