Математика волшебного кубика

22

В. Дубровский

Математика
волшебного кубика

«Квант» уже расссказывает подробно о конструкции венгерского «волшебного кубика» и алгоритмах решения этой головоломки*). Вслед за кубиком на свет появился целая серия похожих на него игр. Математический теории таких игр и посвящена наша статья. А для любителей практической игры в кубик мы приводим принципально схему рекордно короткого алгоритма волшебного кубика, основанную на этой теории.

Волшебный кубик задает вопросы
Условимся называть различные варианты сборки волшебного кубика, возникающие при произвольной расстановке 8 угловых маленьких кубков по вершинам волшебного куба и 12 средних — по ребрам, его состояниеми. Центральные кубики во всех состояниях расположены одинаково — так же, как в нулевом состоянии, когда каждой граны волшебного кубика оказывается законным, то есть можно ли, собрав маленькие кубики в произвольном порядке, получить затем нулевое состояние поворотами граней? Если нет, то как узнать, законно ли данное состояние и вообще, связанные ли два данных состояния? Сколько существует законных

*) «Квант», 1980, № 12, с. 17; 1982, № 3, с. 20 и № 7, с. 22; см. также «Нуука и жизнь», 1981, № 3, с. 131 и 1982, № 2, с. 97.

23

Рис. 1. Нулевое состояние. Скрытий угловой кубик имеет номер 9, скрытие средние — номера 10, 11, 12. На скрыты ребрах стрелки сопправлены со стрелками на симметричных им относительной центра куба ребрах.

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

Как задавать состояние

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

Представим, что волшебный кубик находится в нулевом состоянии. Перенумерем его вершины и находящиеся в них угловые кубики числами от 1 до 8, а ребра и соответствующие средние кубики — числа от 1 до 12. Кроме того, на каждом ребре волшебного куба выберем определенное направление (мысленно на рис. 1) и на рисунем стрелку того же направления на соответствующем среднем кубике (рис. 1).

Тепер местонахождение $i$-го углового ($j$-го среднего) кубика в состоянии $S$ можно задать номером $\sigma_s(i)(\tau_s(j))$ той вершины (того ребра), где он находится (здесь $i=1$, …, 8, $j=1$, …, 12).

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

синний, а нижний — зеленьй*). Каждый угловой кубик имеет либо одну грань синего цвета, либо одну грань зеленного цвета; угол $\alpha(\alpha=0^\circ, 120^\circ$ или $240^\circ)$, на котором следует этот кубик в его «гнезде» вокруг диагонали большого куба против часовий стрелки**), чтобы эта (синяя либо зелена) грань стала горизонтальной, будем называть уелом поворота данного углового кубика в состоянии $S$ и обозначать $\alpha_s(i)$, где $i$ — номер кубика.

Оrientation $j$-го среднего кубика в состоянии $S$ заданным углом $\beta_s(j)$ между направлением на нем стрелкой и направлением ребра, на котором он находится ($\tau_s(j)$-го ребра). Угол $\beta_s(j)$ может равнять $0^\circ$ или $180^\circ$; будем называть его уелом поворота $j$-го среднего кубика в состоянии $S$.

Что общего у связанных состояний

Нам надо выяснить, в каком случае два состояния связанных друг с другом. С этой целью проследим, как изменяются характеристики состояния $\alpha_s, \beta_s, \sigma_s$ и $\tau_s$ при поворотах граней. Начнем с угловой поворотов. Легко проверить, что

А. Углы поворотов угловых кубков не изменяются при поворотах четырех вертикальных граней на $180^\circ$ и при произвольных поворотах горизонтальных граней.

В. Углы поворотов средних кубков не изменяются при поворотах двух противоположных (правой илевой на рис. 1) граней на $180^\circ$ и при произвольных поворотах对立ных граней.

В. При повороте любой вертикальной грани на $\pm 90^\circ$ к углам поворотов $\alpha_s$ двух кубков, стоящих в ее противоположных вершинах, добавляется по $120^\circ***$), а к углам

*) Между прочит, кубик раскрашивают по-разному. Мы имеем в виду куб, у которой зелена и синяя грани противоположны.

**) Разумеется, не разушая волшебный куб, реализно повернуть его угловой кубик в своей гнезде нельзя — мы здесь определяем теоретическое понятие.

***) Как это принято, углы поворотов мы складываем с точностью до $360^\circ$, например $240^\circ + 240^\circ = 120^\circ, 180^\circ + 180^\circ = 0^\circ$ и т. д.

24

Рис. 2. После поворота правой грани на 90° по часовой стрелке. Здесь $\tau(1)=2$, $\tau(4)=1$, $\tau(2)=3$, $\alpha(1)=\alpha(3)=120^\circ$, $\alpha(2)=\alpha(4)=240^\circ$, $\beta(1)=\beta(2)=\beta(3)=\beta(4)=180^\circ$.

поворотов двух ее других угловых кубков добавляется по 240°.

Г. При повороте правой или левой (рис. 2) грани на ±90° меняются углы поворотов всех четырех средних кубков этой грани.

Отсюда немедленно вытекает, что суммы углов поворотов всех угловых и всех средних кубков

$$A(S) = \alpha_S(1) + \alpha_S(2) + \ldots + \alpha_S(8),$$
$$B(S) = \beta_S(1) + \beta_S(2) + \ldots + \beta_S(12)$$
остаются постоянными при всех поворотах граней. Такие характеристики состояния называются инварантами (от латинского «не изменяющийся»). Значения любого инваранта для двух связанных состояний $S_1$ и $S_2$, очевидно, совпадают. Поэтому равенства $A(S_1) = A(S_2)$ и $B(S_1) = B(S_2)$ являются необходимыми условиями связанности состояний. Вскоре мы увидим, что, присоединив к ним аналогичное равенство для еще одного инваранта, мы получим и достаточно условия. Но, прежде чем определить этот третий инварант, нам предется сделать небольшое отсутствие

О перестановках

Перестановкой конечного множества называется любое отображение этого множества на себя. Таким образом, определенная выше функция $\sigma_S$, заданная на множестве {1, …, 8}, является перестановкой этого множества, а $\tau_S$ — перестановка множества {1, …, 12}. С любой операцией $F$ также связаны две перестановки $\sigma_F$ и $\tau_F$ этих же множества: если нулевое состояние $S_0$ переводится операцией $F$ в состояние $S$, то, по определению, $\sigma_F(i) = \sigma_S(i)$, $\tau_F(j) = \tau_S(j)$. Другими словами, $\sigma_F(i)$ и $\tau_F(j)$ — это номера тех мест (см. рис. 1), которые занимают в результате операции $F$ угловой кубик, стоящий на $i$-м месте, и средний кубик, стоящий на $j$-м месте.

Выполнить одну за другой перестановки $\sigma_1$ и $\sigma_2$ одного и того же множества, мы снова получим его отображение на себя — перестановку $\sigma$. Она называется композицией $\sigma_1$ и $\sigma_2$: $\sigma = \sigma_1 \circ \sigma_2$.

Задача 2. Пусть операция $F$ переводит волшебный кубик из состояния $S'$. Докажите, что $\sigma_S' = \sigma_S \circ \sigma_F$, $\tau_S' = \tau_S \circ \tau_F$. Докажите также, что $\sigma_{F_1} \circ F_2 = \sigma_{F_1} \circ \sigma_F, \tau_{F_1} \circ F_1 = \tau_{F_1} \circ \tau_F$, где $F_1 \circ F_2$ — композиция операций $F_1$ и $F_2$.

Пусть $\sigma$ — произвольная перестановка множества {1, 2, …, $n$}. Нарисуем одну под другой две строчки по $n$ точек. Если при перестановке $\sigma$ число $i$ переходит в $j$, соединим $i$-ю точку верхней строки отрезком с $j$-й точкой нижней строки — мы получим граф перестановки $\sigma$ (рис. 3). Обозначим через $N(\sigma)$ число точки пересечения отрезков графа (точку, в которой пересекается больше двух отрезков, сосчитаем столько раз, сколько пар отрезков ее содержит). Перестановка $\sigma$ называется четной (нечетной), если

26

грань выбранного среднего кубика белой наклейкой, а белую — синей. Получим состояние $S_1^1$. Переведем его в $S_2^1$ и симметм наклейки — получится состояние $S_2^1$. Следовательно, состояние $S_1$ и $S_2$ связаны. Аналогично доказывается, что любые два состояния с одинаковыми инвариантами связаны. Таким образом, каждый из $3 \times 2 \times 2 = 12$ наборов значений инвариантов $A$, $B$ и $E$ (А принимает три значения: $0^\circ$, $120^\circ$ и $240^\circ$, $B$ — два: $0^\circ$ и $180^\circ$, $\varepsilon$ — тоже два: 1 и —1) определяет класс попарно связанных состояния с этим набором инвариантов, причем состояние из разных классов не связаны; один из классов образован законными состояниями.

Задача 4. Докажите, что число состояний во всех классах одинаково и равно $8! \cdot 3^8 \cdot 11! \cdot 2^{12}$.

Задача 5. Докажите, что значения инвариантов $A$, $B$, $\varepsilon$ зависит только от состояния волшебного кубика, но не от выбора пары граней, направленной на ребрах и нумерации вершин и ребер.

Рекордный алгоритм

В журнале «Сайентифик Америкэн» (1981 г., № 3) описана общая идеяrekordно короткого алгоритма волшебного кубика, приуманного английским математиком M. Тистлетуэйтом. Получясь этим алгоритмом, можно перейти от любого законного состояния к нулевому не более, чем за 52 хода*). Алгоритм Тистлетуэйта коренным образом отличается от алгоритмов, которые описаны в упомянутых нами выше статьях. В общих чертах его схема такова.

Введем три ограничения на допустимые повороты граней:

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

Обозначим через $\Phi_1$, $\Phi_2$, $\Phi_3$ совокупность всех операций, удовлетворяющих соответствию (например, $\Phi_3$ — это всевозможные последовательности поворотов граней на

*) В том же журнале сообщается, что в действительности всегда достаточно 23 ходов (!), причем уменьшить это число нельзя. Судя по всему, пока столбок короткий реализый алгоритм решия кубика не найден.

180°), а через $\Sigma_1$, $\Sigma_2$, $\Sigma_3$ — класс всех состояний, получаемых из нулевого операции из $\Phi_1$, $\Phi_2$, $\Phi_3$. Ясно, что $\Sigma_1 \supset \Sigma_2 \supset \Sigma_3 \supset S_0$ и что любые два состояния из класса $\Sigma_k$ связаны друг с другом операцией из $\Phi_k$. Весь алгоритм разбивает на четыре этапа. На первом выполняется такая операция $F$ (без ограничений на ходы), которая переводит исходное состояние $S$ в какое-нибудь состояние $S_1 \in \Sigma_1$. В дальнейшем разшагются только операции из $\Phi_1$. На втором этап с помощью операции $F_1 \in \Phi_1$ выполняется в состояние $S_2 \in \Sigma_2$, на третьем с помощью операции $F_2 \in \Phi_2$ — в состояние $S_3 \in \Sigma_3$. Наконец, на четвертом этап, вращая грани только на 180°, мы должны получить из состояния $S_3$ нулевое состояние $S_0$.

Очевидно, попав после очередного этапа в класс $\Sigma_k$, мы его уже не покидаем, так что достижения всех предыдущих этапов сохраняются автоматически. Кроме того, вплоть до последнего этапа не нужно «загорать» маленькие места. Но основное достоинство этой схемы в том, что она городадо лучше обчувных приспособления к просчету на ЭВМ. Веряно, это и сыграло решающего роль при «установлении мирового рекорда».

Прежде, чем составлять по этой схеме алгоритм, надо выяснить, что из себя представляют классы состояния $\Sigma_1$, $\Sigma_2$, $\Sigma_3$. Тут-то нам и пригодятся инварианты. С классами $\Sigma_1$ и $\Sigma_2$ разобраться легко. Вспомним свойства $A$ и $B$ углов поворотов маленьких кубков, мы видим, что улыб повторных средних кубков $\beta_S(j)$ инвариантных относительной операции из $\Phi_1$ (свойство $B$), улыб повторных угловых кубков $a_S(i)$ инвариантных относительной операции из $\Phi_2$ (свойство $A$). Легко заметить также, что при операциях из $\Phi_2$ четыре средних кубика, расположенных в горизонтальном «среднем слое» между вершней и нижней гранями, могут меняться местами только между собой, так что состав этого слое остается неизменным.

Задача 6. Докажите, что величины $A(S)$, $\varepsilon(S)$ и $\beta_j(S)$ (j=1, …, 12) образуют полную систему инвариантов относительной операции из $\Phi_1$, а $\varepsilon(S)$, $\alpha_i(S)$ (i=1, …, 8), $\beta_j(S)$ (j=1, …, 12) и состав горизонтального среднего слое — относительной операции из $\Phi_2$.

Столь же просто убедиться, что при операциях из $\Phi_3$, кроме инвариантов, перечислены в задание 6, сохраняются также составы двух вертикальных средних слоев и составы двух четверок угловых кубков, образующих правильные тетраэды (на рис. 1 в одну

27

из них входят угловые кубики 1, 3, 5, 7, а в другой — 2, 4, 6, 8). Но это еще не все! Имеется еще один инвариант относительно набора операций $\Phi_3$, описывающий зависимость между перестановками угловых кубков внутри четверок. Возьмем любые два кубика одной из четверок. Они прилежаатровно к одной из граней куба. Если это права или левая грань, то скажем, что эти кубики занимают 1-ю позицию, если передняя или задняя — то 2-ю, если верхняя или нижняя — то 3-ю. Ясно, что вторая пара кубков этой четверки всегда занимает ту же позицию, что и первый. Для простоты ограничения состояниями $S$, у которых состав четверок «правильный» (как в нульевом состоянии). Расмотрим первый четверку и определим перестановку $p_S$ множество {1, 2, 3}, полагая $p_S(i) = j$, если пара кубков этой четверки, занимающая i-ю позицию в состоянии $S_0$, занимает j-ю позицию в состоянии $S$. Аналогично, для второй четверки определим перестановку $q_S$. Наш последний инвариант — это перестановка $\delta_S = p_S \cdot q_S^{-1}$). Он может принимать любое из 3!=6 значений.

Задача 7. Докажите, что $\delta_S$ действительно инвариант относительно $\Phi_3$ и что вместе с инвариантами, перечисленных выше, он образует полную систему для $\Phi_3$.

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

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

Понграмм в другие игры

Далее неискшенные в математике люди сразу признают в волшебном кубике «родственника» замененной головоломки «15» Сэма Лойда, хотя внешне они совершенно не похожи. Сходство заключено в общей структуре этих игры, которое можно описать так: имеется некая система, способная孵ать в различных состояниях, среди которых одно («нулевое») состояние выделено. Задча состоит в том, чтобы перевести произвольное заданное состояние в нульевое, пользовясь определенным набором стандартных преобразований системы (в случае волшебного кубика — поворотами граней на $\pm 90^\circ$ или $180^\circ$), которые можно назвать элементарными операциями или ходами. При этом любой ход обратим (то есть, сделав его, мы всегда можем одним ходом вернуться в исходное состояние).

Так же, как и для волшебного кубика, в общем случае определяются понятия операции, связанных с состояниями, инварианта. Еще одно полезное понятие — орбита состояния: так называют множество всех состояния, связанных с данным. В частности, как мы видели, множество состояния волшебного кубика распадается на 12 орбит.

Мы предлагаем читателю ряд задач, посвященных исследованию игрузанного типа. В задачах 8—10 требуется доказать некоторые общие свойства этих игры (приводятся только их формулировки). В задачах 11—16 рассматриваются различные примеры, причем дает только описание игры, а ответить нужно на следующие вопросы: 1) каков полный набор инвариантов данной игры? 2) как перевести одно из двух связанных состояния в другое? 3) каково число орбит и состояния в одной орбите?

Задание 8.

8. Будем писать $S_1 \approx S_2$, если состояния $S_1$ и $S_2$ связаны. Тогда для любых состояния $S_1, S_2, S_3$ 1) $S_1 \approx S_1, 2) S_1 \approx S_2 \Rightarrow S_2 \approx S_1, 3) S_1 \approx S_2, S_2 \approx S_3 \Rightarrow S_1 \approx S_3$. Другими словами, отношение $S_1 \approx S_2$ есть отношение эквивалентности.

9. Орбиты любых двух состояния $S_1$ и $S_2$ либо совпадают (если $S_1 \approx S_2$), либо не имеют общих элементов.

10. Если всякая операция, переводящая в себя хотя бы одно состояние, переводит в себя и любое другое состояние, то число $N_0$ состояние во всех орбитах одинаково, а число всех состояния $N = N_0 \cdot k$, где $k$ — число орбит. Проверьте, что указанное свойства операции справедливо для волшебного кубика.

11. Исследуйте игры, отличующие от «волшебного кубика» только набор элементов операций: 1) разрешено врашать только 2 (3, 4 или 5) грани; 2) ход — это поворот пары противоположных граней (одной по, а другой против часовой стрелки) на один и тот же угол; 3) соответствен, обе грани по часовой стрелке.

(Окончание см. на с. 48)