2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Непрерывный Lights Out
Сообщение12.09.2014, 00:20 
Наверное, тут многие из вас слышали о такой вещи, как Lights Out. Если кто-то не слышал, то тут можно посмотреть простейшую реализацию 5x5. Здесь и здесь можно почитать про решение.

Так вот, хотелось бы расмотреть непрерывную версию.

Пусть задано множество $\Omega \subset \mathbb{R}^2$ вместе с подмножеством $A \subset \Omega$. Назовём $\Omega$ игровым полем, а $A$ - характеристикой игры.
Теперь возьмём множество $P \subset \mathbb{R}^2$ вместе с точкой $q \in P$. Пару $\left\{ P, q \right\}$ будем называть характеристикой хода.
Ходом в точку $a \in \Omega$ будем называть следующую операцию получения из $A$ множества $\bar{A}$: $$Stroke(\Omega, A, P, q, a) = \bar{A} = A \bigtriangleup P_a,$$
где $P_a$ - множество, получаемое из $P$ смещением всех точек $P$ на вектор $\overrightarrow{a - q}$, а $\bigtriangleup$ - симметрическая разность.

Теперь обозначим множество $A$ как $A_0$, множество $\bar{A}$ - как $A_1$, а точку $a$ - как $a_1$. Теперь возьмём точку $a_2 \in \Omega$ и получим новое множество $A_2 = Stroke(\Omega, A_1, P, q, a_2)$(мы совершили ещё один ход в точку $a_2$). Аналогично мы можем получить множество $A_3$ из точки $a_3$ и множества $A_2.$

Отсюда возникает вопрос - существует ли для данных $\Omega, A, P, q$ конечная последовательность ходов в точки $\left\{a_1, a_2,..., a_n\right\}$, такая, что в результате получится множество $A_n = \emptyset$? Назовём эту последовательность решением.
Если не существует конечной последовательности, то существует ли счётная?
Если не существует ни конечной, ни счётной последовательности, возможно ли найти хотя бы такую, что в итоге получится множество $A_n: \mu(A_n) = 0$? Здесь $\mu$ - мера Лебега. В данном случае искомую последовательность назовём почти-решением.

Вот здесь я смоделировал эту проблему. В данном случае $\Omega$ представляет собой квадрат, $A$ - вписанный в $\Omega$ круг, $P$ - круг с радиусом примерно в 8 раз меньше радиуса $A$, а $q$ - точный центр $P$. Существует ли решение в данном конкретном случае? Или хотя бы почти-решение?

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group