Божье число: занимательная математика внутри игрушки

В этом году у самой популярной и самой продаваемой игрушки в мире юбилей. Изобретение венгерского архитектора появилось на прилавках магазинов игрушек в далеком 1980 году и с тех пор будоражит умы от мала до велика, от домохозяек до профессоров. Кубик Эрне Рубика собирают на скорость люди и роботы, суперкомпьютеры ищут самый быстрый способ сборки, а математики пытаются разгадать все секреты скрытые внутри с виду простой игрушки. Все потому, что хоть внутренние части кубика сделаны из пластика, его настоящие кишки — самые настоящие числа.

Общее количество комбинаций классического кубика Рубика 3х3х3 — 43 252 003 274 489 856 000. Если выражаться по‑научному, грамотно с точки зрения математики, это число (3⁸8!)(2¹²12!)/12. Вам же все понятно? Вот и мы не сразу сообразили, откуда все эти числа. Давайте разбираться. Первое число из этой формулы — 3⁸. Это количество поворотов каждого из восьми угловых элементов кубика. Всего их восемь, а способов поворота — три. Далее, вертим угловые элементы уже не относительно своего положения, а перемещаем по кубику Рубика. Всего у нас восемь вариантов положений для этих элементов. У первого углового элемента есть восемь вариантов, куда он может встать. У второго осталось семь положений на выбор, у следующего — шесть, и так далее, до последнего, который должен попасть в последний угловой слот. Получается 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1, что по‑научному выглядит так — 8! (восемь факториалов).

Идем дальше. Теперь пришло время дюжины граней. Они имеют только две плоскости, поэтому в общей сложности у них 2¹² вариантов положений. Для них есть 12 мест, куда они могут встать, так что 12! это количество способов, которыми они могут распределиться по местам.

Наши составляющие формулы осталось разделить на 12. Почему? Это очень интересно. Предположим, вы в прямом смысле разломали кубик Рубика, а потом вставили все грани в произвольном порядке, разве что угловые элементы расположили на углах, а грани — на гранях. По идее, перед вами обычный перемешанный кубик Рубика, бери и собирай. Как бы не так! В эту ловушку попался не один начинающий сборщик кубика. На самом деле, если вы разобрали кубик Рубика и собрали его в произвольном порядке, есть только один шанс из 12, что у вас все получится.

Когда в 1980 году куб попал в магазины игрушек, некоторые математики уже несколько лет экспериментировали с ранними версиями. Одним из них был доктор Дэвид Сингмастер, который написал знаменитое руководство по решению кубика Рубика. Самое быстрое время сборки кубика неуклонно сокращалось на протяжении десятилетий. Мировой рекорд человека на данный момент составляет 3,47 секунды. Он принадлежит Юшенгу Ду из Китая. Робот справился с этой задачей быстрее: в 2016 году Sub1 Reloaded сделал это за за 0,637 секунды.

Одной из конфигураций, для которой не удавалось найти короткое решение, был так называемый суперфлип. В этой конфигурации все угловые и реберные элементы находятся на своих местах, но каждый реберный элемент ориентирован противоположно. Математики предположили, что эта конфигурация отдалена от решения кубика Рубика на максимальное количество ходов, суперфлип назвали глобальным максимумумом.

Доктор Морвен Б. Тистлетвэйт в 1981 году доказал, что самое большое число ходов за которые можно решить кубик — 52. В течение 1990-х и 2000-х годов математики не унимались и искали минимальное число Бога. В 2010 году программист из Пало-Альто Томас Рокики, учитель математики из Дармштадта Герберт Коцемба, математик из Кентского университета Морли Дэвидсон и инженер компании Google Inc. Джон Детридж доказали, что кубик Рубика из любого разобранного состояния можно собрать всего за 20 ходов. При этом любой поворот грани считался одним ходом. Объем вычислений составил 35 лет процессорного времени, пожертвованного компанией Google. Технические данные о производительности и количестве компьютеров, участвовавших в исследовании, не разглашаются. Продолжительность вычислений составляла несколько недель.

Источник: Популярная механика