Раскраска карт: теорема о четырёх красках

Лаборатория для начальной школы (8-12 лет), очень наглядная: всё делается раскрашиванием клеток, треугольников, ячеек сот, чисел и стран одним нажатием. В каждом зале есть правило раскраски, и нужно его выполнить, посчитать, сколькими способами это можно сделать, или решить, можно ли вообще.

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

Чему учатся

• Узнавать соседей на клетчатой доске, в треугольнике из треугольничков и в сотах; отличать «общую сторону» от «касания в точке».
• Выполнять правила про соседей (разные цвета, «три и одна», «оранжевые не касаются друг друга») и видеть, что у правила может быть много решений, два или одно.
• Считать по порядку (спрятанные квадраты доски 4 × 4: 9 квадратов 2 × 2 и 4 квадрата 3 × 3).
• Искать максимум и обосновывать его: при 12 цветах и двух одинаковых клетках в каждом квадрате 2 × 2 максимум — 11, и есть причина, почему больше нельзя.
• Выводить вынужденные цвета (цветные числа: произведение двух разных цветов получает третий) и замечать противоречие, которое доказывает, что у задачи нет решения.
• Раскрашивать карты малым числом цветов; понимать, почему иногда хватает 2 или 3, а иногда нужны 4 (цветок из 5 лепестков), и узнать о теореме о четырёх красках.
• Использовать шахматную раскраску как инструмент: жуки на доске 5 × 5 (13 против 12) и прогулки по всем клеткам, которые не могут начаться или закончиться там, где просят.

Ключевые математические идеи по блокам

A · Соседние клетки. С двумя цветами и правилом «соседи разного цвета» раскрасок всего две: шахматная и обратная к ней (в треугольнике — смотрящие вверх одного цвета, вниз — другого). У клетки на краю или в углу соседей меньше, и это решает многие правила: в «оранжевая с 3 синими соседями, синяя с 1 оранжевым» ни одна оранжевая не может стоять в углу; на доске 4 × 4 два решения, зеркальные друг другу, а в треугольнике из 16 — одно. Чтобы доказать максимум, нужны пример и причина: квадратов 2 × 2 девять, каждая пара одинаковых клеток работает не больше чем на два, значит нужно 5 повторов и остаётся 16 − 5 = 11 цветов.

B · Цветные числа. По правилу цвета «заражают» друг друга: зная 2 и 3, получаем 6, затем 12, 18… Иногда рассуждают от противного (если бы 9 не было синим, 18 не могло бы быть синим). У {2, 3, 4, 6, 12, 24} вынужденные цвета противоречат друг другу: не нужно перебирать все способы, чтобы понять, что их нет.

C · Карты. Соседи — это общая граница. Пиццу из 4 или 6 кусков можно раскрасить 2 цветами, из 5 — нельзя. Острову нужно 3 цвета. Цветку из 5 лепестков нужно 4: центр забирает один цвет, а лепестки образуют нечётное кольцо и не могут чередовать всего два. Трудную карту из 20 стран тоже можно раскрасить 4 цветами, как и любую карту (теорема о четырёх красках, доказанная в 1976 году с помощью компьютера).

D · Раскраска как доказательство. Шахматной раскраски нет в условии — мы рисуем её сами. Каждый шаг к соседу меняет цвет, поэтому 13 жуков не помещаются в 12 клеток, прогулка по всем 25 клеткам доски 5 × 5 должна начинаться на цвете, которого 13, а на доске 4 × 4 нельзя обойти все клетки из угла в противоположный угол. В конце — цветное судоку.

Числа проверены перебором в scripts/verify_colorear.mjs.