Представьте что перед вами лежат остов и 20 кубиков. Ваши действия?
![Собери меня полностью! Собери меня полностью!](https://habrastorage.org/getpro/habr/upload_files/818/685/751/8186857518cd273894261dd628e55bc2.jpeg)
Это же не выпавшие кнопки на клавиатуре, которые можно поставить на место с закрытыми глазами. С кубиком Эрнё Рубика нужно быть осторожным. Проблема в том, что не любая конфигурация этой головоломки собирается в идеальное состояние.
![](https://habrastorage.org/getpro/habr/upload_files/7ad/356/a20/7ad356a202c4e4aa4ba4cfc990ecd43b.png)
Если отец научил вас собирать кубик-рубика, то вы должны знать, что, например, поворот одного уголка невозможно отменить простым вращением граней. Инверсию бокового кубика тоже нельзя исправить без разборки кубика на запчасти.
А всё потому, что в кубике Рубика всё взаимосвязано. Самый простой способ сказать, возможно ли случайно выбранную раскраску превратить в правильный кубик-рубика, это начать собирать его. Обычно на этапе сборки третьего слоя вылезают все проблемы: либо уголок невозможно поставить в нужное место, либо боковой куб не хочет поворачиваться правильной стороной, либо не получается развернуть уголки.
А можно ли определить правильность расстановки деталей не собирая кубик целиком? Должны же быть подходящие математические критерии! Этим вопросом задавались уже в первых научных исследованиях кубика-рубика. И подходщая теорема под пафосным названием "Фундаментальная теорема Кубологии" ("The Fundamental Theorem of Cubology") была сформулирована и успешно доказана учёной Anne Scott (впервые опубликована в книге "Winning Ways for Your Mathematical Plays, Vol. 4" в 1982 году).
Фундаментальная теорема кубологии
Можно сформулировать используя строгие математические выражения:
Позиционный вектор соответствует корректной конфигурации кубика-рубика тогда и только тогда, когда выполняются три условия:
(a)
(b)
(c)
Если говорить нормальным языком — существует последовательность шагов, которая переводит начальный кубик-рубика в данную конфигурацию, тогда и только тогда, когда выполняются три условия:
(a) Количество инверсий перестановки углов и рёбер делится на 2
(b) количество углов повёрнутых по часовой стрелке совпадает с количеством углов повёрнутых против часовой стрелки по модулю 3
(c) количество поворотов рёбер чётное
Одно из доказательств этой теоремы можно найти в книге "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) для каждой стороны уголков введём числовое обозначение как на картинке слева:
![Инвариант углов Инвариант углов](https://habrastorage.org/getpro/habr/upload_files/e67/11a/549/e6711a54997ae7f3b2b64b659768a239.png)
Теперь для конфигурации кубика-рубика справа сумма цифр на двух противоположных гранях должна делиться на 3 (инвариант углов). Например на левой и правой гранях сумма чисел равна 9. На передней и тыльной сторонах — 3.
Для проверки условия (c) каждое ребро пронумеруем как на картинке слева. Сумма цифр на всех подсвеченных голубых квадратах должна делиться на 2 (инвариант рёбер).
![Инвариант рёбер Инвариант рёбер](https://habrastorage.org/getpro/habr/upload_files/766/f0e/2a9/766f0e2a91c187359706cf0ec706e9bf.png)
Любой поворот граней чудесным образом сохраняет инварианты углов и граней. Это как раз доказывается в Фундаментальной теореме Кубологии.
Для подсчёта инверсий в перестановках углов из условия (a) пронумеруем произвольным образом кубики в начальном состоянии. Например, как на картинке:
![Нумерация угловых ячеек Нумерация угловых ячеек](https://habrastorage.org/getpro/habr/upload_files/70c/d76/e90/70cd76e90397451ffa993bdbcf799a4c.png)
Теперь для каждой ячейки нашей конкретной конфигурации найдём номер кубика, который эту ячейку занимает.
![Перестановка угловых кубиков Перестановка угловых кубиков](https://habrastorage.org/getpro/habr/upload_files/529/1e2/6ce/5291e26ce1b73327b6fcd792c2476abc.png)
То есть, в первой ячейке стоит кубик под номер 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 инверсия.
![Перестановка рёбер Перестановка рёбер](https://habrastorage.org/getpro/habr/upload_files/199/fe8/4dc/199fe84dcb58f55edf013e1892622f5b.png)
Чётность инверсий рёбер и углов вышла одинаковая: . А значит кубик-рубика на правой картинке таки можно собрать.
Ну и какая польза?
![](https://habrastorage.org/getpro/habr/upload_files/dc6/597/51c/dc659751ce15b54c930881533d5ec4f0.jpeg)
Первое же применение теореме нашлось в вопросе: "Сколько существует верных конфигураций?" Общее количество конфигураций подсчитывается просто:
Всего перестановок углов:
Количество поворотов всех углов:
Всего перестановок рёбер:
Количество поворотов всех рёбер:
Количество всех конфигураций:
Фундаментальная теорема утверждает, что инвариант углов должен делиться на 3, инвариант рёбер должен делиться на 2, а суммарное количество инверсий углов и рёбер должно быть чётным. Следовательно из всего многообразия комбинаций только одна конфигурация из двенадцати (3⨉2⨉2=12) является верной.
![](https://habrastorage.org/getpro/habr/upload_files/458/91d/02c/45891d02cb27a40a7818f243eed0ae10.png)
Какая же польза нам, обычным любителям кубика-рубика? Я, например, наконец-то понял, почему невозможен вот такой рисунок на кубике.
Ведь среди уголков должно произойти две перестановки, что не меняет чётность инверсий. В то время как у рёбер наблюдается только одна перестановка, которая поменяла чётность рёберных инверсий. Другими словами, условие (a) в Фундаментальной теореме не выполняется.
А ещё если хотите собрать какой-нибудь рисунок на гранях, но не знаете какие цвета выбрать, то на помощь приходят критерии из Фундаментальной теоремы Кубологии. Достаточно перебрать вариантов расстановки цветов, чтобы найти среди них допустимые.
![](https://habrastorage.org/getpro/habr/upload_files/53f/5f5/276/53f5f527665cbad5a0a2f3c0ad424515.png)
Литература
Англоязычной литературы по кубику-рубика очень много. Первые книги начали появлятся уже в начале 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 год.
Комментарии (5)
valemak
23.12.2021 16:45+1Поскольку центры (в отличие от граней и уголков) жёстко зафиксированы, то по ним нужно ориентировать остальные двух- и трёх-цветные детальки. Всё.
sheknitrtch Автор
23.12.2021 17:00+2С таким подходом не придумать Фундаментальную теорему Кубологии!
А вообще, разломанный кубик-рубика — это лишь повод, чтобы поговорить про математику ????
iingvaar
24.12.2021 07:41Аааа! Зачем вы используете римские числа? Любое их появление в тексте заставляет мозг останавливаться, вызывать подпрограмму расчета значения и возвращаться в точку останова, мучительно вспоминая векторы прерывания. Только за одно школьное поколение в мире эти вычисления отнимают более 2000 человеко-жизней. Я бы законодательно запретил использование римских чисел. А статья интересная).
LibrarianOok
24.12.2021 16:23Упражняется, значит развивается. Римские цифры — это деньги. А деньги всем нравятся. Особенно — когда они есть. SPQR.
toxa82
Я б его сразу правильно собрал в кучу и всё, без этой дикой математики.