Расселение фишек

Квант 1982, №7 с. 28, 30, 31 Тег MQ6D

А. Ходульев

Расселене фишек

От редакции

Эта заметка посвящена следующей задаче М. Концевича (из № 11 за 1981 г.), признанной читателями одной из лучших сред опубликованных в «Задачнике Кванта» в прошлом году:

М715. Прямой угол разбит на клетки. На некоторых клетках стоит фишки, причем расположение фишек можно преобразовать так: если для некоторых фишки соседняя сверху и соседняя справа клетки свободны, то в эти клетки ставится по фишке, а старая фишка убирается. Вначале в угловую клетку ставится одна фишка. Можно ли несколькими указанными преобразованиями освободить от фишек уголки из a) трех, б) шести, в) десяти клеток, показанные на рисунках 1, a, б, в?

Эта задача нам также очень понравилась — мы нашли в ней многое черты, которые были бы разделить в новых материалов, присылаемых в журнал: наглядная формулировка, побуждающая проделать эксперимент и затем постройть общую теория; характерный для современной дискретной и прикладной математики объekt исследования (решетка, заполненная единицами и нулями, локальные правила перехода); естественное появление в решении целого букета важных математических понятений и конструкций (инвариант, бесконечная сумма, вложение задачи в некоторое ее «расширение», конечный алгоритм и т. п.). Очень советуем тем, кто не решал задачу M715, подумать над ней хотя бы час, прежде чем читать статью («главный» рисунок 8 мы нарочно отправили в конец статьи). Остальные, уже испытавшим это удовлетворение, мы предлагаем доказать не доказанные факты из второй части статьи, где излагается необольшая теория, позволяющая исследовать разрешимость «игры Концевича» в самом общем случае.

Решение задачи M715. Инвариант

Для понсков нужной последовательности ходов удобно воспользоваться шашками и обычной шахматной доской. Поставив шашку в левый нижний угол и немного позкспериментровав, легко найти решение задачи a). В этой задаче можно освободить розовую область, например, так, как показано на рисунке 2 — за 4 хода (1,1), (2,1), (2,2), (1,2). (Запись хода указывает координаты клетки, с которой снимается фишка при выполнении хода. Например, ход (2,1) означает, что фишка снимается с поля (2,1), а на поля (2,2) и (3,1) ставятся новые фишки).

Рис. 1.

начием оба этих ряда вместе через $L$ — см. рис. 3, где $L$ выделено голубым цветом) всегда будет находиться лишь по одной фишке, каждая из которых внесет в сумму $s_{\text{кон}}$ вклад, не превышащий 1/8 (поскольку они должны находиться за пределами $B$ ). Сумма чисел для остальных фишек должна быть меньше, чем $s(K \setminus B \setminus L) = 3/4$ . Поэтому $s_{\text{кон}} < s(K \setminus B \setminus L) + 2 \cdot \frac{1}{8} = 1$ , а это уже противоречит тому, что $s_{\text{нач}} = 1$ .

Задания a), б), в) решены, однако интересно научиться использовать любую аналогичную задачу. Можно ли, например, освободить область $\Gamma$ , показанную на рисунке 4? Здесь $s(K \setminus \Gamma) = 1\frac{1}{2}$ и даже с учетом единственности фишек в первом горизонтальном и вертикальном ряду можно получить лишь $s_{\text{кон}} < 1\frac{1}{8}$ .

Вместе с тем освободить эту область не удалось.

Мы будем исследовать теперь задачи такого типа: вначале фишки заполняют множество $H$ ; нужно несколькими ходами освободить множество $F$ (здесь $H$ и $F$ — любые конечные множества клеток из $K$ ). Будем назвать её задачей освобождения ( $H, F$ ).

Обобщенные позиции и ходы

Прежде всего, удобно избавиться от запрещения делать ход от клетки $(i, j)$ , когда она свободна или когда клетки $(i, j+1)$ , $(i+1, j)$ заняты (данное в условиях задачи правила

мешает менять порядок ходов, что очень стесняет). Но тогда придется сльно обобщить и понятие позиции. Будем теперь считать, что в клетке $(i, j)$ может находиться любое целое число $A_{ij}$ фишек — не только положительное, но ирицательное, причем для каждой позиции $A$ лишь для конечного множества клеток число $A_{ij}$ отлично от 0. Ход (обобщенный) в такой позиции — одновременная замена
$A_{ij} \rightarrow A_{ij} - 1, A_{i+1,j} \rightarrow A_{i+1,j} + 1, A_{i+1,j} \rightarrow A_{i+1,j} + 1.$
Прежние позиции (в которых $A_{ij}=1$ или $A_{ij}=0$ ) и ходы будем называть нормальными.

На рисунке 5 показан ход, в результате которого из нормальной позиции получается не нормальная. В нижней части рисунка 5 та же позиция показана в новой, числовой записи.

Результат выполнения хода из клетки $(i, j)$ состоит в вычитании единиц из $A_{ij}$ и прибавления единиц к $A_{i+1,j}$ и $A_{i,j+1}$ ; результат нескольких таких вычитаний и прибавлений, очевидно, не зависит от порядка их выполнения.

Имеет место следующий заменательный факт, позволяющий применять обобщенные ходы для решения интересующей нас задачи: если одна нормальная позиция $P$ может быть переведена в другой нормальной позицию $Q$ последовательностью произвольных (возможно, не нормальных) ходов $\{d_1, d_2, \dots, d_n\}$ , то $P$ может быть переведена в $Q$ и некоторой последовательностью нормальных ходов, полученной перестановкой ходов данной последовательности. (Доказйте это!)

Далее вместе задачи освобождения $(H, F)$ мы будем рассматривать следующую «задачу нормализации»: задана позиция $A$ , в которой все $A_{ij} \geq 0$ , причем некоторые $A_{ij}>1$ ; нужно несколькими ходами приведены к нормальной. Чтобы свести передую задачу ко второй, образуем позицию $A_{ij}=H_{ij}+F_{ij}$ (обозначим ее $A=H+F$ ), другими словами, к фишкам $H$ добавим еще по фишке повсюду в $F$ — тогда в $F \cap H$ будет стоять по две фишки. Оказывается, что задача освобождения $(H, F)$ эквивалентна задаче нормализации $H+F$ . (Доказите это!)

Решение «задачи г» (рис. 4)

Добавляя по одной фишке в клетках области $\Gamma$ , получаем задачу нормализации, изображенную на рисунке 6.

Рекомендуем вам продолжать дальнейшие ходы на шахматной доске. Подойдут общные шашки — «минус-шашки» не попадются. Глядя на позицию, мы видим, что на клетке $(1,1)$ стоит две фишки. Одна из них должен быть убрана; это можно сделать только ходом $(1,1)$ . Значит, ход $(1,1)$ должен присутствовать в любом решении, то есть это — необходимый ход. Можно считать, что он делается первым. Сделаем его. Получим позицию, изображенную в второй картине на рисунке 7. Дальнейшие (необходимые) ходы показаны на этом же рисунке. В результате их выполнения исходная позиция возникла вновь (только сдинитая на одну клетку вверх и на одну клетку вправа). Отсюда следует, что исходная задача г) неразрешима (продумайте это!).

Общий алгоритм

Пользовать обобщенными ходами и нормализей, мы сумели разо-

Рис. 7. (Окончание см. на с. 55.)