Задачи по анализу положений

Игры “Рассада” и “Брюссельская капуста”

"The day after sprouts sprouted, it seemed that everyone was playing it, at coffee or tea times, there were little groups of people peering over ridiculous to fantastic sprout positions."

Игру придумали в 1967 году John H. Conway и Michael S. Paterson в английском Кэмбридже.

Пример игры в рассаду

Рассада

В игре участвуют два игрока.

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

Правила игры:

• За один ход игрок обязан нарисовать несамопересекающуюся кривую, соединяющую некоторую вершину с какой-то другой вершиной (может быть той же самой), и нарисовать в некотором месте на этой кривой новую вершину. Причём эта кривая не должна пересекаться с другими кривыми и не должна проходить через другие вершины, кроме тех, которые она соединяет, а новая вершина на этой кривой не должна совпасть с соединяемыми этой кривой вершинами.
• Степень каждой вершины должна быть меньше или равна трём в любой момент времени.

Побеждает тот игрок, который сделал последний ход.

Теорема: Игра в Рассаду всегда заканчивается за конечное время, причем, если игра начинается с $n$ вершин, то суммарное количество ходов не превышает $3n-1$ и оказывается не меньшим чем $2n$.

Доказательство:

1. Игра кончится за конечное время. Будем считать, что у каждой вершины в каждый момент времени есть набор “жизней” — от нуля до трёх. Число жизней вершины — количество кривых, которые ещё можно присоединить к ней. Иными словами, текущее число жизней можно получить вычтя из тройки валентность этой вершины в этот момент. Будем называть точку живой, если число её жизней больше $0$ и мертвой иначе.

   Изначально у всех стартовых вершин было по три жизни. Каждый ход уменьшает суммарное количество жизней на единицу, так как при проведении кривой, соединяющей две вершины, теряется две жизни — по одной в каждой из вершин — при том, что новая вершина, появившаяся на кривой, имеет лишь одну жизнь. Отсюда следует, что количество ходов не может превышать $3n$.

2. Число ходов не превышает $3n-1$. Предположим, что мы начали игру с $n$ вершинами, сделали $m$ ходов, и игра закончилась. В конце игры суммарно осталось $3n-m$ жизней. Все живые вершины имеют в точности одну жизнь, иначе мы могли бы добавить петлю в такой вершине и игра ещё не была бы окончена. Таким образом, живых вершин осталось ровно $3n-m$. При этом, существует хотя бы одна живая вершина — например, вершина, появившаяся на кривой в процессе последнего хода. Отсюда имеем $3n-m\geqslant1$.

3. Число ходов не меньше $2n$. Пусть в конце игры у нас остался некоторый набор живых вершин. Назовём их выжившими. Мёртвая вершина называется соседом выжившей, либо если она соединена с ней напрямую, либо, при условии, что из выжившей вершины идёт петля, если она соединена с вершиной на этой петле (см. рисунок ниже).

   Каждая выжившая точка имеет ровно двух мёртвых соседей. Никакая мёртвая вершина не может быть соседом двух разных выживших вершин, иначе бы существовал ещё один ход. Все остальные мёртвые точки (не соседи выживших) называются фарисеями. Пусть есть $p$ фарисеев. Тогда

   $$ n+m=3n-m+2(3n-m)+p. $$

   Так как число исходных вершин + число ходов = суммарное число вершин в конце игры = выжившие + соседи + фарисеи. Тогда

   $$ m=2n+\frac{p}{4}. $$

   То есть игра длится не менее $2n$ ходов, а число фарисеев кратно $4$. Доказано.