Удивительная математика внутри кубика Рубика

Автор оригинала: Dave Linkletter
  • Перевод

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

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


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

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

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

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

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

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

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

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

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

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

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

Здесь кроется ловушка, в которую попадало множество начинающих любителей разгадывать эту головоломку. Если вы тренируетесь и хотите перемешать уже собранный куб, необходимо сохранить куб в целости и собрать его вручную. Если разобрать куб на части и собрать кубики случайным образом, вероятность того, что головоломку можно будет решить, составит всего 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, можно понять, откуда взялась формула (388!)(21212!)/12. Число всех возможных положений кубиков в кубе составляет (388!)(21212!), но только двенадцатая часть таких положений годится для сборки куба. Таким образом, число (388!)(21212!)/12 обозначает количество способов, которыми можно перемешать кубик Рубика, не разбирая его на части.

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

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

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

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

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

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

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

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

 Главной задачей, поставленной изобретателем головоломки, естественно, была сборка куба. Эрно Рубик (Ernő 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%. 

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

Другие профессии и курсы
SkillFactory
Школа Computer Science. Скидка 10% по коду HABR

Комментарии 17

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

    Мне всегда нравилось, как «зазубрить дохрена формул» называют методом). Только это не метод, это всего лишь готовые формулы (хотя ладно, можно назвать модификацией послойной сборки, так как пропускают в начале расстановку углов). А вот ими уже собирают как послойно, так и рух и другие.
    По мне так логически сбирать куда интереснее, чем на скорость, формулы это механическое задрачивание.
    Пляшем от углов и к центру, все формулы находятся сами, точнее видны что надо делать, и прекрасно видна логика действий. А недавно узнал что оказывается не я один так собирал кубик. Причем одинаково собираются что 3х3х3 что 4х4х4 и тд, просто больше времени требуется.
    Метод последовательного приближения / Метод Валерия Морозова

      +1
      В принципе, собирать методом Джессики Фридрих можно и не заучивая наизусть 42 комбинации F2L, 57 комбинаций OLL и 21 комбинацию PLL. Я так и не выучил ни одной формулы, но интуитивно умею собирать Кубик Рубика именно в той последовательности, который предполагается в CFOP.

      1) Крест — ну, если этот этап не получается собрать самостоятельно, то человеку просто не стоит вообще тратить своё время на Кубик Рубика.
      2) F2L — Я думаю, что если аккуратно покрутить движения R и U (и иногда F), то наблюдательный человек заметит, что таким образом можно самостоятельно собрать двойку на нижних двух слоях соответсвующего ребра, не трогая нижние два слоя на других трёх вертикальных рёбрах. И без всяких формул можно с помощью R/U/F аккуратно собрать два слоя на очередном столбике и затем повернуть Кубик Рубика так чтобы можно собрать другой столбик с помощью тех же движений.
      3) OLL — тут фокус в том, что нужно собирать в два подхода. Сначала развернуть вверх уголки (вот тут, кстати, нужно знать простейшую комбинацию, известную как «пиф-паф»), затем вращая только с помощью движений M и U можно развернуть наверх средние квадратики на верхней грани.
      4) PLL — точно также делаем без формул, только на этот раз сначала с помощью M/U средние квадратики расставляем по своим окончательным местам, а затем с помощью прямого и обратного пиф-пафа окончательно решаем уголки.
        +1
        Да я знаю как собирать, я более менее все популярные способы разбирал для себя уже потом. Первые 2 слоя согласен, полностью интуитивно собираются, даже не обязательно начинать с креста. Всем и объяснял через такой вариант.
        3 — пифпафами это прям совсем классика, мне всегда было очень долго и муторно, еще и не очень удобно. Только из за этого стал готовые формулы смотреть для послойного метода, чтоб меньше движений и удобнее.
        Может мне кажется, но в Вашем варианте получается дублирование, сначала расставляем углы в (3), потом во (4), и там и там средние. Тогда уж проще по классике, развернуть центры и воткнуть на места, а потом сразу расставить углы на места и развернуть их.

        Я обычно в (3), так как лень учить формулы делаю крест, а потом R U' L' U R' U' L U и/или зеркальный вариант разворачиваю углы. В самом простом случае (когда надо 3 угла развернуть) надо будет 1 раз сделать, во всех остальных комбинацию из 2х повторений либо одного и того же, либо прямой и зеркальный вариант. Нравится просто потому что двумя руками одинаковые движения в любом случае :)
        а PLL уже через обмен 3мя центральными и/или 3мя угловыми и их комбинации. Т.е. это какое то состояние «пред-Фридрих»)) используются оптимизации но еще даже не PLL не заучен (хотя там меньше всего)

        Но вот способ как в приложенных мной видео куда более интуитивный. Единственное, для многих идет разрыв шаблона, что собирается не слоями. А по факту, в таком варианте, имеем больше степеней свободы на всем процессе сборки.
        К такому же сводится и в Roux, только там собирается два блока противоположных 2х3, а не «столбики» и свободными остаются одна центральная плоскость и одна грань.
          +2
          Да, я владею и методом Меньшова-Морозова (под приведённым Вами видео есть даже мой комментарий 5-летней давности) и методом Ру (который в некоторых этапах очень похож на метод Морозова и тоже при желании собирается сугубо интуитивно, без формул). Отмечу также, что ZZ или Petrus также можно собирать без формул.

          Ещё могу порекомендовать Вам рассмотреть метод Зайцева, если ещё не знакомы.

          У меня есть планы написать серию хабрастатей про безформульные методы сборки, но так пока и не нашёл подходящий способ создания гиф-анимации вращающегося кубика (мне нужно чтобы можно было «подсвечивать» нужные квадратики, а ненужные вообще делать серым цветом, чтобы не мешали понимать суть того или иного движения). В сети нашёл пару джава-скрипт симуляторов, которые вроде бы могут такое, но по разным причинам они не подошли.
            +1
            valemak
            У меня есть планы написать серию хабрастатей про безформульные методы сборки

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

            Хорошо, посмотрю :)
            У меня есть планы написать серию хабрастатей про безформульные методы сборки

            Подпишусь, будет интересно почитать.
            В сети нашёл пару джава-скрипт симуляторов, которые вроде бы могут такое, но по разным причинам они не подошли.

            Этот виджет не смотрели? Единственное, раскрасить его не тривиально(дело практики так то) но примеры можно посомтреть прямо на сайте в алгоритмах.

            UPD: не увидел что он только для 3х3х3. Тогда наверно проще с 3дмаксом заморочиться (да и лучше уж видео чем гифки, и залить их можно на ютуб будет и тут интеграция есть )
        0
        логически сбирать куда интереснее, чем на скорость

        Такая дисциплина тоже есть на чемпионатах, называется Меньшее Количество Ходов (FMC, Fewer Moves Count).

        0
        Разбирать кубик Рубика, конечно, тоже интересно. И математика занимательная.
        Но вспоминается тяжёлое детство и попытки выточить дефицит на токарном станке.
          0
          Кубик на токарном? Может фрезерный?
            +1
            Токарный, делали. Из всей школы получилось только у меня.

            Страшным дефицитом были подходящие заготовки годного материала. Можно и из алюминия, но лучше из оргстекла.

            Ещё из оргстекла делали «плитку Рубика», тоже очень забавная игрушка. Но там совсем просто — и подходящий лист достать нетрудно, и из инструментов достаточно ножовки и пары напильников. А игрушка прикольная.

            А потом и в широкой продаже появились, но такого ажиотажа уже не было.
              0
              Я не слесарь, но со школы помню, что на токарном тела вращения делают. Или, в смысле подвижных частей но нем делали? Крутилки для крестовины?
              Извините за занудство
                +1
                Внимательнее присмотритесь к внутреннему устройству КР. Там нет никаких «крутилок для крестовины». Зато есть очень хитрые «выступы на кубиках» которые — сюрприз!-- после сборки образуют внутри шар. И это ключевая деталь изделия! Вот и сделайте его на фрезерном, да. Тогда как наружные плоские грани можно сформировать и потом, на полученных заготовках с удавшимися частями шарика. Да хоть бы и на шлифовалке. Или сделать «шарик Рубика», такая игрушка тоже существовала

                Увы, видно что не слесарь. А я как раз слесарь, и так получилось что ещё до поступления в ВУЗ «на прибориста» уже успел заработать 5-й разряд (не бог весть что, но шарики точу запросто) на авторемонтном заводе.

                Да, технология производства такая же «хитрая» как и технология «сборки во время игры». И если нет токарного — на фрезерном это сделать гораздо сложнее. Хотя при навыке и можно, только и сам консольный станок должен быть приличным, и впридачу нужно иметь нормальный поворотный столик. Причём вкупе с поворотным столиком получаем что? ага, получаем тот же токарник, только «поставленный на-попа».
                0
                Респект.
                +1
                Именно на токарном. Предполагалось круглый дюралевый пруток зажимать в патроне поперёк и обрабатывать грани, поворачивая на 90°. Ключевая оснастка, которую предстояло также выточить на токарном станке — стальная оправка, с помощью которой кубики зажимались в патроне для последующей обработки.
                Потенциальным приятным следствием самостоятельного изготовления была возможность изготавливать кубики произвольного размера, к примеру в виде брелка на ключи.
                0

                Про вероятность 1к12 не совсем верно, но мне лень пояснять.
                А за статью спасибо. Как же редко в реках новостей попадаются адекватные вещи про моё любимое хобби. :)

                  +1
                  12!/12 = 11!
                  К вопросу о сокращениях формул.
                    +1
                    Гениальная идея для стартапа:
                    Самосборный Кубик Рубика. На моторчиках.
                    раскручиваешь его в любое положение, а он сам собирается.
                    И приложение на тело — показывает счетчик необходимых поворотов (коэффициент Хаоса). С публикацией в соцсетях.

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое