Игра в 15

26

Игра в 15
О. Т. Долгов

— Так это же известная задача!
— А как она решается?
— Да нет! Условие известное,
а решение я не знаю…
Милл. Диалоги

1. Слово Сэму Лойду
   В «Кванте» уже расссказываюсь о книге Мартина Гарднера «Matематические досуги» («Квант», 1973, № 6). 33-я глава «Досугов» называется «Игра в 15 и другие головоломки».

В плоской квадратной коробочке лежат 15 шашек с номерами. «Нормальное» расположение шашек показано на рисунке 1. На рисунке 2 показано другое расположение: шашки с номерами 14 и 15 переставлены. Нужно, передвигая по очереди по одной шашке, перевести это расположение в «normальное». Шашки передвигают на свободное соседнее место, вынимать их из коробочки не разрешается.

Игру в 15 изобрел в семидесятых годах прошло века Сэм Лойд. Повальное увлечение его быстро охванило Англлю, а потом перекинулось и через Ла-Манш. Свой рассказ об этом Гарднер использовет цитатой из самого Лойда:

«Люди буквально помещались на этой головоломке. Из уст в уста передавались рассказы о лавочнике, забывшем открыть свою лавку, о связишинике, простоявшем под улиным фонарем долгую зимнюю ночь в надежде припомнить, как ему удалось решить задачу…

Один известный редактор из Балтийма рассказывает, что как-то раз он ушел в полдень на ленч и лишь поздней ночь был обнаружен вонец отсутствия сотрудниками газеты сидящим за столом и гоняющим взад — вперед по тарелке маленькие кусочки пирога!»

В 1879 году была опубликована математическая теория игры в 15, после чего игра быстро вышла из моды.

Matematическая теория, подорвавшую интерес к головоломке Лойда, Гарднер в своей книге не изла-

27

гает. Между тем теория эта проста и почительна.

2. Четные и нечетные перестановки
   Расположим числа 1, …, 15 в произвольном порядке. Например, так:
   1, 2, 3, 4, 8, 7, 6, 5, 9, 10, 11,
   12, 15, 14, 13, (1)
   или так:
   1, 2, 3, 4, 8, 7, 6, 5, 9, 10, 11,
   12, 14, 15, 13. (2)

Какое из подобных расположений называется перестановкой.
Будем говорить, что в данной перестановке числа i и j образуют беспорядок, если i > j, но i стоит в этой перестановке левее j.
Пример. Числа 8 и 6 в перестановке (1).
Назовем перестановку цемной (нечетной), если в ней четное (нечетное) число беспорядков.
Примеры. В перестановке (1) — девять, а в перестановке (2) — восемь беспорядков, так что (1) — нечетная, а (2) — четная перестановка.

3. Перестановки и игра в 15
   Начертим на коробочке для игры в 15 такую ломаную, как на рисунке 3. Пройдем по этой ломаной из левого верхнего угла коробочки и выпишем номера шашек, которые мы будем последовательно проходить.
   Примеры. Если шашки расположены так, как на рисунке 1, то мы получим перестановку (1); для расположения на рисунке 2 получится перестановка (2).
   Проход через пустую клетку, мы не пишем никакого номера. Поэтому одна и та же перестановка соответствует шестнадцатей различным расположениями шашек в коробочке. Например, перестановка
   1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
   12, 13, 14, 15
   соответствует любому из расположений на рисунке 4.
   При игре в 15 шашки можно перевиграть по горизонталям и вертикалям, занимая соседнюю путь к клетку. Если шашка перевиграется по горизонталии, то и старому, и новому расположению соответствует оченьindo, одна и та же перестановка (рис. 4, a, б). Если шашку перевиграют по вертикали, то может служиться, что перестановка не меняется (рис. 4, б, б), но общую старому и новому расположению соответствует разные перестановки (рис. 5).
   Однако эти перестановки всегда имеют, оказывается, одинаковую цемность (либо обе четные, либо обе нечетные).
   Проверим это сначала в случае, изобравженном на рисунке 5. Расположению на рисунке 5, a соответствует перестановке
   …, 6, 5, 11, 9, 10, …, (a) расположению на рисунке 5, б — перестановка
   …, 10, 6, 5, 11, 9, … (б) (многооточия заменяют совпадание в

28

(a) и (6) числа). При перехождение (a) к (6) один беспорядок (11, 10) исчезает и три новых (10, 6), (10,5) и (10, 9) возникают. Общее число беспорядков возвращает на 2, так что (a) и (6) имеют действительное одинаковую четность.

В обшем случае, когда шашку с номером $n$ передвигают с клетки $A$ на пустую клетку $B$ (рис. 6), доказательство проводится совершению аналогично. На участке ломанной между $A$ и $B$ располагается всегда четное число шашек. Пусть $y$ $m$ из них номера меньше $n$, у $k$ — больше $n$; тогда $m$ беспорядков при передвижении шашки исчезает и $k$ беспорядков возвращает на $k$ — $m$. Это — четное число, так как по условию число $k + m$ четно. Таким образом, перестановки, соответствующие старому и новому расположению, обязательно имеют одинаковую четность.

4. Неразрешимость головоломки
   Лойда

Перестановки (1) и (2), соответствующие расположения шашек на рисунках 1 и 2, имеют разную четность. Значит, эти расположения нельзя получить друг из других: головоломка Лойда неразрешима.

5. Выйдет — не выйдет?
   Ну, а если произвольно расположить шашки в коробочке? В каких случаях головоломка выйдет (расположение удastoreсти в «normальное»), а в каких — не выйдет?

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

Доказывать это утверждение можно по-разному. Ниже мы сделаем это примерно таким же способом, как С. Бобров в своей книге «Волшебный другог» *).

6. Как перерыгнуть через две шашки
   Начертим на коробочке замкнутый путь в виде буквы П (рис. 7). Вдоль этого путь шашки можно передвигать одну за другой, «гуськом». Таким образом, можно, например, расположение, изобразенное на рисунке 8, $a$, постепенно перевести в «normальное» (рис. 8, 6, 8, 2, $\partial$). Это удastoreсти сделать потому, что относительной порядок шашек вдоль путь П (начиная с шашки 1, по часовой стрелке) одинаковов:
   {1, 2, 3, 4, 8, 12, 15, 11, 7, 6, 10, 14, 13, 9, 5}.

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

*) Бобров С. Волшебный другог. Детгиз, 1946, с. 29—41, 89—117.

29

Ниже мы укажем прием, с помощью которого это можно делать.

Пусть шашки с номерами $i, j$ и $k$ стоит друг за другом вдоль пути $\Pi$ (рис. 9, а). Перевигая все шашки «гуськом» вдоль $\Pi$, легко добиться, чтобы шашки $i, j, k$ и пустая клетка $B$ расположились так, как на рисунке 9, б. Перевигая теперь шашку $i$ на пустую клетку $B$, мы из порядка $\{..., i, j, k, ...\}$ получим порядок $\{..., j, k, i, ...\}$ — шашка с номером $i$ «перепригнута» по часовой стрелке через две соседние: $j$ и $k$.

Так же просто заставить любую шашку «прыгнуть» через две соседние против часовой стрелки. Например, чтобы на рисунке 9, а шашка $k$ «перепригнута» через $i$ и $j$, нужно сначала перевинуть шашки «гуськом» вдоль пути $\Pi$ в положение, изображенное на рисунке 9, в а затем перевинуть шашку $k$ на пустое место $B$.

Итак, мы указали прием, с помощью которого можно заставить любую шашку «прыгнуть» через шашки, стоящие на пути $\Pi$ рядом с ней.

30

7. Все, кроме двух, — по местам!
   С помощью этого приема легко перевести любое расположение шашек в одной из двух расположений, приведенных на рисунках 10, а, б.

Прежде всего поведем вдоль пути П шашку 2 к шашке 1. Перепрыгивая против часовой стрелки через две шашки столко раз, сколько попадобится, доведем ее либо до «своего» места (рядом с «единицей»), либо до соседнего (междуней и шашкой 1 останется неокоторая шашка i), — в обихх случах оставимся в тот момент, когда следующий прыжок был бы через шашку 1. Если между «двойкой» и «единицей» останется шашка i, заставим ее прыгнуть через две шашки (в том числе через «двойку») по часовой стрелке, — тогда «двойка» очистится рядом с «единицей» (причем с нужной стороны).

Затем таким же способом поведем «тройку» к «единице» и «двойке». Потом «четверку» — к «единице», «двойке» и «тройке». И так далее — вплоть до шашки 13.

Передвигая после этого все шашки «гуськом» вдоль П, приdem к одному из двух расположений, изобразенных на рисунке 10.

8. Хорошие и пложные расположения
   Все расположения шашек разбились, таким образом, на два класса. Расположения 1-го класса можно перевести в такое, как на рисунке 10, а, расположения 2-го — в такой, как на рисунке 10, б.

Подумаем, почему отсюда следует утверждение, сделанное в п. 5, и что еще отсюда следует.

Если некоторое расположение P можно перевести в расположение Q, то и обратно, Q можно перевести в P. Поэтому все расположения 1-го класса можно перевести друг в друга. Согласно п. 4 соответствующие им перестановки — одинаковой четности, причем нечетные, так как расположению на рисунке 10, а соответствует нечетная перестановка

1, 2, 3, 4, 5, 10, 11, 15, 12, 9, 6, 7, 8, 13, 14 (тринадцать беспорядков).

Точно так же переводятся друг в друга и все расположения 2-го класса, причем им соответствует четные перестановки.

Тем самым, «нормальное» расположение относится к 1-му классу, а расположение на рисунке 2 — ко 2-му. Изовем расположения 1-го класса хорошим, а 2-го класса — плохими.

Подведем итог доказанному.

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

Все остальные расположения плоские, им соответствуют четные перестановки, их нельзя перевести в расположение, изобразенное на рисунке 1, и можно перевести в расположение, изобразенное на рисунке 2.

Замечание. Сообщения, приведенные в п. 6 и п. 7, фактически позвольют

32

любой перестановки из чисел 1, . . ., n можно перейти к любой другой перестановке из тех же чисел, меняя местами molъко соседние числа.

5. Двухэтажная игра в 31. В коробочку с размерми $2 \times 4 \times 4$ положим 31 кубик «в 2 этажка»: 16 кубков внизу, 15 — наверху. Одно место в коробочке оставим пустым.

На кубиках напишем номера: 1, . . ., 31, причем на каждом кубике напишем его номер дважды: на верхней и нижней грани.

Дно и крышку в коробочке сделаем проэрачными и напротив каждой кубика проделаем отверстия (такие, чтобы кубики через них не проезали, но их легко было передвигать, не вынимая из коробочки). Теперь коробочку можно как угдоно переворчитать: у нее больше нет «постоянного верхка» и «постоянного низа». Кубики можно перемешать по каждому этажу и перевигать с этажка на этаж.

Получился «двухэтажная игра в 31». Разработайте теорию этой игры.

6. Игра в 15 на цилиндре. Полый цилиндр (рис. 12) разрежем на 16 один-каждый изогнутых шашек, проведя 4 вертикальных и 3 горизонтальных разреза. Одну шашку выбросим. Остальные переменуем числа 1, . . ., 15 и поместим в специальную коробочку в форме полости между двумя цилиндрами. Во внешнем проэрачном цилиндре проделаем 16 отверстия — «игра в 15 на цилиндре» готова (рис. 13).

Как и в обычной игре в 15, шашки разрешается передвигать по одной на свободное соседнее место; кроме того, разрешается одновременное поворачивать 4 шашки (рис. 14), как обойтиму шарикоподшипника.

Можно ли любое расположение шашек перевести в любое другое?

Замечание. Не обязательно делать коробочку и шашки цилиндрическими. Можно использовать обычную игру в 15, разрешив дополнительно «циклические сdvги строк» (рис. 15): например, «циклический сdvги 1-й строки» переводит расположение, изображенное на рисунке 15, а, в расположение, изображенное на рисунке 15, 6.

После нее заменение поможет вам справиться с управлением 6 и облегчит нам формировку следующей задачи.

33

7. Игра в 16 на торе. Чтобы сделать из прямоугольника цилиндр, нужно склеить противоположные вертикальные края. Если после этого склеить и противоположные горизонтальные края (рис. 16), получится mop (поверхность бублика).

Чтобы изготовить «игру в 16 на торе», не обязаательно вырезать шашки из бублика. Достаточно в обычной игре в 15 заполнить пустую клетку шашкой с номером 16 и разрезить «циклическое сdwги и строки и столбцов» (рис. 17).

a) Можно ли таким сdwгами перевести расположение, изобразенное на рисунке 18, а, в расположение, изобразенное на рисунке 18, б?

b) Можно ли любое расположение перевести в любое другое?

b) Решите обещую задачу об игре в $n^2$ на торе.

Эта статья была уже подготовлена к публикации, когда редакция «Кванта» получила письмо об игре в 15 от школьника — десяя-