Случайный кубик Рубика

Сколькими способами можно наклеить набор наклеек на поверхность кубика? А сколько всего есть различных состояний «правильного» кубика Рубика?

Предположим, что мы можем различать наклейки одного цвета. Например, можно считать, что они все пронумерованы. Тогда получим 54 уникальные наклейки и 54 места для их приклеивания. Первую наклейку можно поставить на 54 места, вторую наклейку — на 53 места, третью — на 52 места и так далее до последней наклейки. Значит, по правилу умножения число способов наклеить их все на кубик Рубика равно \(54\cdot53\cdot\ldots\cdot2\cdot1=54!\).

Но на самом деле у нас шесть групп одноцветных наклеек по 9 штук в каждой. Это значительно уменьшает число различных способов. Действительно, рассмотрим, например, красные наклейки. Любая перестановка их между собой не изменит раскраску кубика Рубика (наклейки других цветов остаются на своих местах). Значит, все такие перестановки, а их существует 9!, нужно считать как одну. Аналогичное верно и для остальных цветов. Поскольку при оклейке кубика Рубика используются наклейки шести цветов, нужно разделить найденное выше число способов на \((9!)^6\). То есть с учетом того, что не все наклейки разные, получаем \(\frac{54!}{(9!)^6}\) способов оклеить ими кубик.

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

Окончательно получаем, что число всевозможных различных вариантов оклейки кубика равно

Среди этого громадного количества вариантов расположения наклеек есть собираемые и несобираемые. Нас интересует число собираемых.

Как известно, у стандартного кубика Рубика 3×3×3 число всех достижимых состояний равно \(K=8!\cdot3^7\cdot\frac{12!}{2}\cdot2^{11} = 43\,252\,003\,274\,489\,856\,000\).

Здесь есть тонкость. Согласно условию задачи, собранным считается кубик, у которого каждая грань окрашена только в один цвет. Поэтому нужно заметить, что после случайной переклейки наклеек появляется возможность собирать кубики нестандартной раскраски, у которых порядок цветов граней не такой, как у исходного кубика (например, белая грань может оказаться не напротив желтой и т. д.). Из-за этого число различных собираемых вариантов увеличится — во столько раз, сколько существует вариантов раскраски граней кубика шестью цветами. Найдем это число.

Первую грань можно покрасить шестью цветами, вторую грань — пятью цветами, и т. д. Кажется, что число вариантов раскраски равно \(6!=720\). Но надо еще учесть, что раскрашенный куб можно поворачивать в пространстве — от этого раскраска не меняется. Выше мы уже посчитали, что есть 24 способа расположить куб в пространстве так, чтобы он совпал с самим собой без учета раскраски. Значит, количество уникальных способов раскраски граней куба шестью цветами равно \(720:24=30\).

Поэтому число собираемых вариантов равно \(m=30K\), а искомая вероятность равна

Не так уж много!

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

Любопытно, что у нее есть своя история: эту задачу для первой Московской математической олимпиады предложил И. М. Гельфанд — один из крупнейших математиков XX века. Простая, на первый взгляд, задача оказалась весьма трудной для участников олимпиады: ее не решил ни один участник. Видимо, никому не удалось организовать системный перебор вариантов. В ответе лаконично указано, что существует 30 способов. По словам математика В. М. Тихомирова это «задача на все времена», поскольку обладает особой прелестью, в ней запрятано богатое содержание и предлагать ее можно кому угодно.

На рис. 2 наглядно показан процесс получения всех 30 способов раскраски граней куба и приведено дерево вариантов раскраски Т-образных разверток куба.

Рис. 2.

Перебор организован следующим образом. Если одну из граней покрасить, например, красным цветом, то противоположную ей грань можно покрасить одним из пяти оставшихся цветов. В центре рисунка изображены пять таких разверток. В каждом из этих случаев оставшиеся четыре цвета можно распределить шестью (\(1\cdot3\cdot2\cdot1\)) различными способами: третий цвет выбирается однозначно, четвертый цвет выбирается тремя различными способами, пятый цвет выбирается двумя различными способами, шестой цвет определяется однозначно. Таким образом, всего существует \(5\cdot6=30\) различных раскрасок куба. Развертки всех этих кубов расположены на периметре дерева вариантов, имеющего форму правильного пятиугольника.

У основной задачи есть интересный частный случай, в котором не используется переклеивание наклеек. Любители кубика Рубика знают, что нередко происходит непредвиденное: он рассыпается на мелкие составляющие (даже если не пытаться его ломать или разбирать). Из них можно собрать новый кубик 3×3×3, но при этом использовать детали в случайном порядке. Получившийся в итоге кубик будет на вид неотличим от настоящего, разница лишь в том, что его не всегда можно собрать. Возникает все тот же вопрос: какова вероятность собрать кубик Рубика в таком случае?

Рис. 3.

При решении этого варианта задачи надо помнить, что на поверхность кубика Рубика «выходят» единичные кубики трех видов (рис. 4):
    а) Центральные, с одной цветной наклейкой (их 6 штук). При вращении граней эти кубики всегда остаются на месте, потому что они прикручены винтами к крестовине кубика Рубика.
    б) Реберные, с двумя цветными наклейками (их 12 штук). При вращении граней каждый реберный кубик занимает место другого реберного кубика.
    в) Угловые, с тремя цветными наклейками (их 8 штук). При вращении граней каждый угловой кубик занимает место другого углового кубика.

Рис. 4.

Посчитаем число всевозможных различных вариантов сборки этих деталей (единичных кубиков) в форме куба 3×3×3. Центральные кубики уже на месте, потому что они прикручены, а их ориентация не играет роли. Расставить 12 реберных кубиков по 12 местам можно 12! способами, но каждый реберный кубик может в своем месте занимать положение двумя способами (рис. 5), поэтому в каждом из этих способов число комбинаций с учетом поворотов реберных кубиков равно \(2^{12}\).

Рис. 5.

Расставить 8 угловых кубиков по 8 местам можно 8! способами, но каждый угловой кубик может в своем месте занимать положение тремя способами (рис. 6), поэтому в каждом способе число комбинаций с учетом поворотов угловых кубиков равно \(3^{8}\).

Рис. 6.

Поэтому все кубики (12 реберных и 8 угловых) можно расставить \(n=12!\cdot2^{12}\cdot8!\cdot3^8\) способами с учетом возможных разворотов каждого из них в своем «гнезде». Но понятно, что здесь посчитаны как расстановки, позволяющие собрать кубик Рубика по правилам, так и расстановки, которые не позволяют этого сделать.

Но число «собираемых» расстановок у стандартного кубика Рубика 3×3×3 нам известно: оно равно числу всех достижимых различных состояний, то есть \(K=\frac{8!\cdot3^7\cdot12!\cdot2^{11}}{2}\).

Тем самым вероятность сборки кубика Рубика в этом случае получается такой:

Гораздо больше, чем в исходной задаче!

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

Рис. 7.

Разберемся, как устроена эта картинка. Вверху расположен собранный кубик, как одна из возможных ситуаций. Во втором ряду расположены кубики с одной проблемой, из-за которой кубик Рубика не решается. В третьем ряду изображены кубики, в которых совмещены проблемы из кубиков второго ряда. Например, проблемная ситуация №7 получается совмещением простых проблемных ситуаций №2 и №4. Обратите внимание, что проблемные ситуации №2 и №3 несовместимы.

Одним из популярных методов скоростной сборки кубика Рубика является так называемый метод Джессики Фридрих, в котором весь процесс завершается сбором желтой грани и наведением порядка во всем слое с желтой гранью. По расположению трех последних кубиков этого слоя можно рассчитать вероятность сборки рассыпавшегося кубика Рубика совсем просто. Приведу рассуждение спидкубера Ивана Макачёва, участника чемпионата мира по скоростной сборке кубика Рубика. Угловой кубик правильно «садится» в свое гнездо с вероятностью 1/3 (рис. 8, верхний ряд). Реберный кубик правильно «садится» с вероятностью 1/2 (рис. 8, средний ряд). Не вдаваясь в подробности спидкуберской терминологии, скажем, что паритет по перестановке элементов возможен с вероятностью 1/2, поэтому он не попадается тоже с вероятностью 1/2. В итоге получается, что рассыпавшийся кубик, элементы которого случайным образом собраны в кубик 3×3×3, решается с вероятностью \(\frac13\cdot\frac12\cdot\frac12=\frac1{12}\).

Рис. 8.

Можно обсудить еще один вероятностный вопрос: какова вероятность случайно собрать кубик Рубика у необученного человека, если он будет крутить-вертеть кубик, не повторяя позиций?

Ответ на этот вопрос поможет дать число \(K=8!\cdot3^7\cdot\frac{12!}{2}\cdot2^{11} = 43\,252\,003\,274\,489\,856\,000\) всех достижимых различных состояний кубика Рубика 3×3×3. Из этого огромного числа состояний только одно правильное. Значит, вероятность случайной сборки кубика Рубика равна \(\frac1K\approx2{,}3\cdot10^{-20}\). Очень маленькая вероятность: если крутить кубик, например, со скоростью 100 поворотов в секунду, то потребуется порядка \(10^{10}\) лет, чтобы перепробовать все позиции!