Поворачиваем кубики

11

Поворачиваем кубики

Нет, в этой статье не обсуждается «венгерский шарнирный кубик» (см. «Квант», 1980, № 12, с. 17) — головоломка, родившаяся в руках венгерского архитектора Эрнё Рубика и вызавшая акционер во всем мире, особенно в ВНР и США, где ее выпускают в миллионах экземпляров. К этой трудной и интересной игре «Квант» скоро вернется, а здесь речь пойдет о значительно более простой головоломке, которое каждый может смастить за несколько минут и для которого можно построить несколько и законченную математическую теорию.

Возьем 8 кубков и сложим из них куб вдвое большого размера*). Раскрасим три пары противоположных граней этого куба, соответственно, в белый и желтый, красный и оранжевый, зеленьий и синий цвета. Тогда у каждой из маленьких кубков три грани окажут раскрашениями в разные цвета. Возьем теперь куб в руки и повернем на 180° слой из четырех прилегающих друг к другу кубков относительно четырех остальных (по часовой или против часовой стрелки, не важно, — результат от этого не зависит). Очевидно, что это можно сделать третья разными способами. Изовем эти три поворота элематрими операции или ходами. Повторяя эти ходы в разном порядке несколько раз, мы будем получить разные распределения

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

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

Изображение состояния и запись ходов

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

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

Обозначим поворот передних четырех кубков на 180° вокруг оси x буквой X, поворот четырех правых кубков — Y и поворот четырех верхних кубков — Z (рис. 2). При всех этих ходах задний малый кубик будет оставаться неподвижным, так что выполнях ходы X, Y, Z, мы никакда не повернем куб как целое. Состояния, которые получаются из нулевого применением операций X, Y, Z, изображены на рис. 1, где они помещены номерами 2—4.

Композиция ходов и соответствия

Композицию (последовательное выполнение) ходов мы будем назвать

12

Рис. 1.

также умножением; произведение ходов будем записывать слева на право. Например, $YZX$ — это последовательное выполнение ходов $Y, Z, X$; $X^3 = XXX$ — это выполнение трех ходов $X$. Два произведения ходов мы будем считать равными, если они на каждое состояние куба действуют одинаково.

Умножение ходов, конечно, не коммутативно; например, все шесть «парных» произведений не равны (номера 5—10 на рисунке 1).

Обозначим $I$ «тождественный» ход, оставляющий куб не изменившимся. Очевидно,

$$X^2 = Y^2 = Z^2 = I.$$

Легко проверить, что все «парные» произведения, повторенные три раза, не меняют состояние куба:

$$(XY)^3 = (YZ)^3 = (ZX)^3 = (YX)^3 = (ZY)^3 = (XZ)^3 = I.$$

Кроме того,

$$(XYZY)^2 = (XZYZ)^2 = (YXZX)^2 = (YZXZ)^2 = (ZXYX)^2 = (ZYXY)^2 = I$$

Из равенств (), (), () легко получить (уже не обращаясь к кубу!) много новых равенств. Например (проверьте!), $XYX = YXY$ (см. также задачу 1 на с. 16).

Итак, мы получили три группы равенств, согласно которым все три хода $X, Y, Z$ являются «корнями квадратными из единиц» (*), а все шесть парных ходов — «корнями кубичными из единиц» (**), а еще шесть комбинаций ходов специального вида $(XYZY, YZXZ, ...)$ тоже являются.

13

Рис. 2.
ляются «корнями квадратными из единиц» (***).

Граф состояний
Мы научились изобразить состояния куба (и приписали им номера 1—24, рис. 1), научились записывать ходы и нашли соответствия между ходами. Хотелось бы уметь более наглядно изобразить связь между состояниями и ходами. Для этого служит граф состояний, показанный на рисунке 3. На нем точки (вершины) обозначают состояния, а отрезки — ходы, позволяющие перейти из одного состояния в «соседнее». Так, в центре рисунка жирная точка изобразает нульевое состояние; из нее выходит три отрезка, отвечающие ходам X, Y, Z; из точки на концах этих отрезков также выходит по три отрезка: один возврашает в нульевое состояние, остальные приводят в два новых состояния, и т. д. Продолжая этот процесс неограниченно, можно считать всего плоскостью покрытой шестиугольной сеткой — графом состояний.

Соотношения (*) на графе ответает движение туда и обратно по одному из отрезков, а соотношения (**) — обход шестиугольника (проверьте!).

У полученной картины оченьный недостаток — на ней имеется бесконечного много вершин (состояний), в то время как у нашего куба лишь конечное число состояний. Значит, какие-то (различные) вершины ответают одному и тому же состоянию. Чтобы в этом разобраться, зануемуйте (например, прямо на рисунке 3) все вершины графа номерами 1—14, пользовать рисунком 1.

Вы тогда увидите, какие вершины между собой должны совпадать. Например, жирная точка в верхней части рисунка 3 тоже ответает нульевому состоянию (а всего таких точки на рисунке уменьшилось 7). Кстати, путь от «центральной» нульевой точки к «верхней» соответствуют соотношениям

$$XZYZXZYZ = 1,$$

то есть одному из соотношения (***).

Рис. 3. Граф состояний куба. Стороны шестиугольников обозначают элементы операции (они помещены буквами X, Y, Z), вершины шестиугольников — состояния, а жирные точки ответают нульевому состоянию. Синние, красные и зеленные линия выделяют фундаментальные области.

14

Имея перед глазами пропумерованный граф состояний, легко ответить на поставленные в начале статьи вопросы. Имеется всего 24 состояния (и 24 класса равных между собой последовательностей ходов). Из них 3 состояния получятся из нулевого состояния одним ходом, 6 — двумя ходами, 9 — третья ходами и 5 — четверя ходами. Вообще, чтобы найти минимальную целочкуховов, соединяющую данные два состояния, достаточно найти две вершины на графе с соответствующими номерами и соединить их кратчайшей ломаной, которая указывает нужные ходы, причем число этих ходов всегда ≤4.

Фундаментальные области

В последней фразе вымательный читатель должен был заметить неообщим брать не любые «две вершины с соответствующими номерами», а также, которые расположены «по соседству», иначе может появиться лиший путь типа (***).

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

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

Пространственный граф состояний

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

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

Рис. 4.

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

Геометрическая задача. Покажите, что отношение границ других фундаментальных области (см. рис. 3; красные шестиугольники и синее ромбы) по указанным выше правилам дает тор с направованным на нем графом. Сравните этот граф с предыдущим.

Рис. 5.

15

Группы преобразования

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

$$1^\circ \text{композиция любых двух преобразований из } G \text{ также является преобразованием из } G:$$

$$f, g \in G \Rightarrow f^\circ g \in G;$$

$$2^\circ \text{преобразование, обратное к любому преобразованию из } G, \text{ также содержится в } G:$$

$$f \in G \Rightarrow f^{-1} \in G.$$

Из свойств $1^\circ$ и $2^\circ$ сразу следует, что тождественное преобразование $1$ всегда содержится в $G$ (ибо $f^{-1} \circ f = 1$).

Легко видеть, что для нашей игры совокупность всех преобразования (то есть последовательностей ходов) куба является группой преобразования множества всех его состояний. Действительно, свойство $1^\circ$ очень видно, свойство же $2^\circ$ следует из того, что любой ход обратен сам к себе (см. (*)), а преобразование, обратное к любой последовательности ходов, является той же последовательностью, только выписанной в обратном порядке (проверьте!).

В качестве других примеров групп преобразования называем семейство всех перемещений плоскости и совокупность всех взаимно-однозначных преобразования конечного множества (из $n$ элементов) на себя. Последняя группа называется группой подстановок (из $n$ элементов) и обозначается $S_n$. (Проверьте для нее свойства $1^\circ$ и $2^\circ$ и показите, что в $S_n$ имеется $n! = 1 \cdot 2 \cdot \dots \cdot n$ элементов).

С алгебраической точки зрения не существует, какова природа преобразуемых элементов, а важна алгебраическая структура самих преобразований, то есть то, как устройна операция умножения $\circ$ (композиция) в совокупности $G$. Алгебраические считают две группы преобразования $G$ и $H$ одинаковыми, если они изоморфны; это значит, что существует взаимно однозначное отображение $\alpha : G \rightarrow H$ группы $G$ и $H$, сохраняющее операцию композиции, то есть удовлетворяющее свойству

$$g, g' \in G \Rightarrow \alpha(g \circ g') = \alpha(g) \circ \alpha(g').$$

Например, совокупность всех перемещений плоскости, переводшей в себя некоторый фиксированный равносторонний треугольник, является группой (почему?) и эта группа изоморфна группе подстановок множества из трех элементов $S_3$ (проверьте!).

Подробнее о группах преобразования и о важном понятии (абстрактной) *группы можно прочитать в книге П. С. Александрова «Введение в теории групп» (Библиотека «Квант», вып. 7, М., 1980).

Алгебраическая модель игры

Мы показем, что группа преобразования называго куба изоморфна группе $S_4$ перестановок четырех элементов. Для этого занумерум вершины куба (или, что то же, маленькие кубики) цифрами от 1 до 8, как показано на рисунке 2. Легко видеть, что вершины $1-4$ и $5-8$ являются вершинами tetraэдров, вписанных в куб, причем при всех наших преобразованиях вершины $1-4$ и $5-7$ переходят друг в друга (а вершина $8$ остается на месте). Таким образом, наши преобразования осуществляют перестановку вершин $1-4$ и двацати четыREM преобразованиям куба взаимно однозначно сопоставляются $4! = 24$ перестановки четыREM четыREM.

Трем ходам $X, Y, Z$ соответствуют перестановки двух вершин: ходу $X$ — вершин $1, 2$, ходу $Y$ — $1, 3$ и ходу $Z$ — $1, 4$. Таким образом, мы связали нашу исходную задачу с довольно простой задачей о представлении всех элементов группы преставновок четыREM четыREM в виде произведения трех базисных парных преставновок одного выделенного элемента с треями остальных и показали, что

16

Все остальные элементы группы можно построить в виде произведений не более чем четырех базисных элементов.

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

Алгебраические задачи. 1. Покажите, что группа преобразованный нашего куба однозначно описывается основными соответствиями (); (), (). Это значит, что любое верное соотношение между ходами X, Y, Z может быть получено из основных вставками и сокращениями. (Вставкой называется операция над соотношениями, при которой в любое место уже полученного соотношения встляется одна из левых частей основных соотношения напрямера

$$XYXY = I \Rightarrow XY(ZZ)XY = I,$$

а сокращение — это операция, обратная к вставке, например:

$$ZXY(ZZ)YXZ = I \Rightarrow ZXYYXZ = I).$$

2. Покажите, что соотношение (*), (**) однозначно описывает группу тех перемещений плоскости, которые совмещают шестиугольную сетку саму с собой. (Указание. Ходу X отвечает симметрия плоскости относительно серединного перпендикуляра отрезка X — см. рис. 3).

Только ли игра?

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

Простейшей такой молекулой является молекula этана CH₃—CH₃, в которой один метильный радикал может поворачивать относительно другого (рис. 6). Свойства симметрики таких молекул, описываемые группами преобразования, оставляющих молекулы неизменными, в настоящее время интенсивно изучаются. И хотя пока неизвестна молекula, обладающая как раз такой симметрией внутренних враценей, как расстояний нами куб, но не исключано, что она может быть найдена. Существует молекula «кубон», состоящая из восеми atomов углерода и восеми atomов водорода (рис. 7), похожая на рассмотренную здесь модель; но, по-видимому, свободного враценя одной грани относительно паралельной грани не происходит.

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

Отсюда видно, что исследованные группы симметрики такого типа может оказаться интересным и с физическим точки зрения.

Поправка

В программу на с. 56 «Кванта», 1981, № 9 включает несколько операторов, из которых указывает отсутствие метки 1 перед пятым оператором и пропуск знаков продолжения в записи оператора DATA. На с. 55 вместе CALL STR следует читать CALL STR.