§ 18. ИГРА «В ПЯТНАДЦАТЬ»

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

И «виноваты» в том, что она забыта, математики, потому что они строго доказали, что определенные позиции этой игры являются выигрышными, а остальные — нет. Здесь мы приведем доказательство этого факта, использовав теорию перестановок.

Сначала коротко опишем смысл игры.

В плоской квадратной коробке размещены 15 одинаковых фишек квадратной формы, одно место остается свободным. Фишки занумерованы числами от 1 до 15 и размещены в определенном порядке (например, так, как на рис. 34 а).

Не вынимая фишек из коробки, а лишь передвигая друг за другом на свободное место, нужно разместить их в порядке возрастания номеров так, как на рис. 34 б.

Рис. 34

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

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

С каждым размещением фишек в коробке можно связать определенную перестановку на множестве М = {1, 2, 3, ..., 15, 16}, считая, что свободное место — это фиктивная фишка с номером 16. Для этого занумеруем места, которые могут занимать фишки, числами от 1 до 16 так, чтобы порядок нумерации совпадал с порядком стандартного размещения фишек. Следовательно, каждое размещение фишек однозначно характеризуется перестановкой на множестве М, первый ряд которой составляют номера мест, а второй — номера фишек, которые на этих местах стоят.

Например, размещение фишек на рис. 34 а описывается перестановкой

а размещение фишек на рис. 34 б — единичной перестановкой.

Начальные размещения можно однозначно описывать перестановками на множестве так как для них фиктивная фишка «стоит» на месте с номером 16. Переход от позиции, которая характеризуется перестановкой к позиции, которая характеризуется перестановкой если он возможен, осуществляется за несколько «ходов», причем каждый ход — это передвигание на свободное место какой-нибудь соседней фишки. Если свободным является место, а фишка, которая будет передвигаться, имеет номер и стоит на месте, то после перемещения эта фишка будет стоять на месте, а место освободится. Значит, за один ход от размещения

мы переходим к размещению

Следовательно, перестановку мы умножаем на. транспозицию

и имеем равенство

Если от позиции, которая описывается перёстановкой можно перейти к новой за один ход, то найдется такая транспозиция 62, что перестановка , которая отвечает новой позиции, будет связана с равенством

Допустим теперь, что для перехода от. позиции к позиции нужно сделать k ходов. Это означает, что существуют такие транспозиции вида для которых справедливо равенство

На свободное место каждый раз передвигается соседняя фишка, а это накладывает определенные ограничения на произведение Если от начального размещения удается перейти к стандартному, то можно подобрать такие транспозиции отмеченного вида, чтобы выполнялось равенство

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

Рис. 35

Покажем сначала, что когда от начального положения можно перейти к стандартному, то перестановка — четная.

Занумеруем ряды и столбцы, составленные из фишек так, как на рис. 35. При каждом перемещении фишки на свободное место (пере-ставлении ее с фиктивной) сумма номеров ряда и столбца, в которых стоит фиктивная фишка, увеличивается или уменьшается на единицу. Действительно, место каждой фишки однозначно характеризуется парой чисел . Если фиктивная фишка «стоит» на месте то очередной ход можно сделать четырьмя способами:

или лишь двумя или тремя из них, если фиктивная фишка «стоит» возле стенки коробки. В каждом этих случаев сумма заменяется на или , т. е. увеличивается или уменьшается на единицу.

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

Следовательно, перестановка раскладывается в произведение четного числа транспозиций, т. е. она четна.

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

(1)

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

Рис. 36

Пусть размещение характеризуется циклом (1, 2, k), т. е. в коробке фишка с номером 2 стоит на первом месте, фишка с номером k — на втором месте, фишка с номером месте , а все остальные — на своих местах. Делая определенное число перемещений звеньев цепи, мы можем фишку с номером 1 поставить на 3-е место. После этого, перемещая фиктивную фишку вдоль цепи в противоположном направлении, освободим место с номером 7. Теперь можно, переставляя лишь фишки, что стоят на местах с номерами 1, 2, 3, 5, 6, 7, достичь того, чтобы фишки с номером 1 и 2 стали на свои места, с номером k — на третье место, а остальные не изменили позиций.

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

В результате таких перемещений изменился порядок размещения лишь трех фишек. Фишку с номером к можно теперь включить в цепь. Перемещая по цепи, поставим ее на место с номером к. При этом все остальные фишки из цепи займут начальное положение. Осталось лишь поставить фиктивную фишку на последнее место, и мы получим стандартное размещение.

Рис. 37

Докажем теперь, что каждая четная перестановка раскладывается в произведение циклов из ряда (1). Действительно, каждая четная перестановка а раскладывается в произведение четного числа транспозиций:

Если , то в силу равенства можно написать

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

Если одно из в разложении (2) равно (1, 2), то соответствующее произведение на о будет тождественной перестановкой и его можно не учитывать.

Упражнения

1. Как практически осуществлять переход к стандартной позиции от размещений, которые характеризуются четной перестановкой?

2. Доказать, что каждая четная перестановка на множестве раскладывается в произведение таких циклов длины 3: .

3. Разложить в произведение циклов вида (1, 2, k) перестановки

4. Можно ли перейти к стандартному размещению от начальных позиций, заданных перестановками

5. Если позиция характеризуется нечетной перестановкой, то от нее можно перейти к размещению, которое отличается от стандартного порядком двух последних фишек. Доказать это.

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

Рис. 38

7. Игра «хамелеон» проводится на «доске» с девятью, клетками, которые соединены прямолинейными отрезками (рис. 38). На восьми фишках выписаны буквы х, а, м, е, л. Фишки в случайном порядке расставлены на клетках, расположенных в вершинах многоугольника. Цель игры состоит в том, чтобы, передвигая фишки по соединительным отрезкам, разместить их в правильном порядке, т. е. так, чтобы при чтении по часовой стрелке, начиная с клетки 1, получилось слово «хамелеон». Докажите, что прийти к правильному размещению фишек можно при любом их начальном расположении.

8.: Доказать, что теория игры «в пятнадцать» остается в силе и для игры «в восемь», правила которой такие же как и при игре «в пятнадцать», но здесь 8 фишек с номерами. 1, 2, 3, 4, 5, 6, 7, 8 перемещаются в квадрате с 9 клетками.

9. Пусть на фишках для игры «хамелеон» вместо букв выписаны числа 1, 2, 3, 4, 5, 6, 7, 8. Правила игры остаются прежними. Доказать, что полученная таким образом игра в точности совпадает с игрой «в восемь».

10. По аналогии с игрой «в 15» проведите исследование игры «в двадцать четыре».