Комбинаторная геометрия

Представьте игру, в которой выполняются простые правила:
1. На плоскости проведены несколько линий, каждая пара линий пересекается в одной точке.
2. Линии разбивают плоскость на области, раскрашенные в шахматном порядке.
3. Вы можете перестраивать разбиение, схлопывая и выворачивая треугольники.
4. Ваша цель получить максимально возможное количество темных областей.

Я уже запрограммировал браузерную игрушку по этим правилам. В простейшем случае 5 линий процесс игры выглядит так:

Пользовательский опыт

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

Я довольно быстро прошел все уровни до 19 линий. 21 линию (на скриншоте в начале) собрал часа за полтора. Правда, я знал, что существует центрально-симметричная конфигурация (поворот на 120 переводит ее в себя), и специально делал ее симметричной. 23 линии пытался собрать дважды, и оба раза не получилось набрать последнее очко.

С увеличением уровня сложность игры растет не только количественно (нужно дольше идти к цели), но и качественно: приходится придумывать новые приемы и подходы, так как старых становится недостаточно.

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

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

Математическая основа

Эта головоломка навеяна одной из задач из сборника Задачи Арнольда (В. И. Арнольд, 1983-4, изд. Фазис, 2000):

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

Это открытая математическая проблема. Она является частным случаем 16-й проблемы Гильберта для многочленов специального вида произведения линейных сомножителей ax+by+c.

Таким образом, переворачивая треугольники в игрушке, вы на самом деле решаете в частном случае задачу Арнольда! :)

Для преобразования конфигураций в головоломке именно схлопывание треугольников выбрано не случайно. Оказывается, с помощью таких схлопываний можно перевести произвольную конфигурацию в любую другую конфигурацию. Действительно, линии на плоскости, описанные в правилах, называются конфигурацией (псевдо)прямых. Они представляют элемент из группы кос. Суть теоремы Артина об образующих группы кос как раз и состоит в возможности перевода конфигураций друг в друга последовательностью преобразований треугольников.

Также задача Арнольда тесно связана с задачей о треугольниках Кобона.

Как я написал выше, задача Арнольда для произвольного количества прямых не решена. Вместе со мной Денис Уткин и Сергей Белёв потратили немало времени на попытки решения. Результаты нашего исследования в многостраничном pdf-отчете. Я хочу выразить благодарность Денису и Сергею за совместный интерес, без которого в конечном итоге не появилась бы эта головоломка. Бонус для внимательных читателей: в отчете есть примеры конфигураций, на которых достигается цель головоломки.

Вычислительная модель игры

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

На этом пока всё. Могу подробнее рассказать о процессе разработки игрушки и о нашем исследовании задачи Арнольда, включая десятки тысяч часов процессорного времени, потраченного на поиск оптимальных конфигураций оптимизированным перебором. Пишите в комментариях, интересны ли эти вопросы.