Головоломка Арнольда: от комбинаторной геометрии к браузерной игрушке

Представьте игру, в которой выполняются простые правила:

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

1. На плоскости проведены несколько линий, каждая пара линий пересекается в одной точке.

2. Линии разбивают плоскость на области, раскрашенные в шахматном порядке.

3. Вы можете перестраивать разбиение, «схлопывая» и «выворачивая» треугольники.

4. Ваша цель – получить максимально возможное количество темных областей.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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