В прошлом году исполнилось 40 лет с того времени, как человечество узнало о кубике Рубика. Эта головоломка сразу смутила умы почти полумиллиарда энтузиастов, которые полагали, что могут раскрыть сумасшедшие секреты этого удивительного кубика, если разберут его на составные части.

В преддверии юбилея кубика Рубика (да, юбилея!) и стартов новых потоков курсов Математика для Data Science и его расширенной версии Математика и Machine Learning для Data Science, пришло время раз и навсегда разгадать эту головоломку, на этот раз с помощью довольно сложной математики. Физические внутренности кубика могут быть изготовлены из пластика, но его виртуальными внутренностями, конечно же, являются числа. Давайте же окунёмся в этот мир чисел.

Разбор кубика Рубика на блоки

Начнем с базовых знаний. Кубик Рубика размером 3x3x3 имеет шесть граней, каждая своего цвета. Центральный кубик каждой грани прикреплён к внутренней крестовине, скрепляющей все элементы куба. Центральные кубики могут только вращаться вокруг своей оси. Одни и те же цвета всегда располагаются напротив друг друга; на стандартном кубе белый цвет находится напротив жёлтого, красный – напротив оранжевого, синий – напротив зелёного.

Если разобрать кубик Рубика, можно увидеть, что он состоит из трёх типов составных блоков. Первый тип: центральная крестовина, на которой удерживаются центральные кубики каждой грани. Второй тип – маленькие кубики размером 1x1x1. Угловые кубики имеют три цветные стороны, бортовые кубики – две. Кубик Рубика имеет одну крестовину, восемь угловых кубиков и двенадцать бортовых кубиков.

С помощью математики мы можем узнать общее количество способов, которыми можно перемешать кубик Рубика: 43 252 003 274 489 856 000. В виде математической формулы это число можно представить следующим образом: (3⁸8!)(2¹²12!)/12. Вот как получается эта формула.

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

Далее учитываем перемещения каждого углового кубика. Всего угловых пазов восемь, поэтому у первого углового кубика есть восемь вариантов. У второго углового кубика остается семь вариантов, у следующего слева кубика – шесть вариантов и так далее, вплоть до последнего углового кубика, который должен войти в последний угловой паз. Это даёт факториал 8!.

Таким образом, первая часть формулы (3⁸8!) осуществляет подсчёт всех способов, которыми угловые кубики могут размещаться в кубе. Значение 3⁸ – это их ориентация, а 8! – их положение.

В следующей части формулы (2¹²12!) применяется тот же принцип, но теперь для ребер. Рёбра имеют только две ориентации, поэтому 12 рёбер могут иметь в общей сложности 2¹² ориентаций. Всего имеется 12 положений, поэтому 12! представляет собой количество способов, которыми кубики могут быть размещены в таких положениях.

Что ещё осталось в формуле (3⁸8!)(2¹²12!)/12? Осталось деление на 12. Деление на 12 связано с одной особенностью кубика Рубика, о которой многим известно, но которую не до конца её понимают. Проведём мысленный эксперимент (который, возможно, вы уже проводили вживую!):

Предположим, вы разобрали кубик Рубика, вытащили из него все кубики, а затем вставили все кубики обратно в случайные пазы (при этом угловые кубики можно установить только в углы, а бортовые кубики – только на рёбра). Вы получите конструкцию, которая выглядит как обычный перемешанный кубик, и на данный момент мы подсчитали все возможные комбинации созданного таким образом куба: (3⁸8!)(2¹²12!). Теперь зададим вопрос, всегда ли можно собрать такой перемешанный кубик, не разбирая его на части?

Ответ – "нет".

Здесь кроется ловушка, в которую попадало множество начинающих любителей разгадывать эту головоломку. Если вы тренируетесь и хотите перемешать уже собранный куб, необходимо сохранить куб в целости и собрать его вручную. Если разобрать куб на части и собрать кубики случайным образом, вероятность того, что головоломку можно будет решить, составит всего 1 к 12.

Ответ кроется в алгоритмах

Хотите понять, почему вероятность составит всего 1 к 12? Есть хороший визуальный способ понять, почему вероятность именно такая. Шанс собрать разобранный на составные кубики и снова случайным образом перемешанный большой куб будет равен шансам собрать куб со следующими образцами граней:

 Мы разместили их таким образом, чтобы было понятно, как получается коэффициент 12. Ряд 1 имеет нормальные углы. У рядов 2 и 3 один угол повёрнут. Столбец 1 имеет нормальные рёбра. У столбцов 2 и 3 одно ребро повёрнуто. У столбца 3 два ребра поменяны местами. И, наконец, в столбце 4 одно ребро повёрнуто и два ребра поменяны местами.

Таким образом, 12 кубов, представленных выше на фотографиях, не могут быть преобразованы друг в друга. 13-го варианта, который нельзя преобразовать ни в один из таких 12 кубов, не существует. Откуда нам это может быть известно?

Между тем, что может и что не может быть сделано посредством перемещения граней куба, есть связь. Последовательность перемещений граней куба энтузиасты сборки часто называют "алгоритмом". Популярными алгоритмами являются те, которые перемещают лишь несколько кубиков, оставляя остальные нетронутыми. Число 12 возникло по той причине, что на такие алгоритмы накладываются ограничения.

Число 12 составляется из трёх множителей: 12 = 3 * 2 * 2. Откуда берутся множитель 3 и два множителя 2?

Множитель 3: существует алгоритм, который поворачивает каждый из двух разных углов, но нет алгоритма, который поворачивает один угол (оставляя все остальные нетронутыми). Другими словами, если взять обычный кубик Рубика, вынуть один из его углов и заменить его на повёрнутый, такой куб собрать будет невозможно, то есть вы переместитесь из верхнего левого угла нашей диаграммы в одну из клеток прямо под ним.

Однако, если повторить эту операцию и повёрнуть еще один угол, второй множитель 3 не добавится. Теперь, когда в кубе повёрнуто два угла, мы можем последовательно применять алгоритм, поворачивающий два угла, до тех пор, пока не зафиксируется по крайней мере один из углов. Если другой угол случайно встанет на своё место, можем считать, что нам повезло и такой куб можно собрать. Ориентация углов может быть троякой.

Рассуждения относительно первого множителя 2 аналогичны. Существует алгоритм, поворачивающий на свое место каждое из двух разных рёбер, но алгоритма, способного повернуть на своё место только одно ребро, не существует. Таким образом, любое количество повёрнутых ребер может быть сведено к одному ребру, которое в итоге либо окажется, либо не окажется повёрнутым – варианта всего два.

Последний множитель 2 фактически относится к граням и углам, хотя на диаграмме мы показали его с гранями. Существует алгоритм, меняющий местами два угла, одновременно меняя местами два ребра. Но нет ни одного алгоритма, который был бы способен менять местами ни только пару углов, ни только пару рёбер.

Возьмите куб, вытащите два ребра и поменяйте их местами – на диаграмме вы попадёте на столбец, расположенный либо между столбцами 1 и 3, либо между столбцами 2 и 4. Аналогичные рассуждения можно применить, если поменять местами пару углов. Однако перемена местами пары ребер и пары углов уравновешивает баланс, так как алгоритм выхода из таких состояний существует.

Итак, после того как мы объяснили, откуда взялись все множители в коэффициенте 12, можно понять, откуда взялась формула (3⁸8!)(2¹²12!)/12. Число всех возможных положений кубиков в кубе составляет (3⁸8!)(2¹²12!), но только двенадцатая часть таких положений годится для сборки куба. Таким образом, число (3⁸8!)(2¹²12!)/12 обозначает количество способов, которыми можно перемешать кубик Рубика, не разбирая его на части.

Доказательство Популярной механики

Если вы достаточно любопытны, то, наверное, захотите проверить, верны ли сделанные выше утверждения. Существуют ли более сложные математические приемы, которые могут доказать, что "алгоритма, способного повернуть на своё место только один бортовой кубик, не поворачивая любой другой кубик, не существует"? Да, такие математические приёмы существуют. Вот как примерно строится такое математическое доказательство:

При переворачивании грани куба происходит перемещение четырёх бортовых кубиков. Рассмотрим, к примеру, алгоритм из 10 перемещений. Для каждого кубика выполните алгоритм и посчитайте, сколько раз перемещался кубик, и назовите это количество "числом перемещений кубика". Сложите эти числа для каждого бортового кубика, всего должно получиться 40 перемещений кубиков, так как каждое из 10 перемещений добавляет к сумме четверку.

В общем случае для любого алгоритма общее число перемещений бортовых кубиков должно быть кратно 4. Теперь пара важных фактов: если бортовой кубик перемещать чётное количество раз и вернуть его обратно в тот же самый паз, он будет иметь такую же ориентацию. И наоборот, если бортовой кубик перемещать нечётное количество раз и вернуть его обратно в тот же самый паз, он будет иметь перевёрнутую ориентацию.

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

Теперь давайте рассмотрим гипотетический алгоритм, достигающий цели, поворачивающий один бортовой кубик, оставляя при этом в неприкосновенности другой кубик. Одно повёрнутое ребро было перемещено алгоритмом нечётное количество раз, а каждое из 11 остальных рёбер было перемещено чётное количество раз. Сумма 11 чётных чисел и одного нечётного числа всегда нечётна, но мы показали ранее, что такая сумма должна быть кратна 4. Может ли нечётное число быть кратно 4? Нет, не может. Следовательно, такого алгоритма не существует.

Теперь вы понимаете, что число (3⁸8!)(2¹²12!)/12 представляет собой количество возможных состояний куба. Но для изучающего куб математика это лишь предварительная информация. Перед тем как начинать применять более сложные математические методы, задайте себе главный вопрос: "Существуют ли в этой теме математические вопросы, оставшиеся без ответов?"

Число Бога и многое другое

 Главной задачей, поставленной изобретателем головоломки, естественно, была сборка куба. Эрно Рубик (Erno Rubik) создал первый прототип головоломки в 1974 году, и через шесть она поступила в массовую продажу. Естественно, он был первым, которому удалось собрать куб.

В 1980 году кубик Рубика стал хитом продаж в магазинах игрушек. Но некоторые математики уже несколько лет экспериментировали с его ранними версиями. Одним из них был доктор Дэвид Сингмастер (David Singmaster) – составитель знаменитого путеводителя "Записки о Волшебном кубике Рубика" и разработавший нотацию для записи операций поворота граней куба. Эта нотация стала стандартом и теперь известна как нотация Сингмастера.

Если бы это была статья писалась в 1980-х годах, то, возможно, стоило бы подробнее объяснить читателям, что такое нотация Сингмастера, и использовать её при описании алгоритмов сборки куба. Множество авторов статей так и делали. Но сегодня на Youtube выложено множество видеоинструкций, поэтому в этой статье мы не будем отвлекаться на описание нотации.

За последние несколько десятилетий рекорд сборки кубика Рубика на время постоянно обновлялся. На сегодня мировой рекорд сборки кубика Рубика человеком составляет 3,47 секунды. В 1997 году доктор Джессика Фридрих разработала самый известный, самый скоростной и самый гибкий метод быстрой сборки кубика Рубика Самые быстрые сборщики кубика Рубика сегодня пользуются разными вариантами сборки от доктора Фридрих.

По мере того как одни пользователи оттачивали мастерство сборки, другие пытались решать важные математические вопросы, связанные с этой головоломкой. За сколько ходов можно собрать куб независимо от того, в каком состоянии он первоначально находился? Если кто-то перемешал куб за 500 ходов, то, естественно, собрать его можно менее чем за 500 ходов. На насколько именно меньше ходов?

Соответственно, была поставлена главная математическая задача: существует ли магическое число, позволяющее сказать: "любой перемешанный куб может быть собран именно за такое количество ходов [или меньше]"? Благодаря остроумному замечанию, что для обретения чувства уверенности нужно божественное вмешательство, это число получило название "Число Бога".

Первая гипотеза о существовании Числа Бога была выдвинута доктором Морвеном Тистлетвэйтом (Morwen Thistlethwaite) в 1981 году, который доказал, что это число существует и не превышает 52. Другими словами, любой перемешанный куб может быть собран за 52 хода или меньше.

В 1990–2000-х годах математики пошли ещё дальше. В июне 2010 года группа из четырёх учёных доказала, что Число Бога равняется 20. На этом веб-сайте, который ведут эти учёные, представлены самые последние знания о кубике Рубика.

Другими словами, какое бы хаотичное первоначальное состояние ни имел Кубик Рубика, его всегда можно собрать за 20 или менее ходов. 

Для математиков в теме кубика Рубика остались лишь небольшие лакомые кусочки. Число Бога определено и равняется 20. Но точно неизвестно, сколько именно из 43 252 003 274 489 856 000 комбинаций потребуют для сборки полных 20 ходов.

Количество комбинаций, для сборки которых требуется ровно один ход, составляет 18. Это значение легко рассчитать. Есть шесть граней и три способа поворота каждой из них. Сколько кубов можно собрать ровно за два или три хода? Для математиков эта задача сложности не представляет, но можно предположить, что с увеличением количества ходов также будет увеличиваться сложность вычислений. Сегодня математики уже добрались до числа ходов 15; мы точно знаем количество комбинаций, для сборки которых требуется ровно 15 ходов, но пока не вполне точно представляем количество комбинаций для числа ходов от 16 до 20.

И это – последняя нерешённая задача в математической теме кубика Рубика. Будем ждать, когда кто-либо её решит. Может быть, это будете вы?

Получите нужные знания и навыки на курсе Математика для Data Science и его расширенной версии Математика и Machine Learning для Data Science. А промокод HABR даст скидку 50%. 

Узнайте, как прокачаться в других специальностях или освоить их с нуля:

• Профессия Data Scientist

• Профессия Data Analyst

• Курс по Data Engineering