Кубик Рубика — это не только головоломка, но и математическая модель с пространством состояний порядка 43 квинтиллионов конфигураций и богатой симметрией. Из практической задачи создания двусторонних мозаик на кубике у меня возникла идея зеркальных двусторонних инверсивных паттернов (MDSI). В статье я формализую этот тип симметрии и вывожу формулу, позволяющую определить число уникальных паттернов.
Симметрия кубика Рубика
Кубик Рубика – это уникальная математическая модель, а исследование симметрий кубика – довольно увлекательный процесс. Немецкий математик Герберт Коцемба, один из открывателей «Числа Бога» и разработчик двухфазного алгоритма поиска оптимальных решений кубика Рубика посвятил типизации его симметрии несколько лет. Работая нам поиском «числа Бога», Коцемба с соавторами определили 164 604 041 664 возможных симметричных конфигураций кубика Рубика. Затем Коцемба определил 33 типа симметрий на основе перестановок, вращений угловых и реберных элементов куба.
К изучению симметрии кубика Рубика меня привела прикладная задача создания двусторонних рубиккубических мозаик. Я обратил внимание, что для любой комбинации цветов на лицевой грани кубика 3×3×3 можно собрать зеркальную комбинацию в инверсивных цветах на его противоположной грани. В классической расцветке кубик Рубика имеет три пары инверсивных цветов: красный – оранжевый, синий – зеленый, белый – жёлтый. В собранном состоянии грани этих цветов всегда противоположны друг другу, а цветовые пары центральных элементов куба противоположны в любом состоянии куба. Я разработал метод сборки двусторонних паттернов – MDSI (Mirror Dual-Sided Inverse), описание которого приведено в отдельной статье.
Мне удалось обсудить идею MDSI-паттернов с Гербертом Коцембой. Он отметил, что отражение относительно центра куба передней и задней грани и смену цветов можно воспринимать как форму симметрии. Подобные цветовые инверсии реализуются в 11 подгруппах из его списка классификации, поскольку включают точечное отражение через центр куба, но оказываются повернутыми на 180°, как в камере-обскура. По мнению Коцембы, моя симметрия в MDSI-паттернах обладает уникальной особенностью – инверсией цвета и ориентации, которая частично соотносится с определенными симметрическими группами в его программе Cube Explorer, но все же не входит полностью в его формальную классификацию, где под симметриями понимаются структурные перестановки элементов, а не только цветовые инверсии. Тем не менее, тип MDSI можно рассматривать как новую прикладную симметрию, особенно в контексте художественных и визуальных паттернов. Он даже предложил предложил новый термин для MDSI-паттернов, которые, в его системе будут иметь симметрию на всех шести сторонах: Point Mirror Six-Sided Inverse (PMSSI), или «точечные зеркальные шестисторонние инверсивные».
На рис. 1 приведен пример зеркального двустороннего инверсивного паттерна на лицевой и задней гранях кубика Рубика. Цвета элементов других граней могут иметь любой допустимый конструкцией куба цвет и не имеют значения в контексте решаемой задачи сборки двустороннего паттерна для мозаики из кубиков Рубика.
Задача о паттернах
При разработке MDSI-метода для сборки двусторонних мозаик одной из первых задач для меня было определение числа возможных конфигураций зеркальных двусторонних инверсивных (MDSI) паттернов на кубике Рубика.
Далее привожу свое решение.
1. Если учесть все теоретически возможные комбинации всех 54 цветных пикселей на 26 элементах кубика Рубика: 6 центрах, 8 углах и 12 ребрах (без ограничений на паритет* и ориентацию), то получаем общее число:
8 углов: 8! перестановок × 38 ориентаций;
12 рёбер: 12! перестановок × 212 ориентаций;
центры зафиксированы – их не считаем.
* Паритет в состоянии кубика Рубика — это ситуация, когда кубик оказывается в «неправильном» положении с точки зрения математической четности перестановок или ориентаций элементов, из-за чего его невозможно собрать. Паритет может возникнуть в следствие нарушения физической структуры куба и изменения положения его элементов любым механическим способом, кроме разрешенного вращения граней.
2. Однако далеко не все эти комбинации достижимы посредством вращения граней куба, так как его механика накладывает следующие ограничения:
четность перестановки углов и ребер кратна 2;
сумма ориентаций углов кратна 3;
сумма ориентаций ребер четная, то есть кратна 2.
Таким образом, только 1/12 возможных состояний кубика Рубика достижима через легальные вращения при произвольном размешивании – скрамбле (scramble – в спидкубинге означает заранее сгенерированную последовательность вращений граней кубика Рубика, которая используется для случайного перемешивания головоломки перед решением):
Это число всех физически возможных перестановок (разрешенных вращений граней куба), то есть 43 квинтильона легальных состояния кубика.
Таким образом, примерно 92% всех «разобранных» состояний кубика Рубика невозможны для достижения обычными вращениями и не принимаются в расчет при изучении куба.
3. Путем вращения граней куба на одной стороне можно получить любой паттерн из 9 пикселей 6 возможных цветов. Число возможных комбинаций математически составляет 69 = 10 077 696. Однако большинство из этих паттернов не являются уникальными, поскольку подобны по своей структуре при повороте куба на 90° (без вращения граней, когда расположение элементов на грани относительно друг друга не меняется). В общем множестве такие паттерны учитываются по 4 раза. Поэтому число подобных комбинаций следует делить на 4 (тип 4p на рис. 2а).
Кроме того, существуют паттерны, которые при повороте куба дважды повторяют себя. В общем множестве такой паттерн учитывается 2 раза. Поэтому число подобных комбинаций следует делить на 2 (тип 2p на рис. 2б).
Наконец, есть паттерны, которые не изменяются при повороте куба, и каждая комбинация должна учитываться в общем числе (тип 1p на рис. 2в). Тип 1p включает «нулевые паттерны», когда комбинация состоит из пикселей одного цвета, то есть находится в исходном собранном состоянии.
4. Упростив задачу, сначала можно найти число паттернов для комбинаций из двух цветов – например, белого и красного. Центральный элемент на начальном этапе не учитывается, поскольку он не меняет своего положения при повороте паттерна. На финальном этапе полученное число комбинаций необходимо умножить на количество возможных цветов центрального элемента, то есть на 2.
Далее квадрат паттерна 3х3 пикселя раскладывается в линию из 9 элементов, как представлено на рис. 3.
Паттерны типа 1p и 2p всегда симметричны относительно элемента 5 – центра. Поскольку элементы 1, 2, 3 и 4 в паттернах 1p и 2p симметричны элементам 6, 7, 8 и 9, в расчетах можно учитывать только элементы 1, 2, 3 и 4. Каждый элемент может быть только 2 цветов. Для 4 элементов получаем 24 = 16 паттернов типа 1p и 2p (без учета центрального элемента).
Далее следует выяснить, сколько из этих случаев являются паттернами типа 1p. Элементы 1 и 3 – это угловые элементы кубика Рубика, а элементы 2 и 4 – его ребра. Законы вращения граней куба не позволяют реберному элементу превратиться в угловой. Это означает, что паттерны типа 1p удовлетворяют системе равенств:
Чтобы подсчитать количество паттернов 1p, следует отбросить последние два элемента, потому что они копируют первые два. Остаются элементы 1 и 2. Имеются 2 цвета, отсюда 22 = 4 уникальных паттерна типа 1p (без учета центрального элемента).
Число паттернов 2p: 16 – 4 = 12. Паттерны 2p по определению имеют 2 позиции, поэтому существует всего 12/2 = 6 уникальных паттернов типа 2p (без учета центрального элемента).
Далее определяется число возможных паттернов типа 4p. Поскольку центральный элемент не учитывается, остаются 8 элементов и 2 цвета, следовательно 28 = 256 паттернов. Из этого числа вычитается 16 паттернов (1p + 2p): 256 – 16 = 240 паттернов. Чтобы избавиться от повторяемых паттернов, результат делится на 4 и получается 60 уникальных паттернов типа 4p (без учета центрального элемента).
Таким образом, общее число уникальных паттернов всех типов без учета центрального элемента составляет: 4 + 6 + 60 = 70.
Теперь следует возвратится к центральному элементу, который может быть 2 цветов, поэтому 70 умножаем на 2 и получаем 140 уникальных паттернов. Вычисление этого числа можно представить следующим выражением:
Все, что отмечено выше жирным подчеркнутым курсивом, не является константой – это решение конкретно для случая с 2 цветами.
5. Далее вводится функция C(x), которая считает количество паттернов, где х – количество цветов. Количество цветов (в рассмотренном случае 2) меняется на x:
После упрощения получается итоговая формула:
где х – это количество возможных цветов на паттерне.
При х = 6 число полноцветных односторонних паттернов равняется 2 521 476.
Для паттернов из 2 цветов их количество составляет – 140;
из 3 цветов – 4 995 паттернов;
из 4 цветов – 65 824 паттернов;
из 5 цветов – 489 125 паттернов.
Формула работает для любого количества цветов. Если представить четырехмерный кубик Рубика, с 7 гранями (и цветами), то он будет иметь 10 092 775 уникальных паттернов.
6. MDSI-метод позволяет для любого одностороннего паттерна собрать его зеркальное инверсивное отражение на противоположной стороне, поэтому количество односторонних паттернов будет равняется количеству MDSI-паттернов.
Однако множество полноцветных односторонних паттернов включает все возможные паттерны, включая любой противоположный паттерн, который собирается в процессе применения соответствующего алгоритма. Таким образом количество полноцветных уникальных MDSI-паттернов будет вдвое меньше:
Ответ: существует 1 260 738 уникальных MDSI-па��тернов.
