sheknitrtch Dec 23 2021 at 11:44

Как собрать кубик Рубика из деталей?

4 min

6.3K

Entertaining tasksAlgorithms*Mathematics*

Представьте что перед вами лежат остов и 20 кубиков. Ваши действия?

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

Если отец научил вас собирать кубик-рубика, то вы должны знать, что, например, поворот одного уголка невозможно отменить простым вращением граней. Инверсию бокового кубика тоже нельзя исправить без разборки кубика на запчасти.
А всё потому, что в кубике Рубика всё взаимосвязано. Самый простой способ сказать, возможно ли случайно выбранную раскраску превратить в правильный кубик-рубика, это начать собирать его. Обычно на этапе сборки третьего слоя вылезают все проблемы: либо уголок невозможно поставить в нужное место, либо боковой куб не хочет поворачиваться правильной стороной, либо не получается развернуть уголки.

А можно ли определить правильность расстановки деталей не собирая кубик целиком? Должны же быть подходящие математические критерии! Этим вопросом задавались уже в первых научных исследованиях кубика-рубика. И подходщая теорема под пафосным названием "Фундаментальная теорема Кубологии" ("The Fundamental Theorem of Cubology") была сформулирована и успешно доказана учёной Anne Scott (впервые опубликована в книге "Winning Ways for Your Mathematical Plays, Vol. 4" в 1982 году).

Фундаментальная теорема кубологии

Можно сформулировать используя строгие математические выражения:

Позиционный вектор $(\rho, \sigma, v, w)\in S_8 \times S_{12} \times C_3^8 \times C_2^{12}$ соответствует корректной конфигурации кубика-рубика тогда и только тогда, когда выполняются три условия:

(a) $sign(\rho)=sign(\sigma)$

(b) $v_1+v_2+...+v_8 = 0 \: (mod \; 3)$

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

(a) Количество инверсий перестановки углов и рёбер делится на 2

(b) количество углов повёрнутых по часовой стрелке совпадает с количеством углов повёрнутых против часовой стрелки по модулю 3

Одно из доказательств этой теоремы можно найти в книге "Mathematics of the Rubik's cube" Associate Professor W. D. Joyner, Spring Semester, 1996-7. Чтобы разобраться в нём потребуются знание теории групп и пространственное воображение.

Как теперь посчитать циклы перестановок деталей (или пермутации этих перестановок)? Как посчитать повороты углов и рёбер? Для этого уже придуманы хитрые инварианты.

Как это всё посчитать с помощью ЭВМ?

Введём обозначения!

Грань — поворачиваемая часть головоломки. Может быть верхней (U), нижней (D), левой (L), правой (R), передней (F), тыльной (B).
Кубик (cubies) — деталь кубика-рубика. Может иметь одну, две или три цветные стороны.
Ячейка (cubicles) — место для кубика в головоломке.
Квадрат (facelet) — цветная сторона кубика.
Конфигурация — конкретное расположение кубиков в головоломке.

Чтобы проверить условие (b) для каждой стороны уголков введём числовое обозначение как на картинке слева:

Теперь для конфигурации кубика-рубика справа сумма цифр на двух противоположных гранях должна делиться на 3 (инвариант углов). Например на левой и правой гранях сумма чисел равна 9. На передней и тыльной сторонах — 3.

Для проверки условия (c) каждое ребро пронумеруем как на картинке слева. Сумма цифр на всех подсвеченных голубых квадратах должна делиться на 2 (инвариант рёбер).

Любой поворот граней чудесным образом сохраняет инварианты углов и граней. Это как раз доказывается в Фундаментальной теореме Кубологии.

Для подсчёта инверсий в перестановках углов из условия (a) пронумеруем произвольным образом кубики в начальном состоянии. Например, как на картинке:

Теперь для каждой ячейки нашей конкретной конфигурации найдём номер кубика, который эту ячейку занимает.

То есть, в первой ячейке стоит кубик под номер 8. Во второй — номер 6. В третьей — номер 5. И т.д. В итоге получится подстановка: 8, 6, 5, 4, 7, 3, 2, 1. Инверсия подстановки — это когда большее число стоит левее чем меньшее. Например 8 стоит перед 3 — это одна инверсия. 6 перед 3 — ещё одна. 7 и 2 — тоже инверсия. Подсчитать количество таких инверсий можно простым двойным циклом. Для данного примера получается 25 инверсий.

Аналогично для рёбер: выбираем нумерацию → определяем номера рёбер в конфигурации → подсчитываем инверсии. Для нашего примера подстановка будет следующая — 12, 10, 9, 3, 8, 5, 2, 1, 4, 7, 6, 11. Итого 41 инверсия.

Чётность инверсий рёбер и углов вышла одинаковая: $41 = 25\:(mod\;2)$ . А значит кубик-рубика на правой картинке таки можно собрать.

Ну и какая польза?

Первое же применение теореме нашлось в вопросе: "Сколько существует верных конфигураций?" Общее количество конфигураций подсчитывается просто:

Всего перестановок углов:
Количество поворотов всех углов:
Всего перестановок рёбер:
Количество поворотов всех рёбер: $2^{12}$

Количество всех конфигураций: $N=8!\times 3^8 \times 12! \times 2^{12}$

Фундаментальная теорема утверждает, что инвариант углов должен делиться на 3, инвариант рёбер должен делиться на 2, а суммарное количество инверсий углов и рёбер должно быть чётным. Следовательно из всего многообразия комбинаций только одна конфигурация из двенадцати (3⨉2⨉2=12) является верной.

$N_{valid}=\frac{8!\times 3^8 \times 12! \times 2^{12}}{12}=43\:252\:003\:274\:489\:856\:000$

Какая же польза нам, обычным любителям кубика-рубика? Я, например, наконец-то понял, почему невозможен вот такой рисунок на кубике.
Ведь среди уголков должно произойти две перестановки, что не меняет чётность инверсий. В то время как у рёбер наблюдается только одна перестановка, которая поменяла чётность рёберных инверсий. Другими словами, условие (a) в Фундаментальной теореме не выполняется.

А ещё если хотите собрать какой-нибудь рисунок на гранях, но не знаете какие цвета выбрать, то на помощь приходят критерии из Фундаментальной теоремы Кубологии. Достаточно перебрать вариантов расстановки цветов, чтобы найти среди них допустимые.

Литература

Англоязычной литературы по кубику-рубика очень много. Первые книги начали появляться уже в начале 80-х. Основоположник кубикологии — британский математик Дэвид Сингмастер.

"Handbook of Cubik Math", Alexander Frey, David Singmaster, 1981
"Notes on Rubik's magic cube", David Singmaster. Enslow Pub Inc, 1981.

Фундаментальное математическое описание головоломки можно найти в книге "Mathematics of the Rubik's cube", W. D. Joyner.

При подготовке статьи мне помогли материалы Jesse Burke из Australian National University.

Из современных изданий можно порекоммендовать курс "Permutation Puzzles: A Mathematical Perspective" от Dr. Jamie Mulholland из Simon Fraser Univevrsity. Есть лекции за 2012 год и за 2021 год.

Tags:

кубик-рубика

Hubs: