§ 21. ДРУГИЕ ИГРЫ

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

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

1. Игры типа игры «хамелеон».

Игра «хамелеон», описанная в упражнении 7 к § 18, совпадает с игрой в «восемь» (упражнение 9 к § 18). Однако первоначальная формулировка этой игры допускает различные обобщения, которые можно условно назвать перестановочными играми на графах. Опишем такую игру в общем случае (рис. 49).

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

Рис. 49

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

Следует отметить, что если характеризовать всевозможные случайные расположения фишек перестановками множества номеров вершин Графа (т. е. считать, что фишки занумерованы теми же числами, что и вершины графа кроме последней), то всем «допустимым» расположениям фишек — таким, от которых можно перейти к первоначальному, — будут соответствовать перестановки, образующие группу (почему?). А различным «ходам» будут отвечать умножения на определенные перестановки из этой группы, которые являются ее системой образующих (почему?).

2. Игра «домино».

Эта игра построена по образцу кубика Рубика. Прямоугольный параллелепипед составлен из 18 маленьких кубиков, образующих две квадратные плиты по 9 кубиков в каждой (рис. 50), Кубики скреплены так, что плиты могут свободно вращаться одна относительно другой (рис. 50). Кроме того, могут вращаться и прямоугольные плиты, состоящие из 6 кубиков. Три таких плиты параллельны одной паре боковых (не квадратных) граней и три — другой.

Рис. 50

Рис. 51

Рис. 52

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

В начальном положении квадратные плиты составлены из кубиков одинакового цвета, которые расположены в порядке возрастания числа кружочков справа налево и снизу вверх (рис. 51). Кубики черной и белой плит с одинаковым числом кружочков расположены один под другим.

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

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

элементов!

Обобщением игры «домино и кубика Рубика является «волшебный параллелепипед». Имеется в виду параллелепипед, разбитый на х маленьких кубиков плоскостями, параллельными его граням. Неквадратные грани можно поворачивать только на 180°. Внутренние плиты тоже вращаются. Понятно, что анализ этого общего случая основывается на тех же идеях, однако чисто технически все сложнее.

Недавно в Венгрии налажен выпуск 4x4x4 кубиков, называемых «Месть Рубика»!

3. Волшебный тетраэдр.

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

Группа перестановок, связанная с тетраэдром, состоит из

элементов.

Аналогичные игры можно образовывать и для других правильных многогранников, например для додекаэдра. Группа перестановок, получающаяся при рассмотрении игры, связанной с додекаэдром, состоит из

элементов.

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

4. Волшебная пирамидка.

Основой этой игрушки является урезанный конус, разбитый плоскостями, параллельными основанию, на 6 частей, которые крепятся на общей оси, совпадающей с осью симметрии конуса, и могут свободно вокруг нее вращаться. В этих частях сделано 6 вертикальных прорезей, в которых крепятся шарики одинакового диаметра. Прорези устроены так, что шарики из них не выкатываются. Шарики окрашены в 6 цветов по числу прорезей. Шарики одного цвета имеют разную тональность — от более светлых до более темных тонов. Имеется 6 шариков каждого цвета, кроме одного цвета, в который окрашено на один шарик меньше, так что одно из 36 мест для шариков в прорезях остается свободным. Кроме того, в одной прорези имеется внутренняя кнопка, позволяющая «утапливать» шарик, стоящий на этом месте, и ставить на его место другой шарик. «Утопленный» шарик возвращается на свое место как только оно освобождается. Общий вид - волшебной пирамидки изображен на рис. 53; пирамидкой она называется потому, что конус, после того как в нем сделаны прорези, стал больше походить на пирамидку.

Рис. 53

В начальном положении шарики расположены в прорезях так, что в каждой из прорезей лежат упорядоченные по тональности шарики одного цвета, скажем снизу темнее, а чем выше, тем светлее. Случайными вращениями шести основных частей пирамидки вокруг оси приводят ее в «пестрое» положение. Требуется с помощью таких же вращений, перемещений шарика в одной из прорезей на свободное место, «утапливания» одного из шариков перевести пирамидку в начальное состояние. Игра эта интересная, однако она существенно проще игры «кубик Рубика».

В заключение отметим также, что югославский математик В. Чепулич в 1979 г. предложил перестановочную

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

Упражнения

1. Неориентированный граф называется полным, если любые две его вершины соединены ребром. Рассмотреть игру типа «хамелеон» для полного графа. В частности, установить, можно ли от любого расположения фишек в вершинах такого графа перейти к начальному расположению? Если это так, то какое наибольшее число ходов необходимо осуществить для перехода к начальному расположению фишек в случае полных графов с тремя, четырьмя, пятью вершинами?

2. Построить неориентированный граф с шестнадцатью вершинами, перестановочная игра на котором совпадала бы с игрой «в пятнадцать»,

3. Доказать, что группа перестановок, получаемых при вращениях «домино», состоит из перестановок.

4. Какие перестановочные конструкции используются при построении, группы перестановок для «домино».

5. Разработать алгоритм, позволяющий от любого допустимого расположения кубиков в «домино» перейти к начальному.

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

7. Можно ли от любого расположения шариков в волшебной пирамидке перейти к начальному?