Какие задачи решила математика: комбинаторика, укладки и замощения

продолжаем смотреть на задачи, решенные математикой, сегодня немного комбинаторики и укладок:

Решённые задачи математики: раскраска карт четырьмя цветами

11. Раскраска любой плоской карты четырьмя цветами
Задача: доказать, что любую карту на плоскости можно раскрасить так, чтобы соседние области были разных цветов, и при этом хватило четырёх красок.
Решение: построено доказательство (искали десятилетиями): если бы существовала карта, требующая пять цветов, в ней обязательно нашлась бы «запретная» конфигурация, которая не может возникнуть. Итог строгий: четырёх цветов всегда достаточно.

Решённые задачи об укладках шаров и кругов

12. Максимально плотная укладка одинаковых шаров в 3D
Задача: уложить шары одного радиуса в пространстве так, чтобы доля занятого объёма была максимальной и шары не пересекались.
Решение: доказано, что классическая «пирамидальная» укладка (как у апельсинов в магазине) — предельно плотная. Никакая другая конфигурация не заполнит пространство большей долей. Эту задачу называют ещё гипотезой Кеплера.

13. Максимально плотная укладка кругов на плоскости
Задача: уложить одинаковые круги на плоскости максимально плотно без перекрытий.
Решение: оптимален рисунок в виде пчелиных сот: каждый круг окружён шестью соседями, центры образуют гексагональную решётку. Плотнее в плоскости нельзя — это строго доказано.

Комбинаторика и стратегии: ещё одни решённые задачи математики

14. Стратегии в играх
Задача: для игр вроде крестиков-ноликов определиить при идеальной игре будет ли выигрыш или ничья.
Решение: игру представляют деревом ходов и систематически обходят, помечая позиции как выигрышные/проигрышные/ничейные. Для крестиков-ноликов строгий вывод: при идеальной игре получается ничья.

Решённые задачи о замощении плоскости без периодичности

15. Замощение плоскости одной плиткой без периодичности
Задача: найти форму плитки, которая замощает плоскость без дыр и перекрытий, но так, чтобы узор не становился периодическим (никакой сдвиг не совпадает с самим собой).
Решение: найдены конкретные формы плиток, для которых доказано: замощение возможно, но любые получающиеся узоры неизбежно непериодичны. Получаются «орнаменты без обоев»: локальные мотивы повторяются, а глобального повторения нет.

Продолжение следует…