Сайт Романа ПарпалакаБлогКлючевые словазадача Арнольда

задача Арнольда

Головоломка Арнольда

Постоянные читатели помнят, что мы с коллегами по учебе лет 10 назад занимались задачей Арнольда. В ней остались открытые вопросы, и я недавно решил к ним вернуться. Дописал одну из программ, отрисовывающих и распрямляющих конфигурации, и понял, что получилась хорошая игровая механика для головоломки. Переписал код моделирования визуализации и моделирования на js, и получилась браузерная головоломка.

Правила

В этой игре выполняются простые правила:

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

В простейшем случае 5 линий процесс игры выглядит так:

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

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

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

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

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

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

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

Напомню формулировку задачи Арнольда:

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

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

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

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

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

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

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

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

21 ноября 2020 года, 21:27     задача Арнольда     Оставить комментарий

Намайнили

За попытку намайнить биткоины на суперкомпьютере в ядерном центре в Сарове оштрафовали на 450 тысяч рублей. Неплохо так намайнили.

Эх, не тем делом мы занимались на вычислительном кластере ОИЯИ. На 20 ядрах запускали перебор конфигураций в задаче Арнольда, потратили на него десятки тысяч часов процессорного времени. А можно было биткоины майнить.

28 сентября 2019 года, 22:08     по жизни · задача Арнольда     Оставить комментарий

Исследование на миллион

Задача о расположении прямых на плоскости была сформулирована В. И. Арнольдом в 1983 году. С тех пор эта нерешенная математическая проблема занимает лучшие умы человечества, подкупая простотой формулировки и создавая ощущение (в общем-то, ложное) близости решения.

Мы с Сергеем Белёвым и Денисом Уткиным рады сообщить о нашем скромном вкладе и представить отчет (PDF, 714 Кб) об упорных двухлетних исследованиях. В них использовались параллельные вычисления на десятках процессоров, некоторые сведения из теории группы кос и симметрической группы, а также факты из школьной геометрии и тригонометрии.

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

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

1 апреля 2010 года, 12:00     математика · задача Арнольда     Оставить комментарий

Летние школы

В ОИЯИ проходила школа по физике высоких энергий. На ней были лекции и доклады. Некоторые были интересными. Некоторые — слишком специфичными и скучными.

Один из лекторов — Андрей Грозин — ходил в прикольной футболке с надписью «посторонись, несу ахинею».

Впрочем, стоит заметить, что говорил он умные и дельные вещи.

В программе школы были предусмотрены развлекательные мероприятия: в один из дней мы катались по Волге и ели шашлыки на открытом воздухе.

А еще я умудрился встретиться с Владимиром Игоревичем Арнольдом (по поводу задачи о прямых). Он читал лекции на летней математической школе в Ратмино, недалеко от Дубны. Там мы его и нашли.

В целом, июльская поездка в Дубну была полезной и продуктивной.

13 августа 2009 года, 22:16     lytdybr · задача Арнольда     Комментарии (1)

Задача

На плоскости проведены n прямых, разбивающих ее на области. Они раскрашиваются в шахматном порядке: области, имеющие общие стороны, должны быть покрашены в разные цвета. Чему равна максимальная разность между числом черных и белых областей?

PS. Для заинтересовавшихся этой задачей приведу одну картинку для семи прямых:

7 прямых

Разность между числом черных и белых областей на этом рисунке — 7. Расположение прямых, дающее такую разность, не единственное, но вычисления на компьютере показали, что улучшить данный результат нельзя.

9 марта 2008 года, 20:44     математика · задача Арнольда     Комментарии (5)
Поделиться
Записи