Божье число: занимательная математика внутри игрушки
Общее количество комбинаций классического кубика Рубика 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. Технические данные о производительности и количестве компьютеров, участвовавших в исследовании, не разглашаются. Продолжительность вычислений составляла несколько недель.
В 2014 году Томас Рокики и Морли Дэвидсон доказали, что кубик Рубика можно собрать не более чем в 26 ходов без использования поворотов на 180°. Объем вычислений составил 29 лет процессорного времени в суперкомпьютерном центре Огайо.
Если вы думаете, что все математические загадки, связанные с кубиком Рубика, уже давно решены, то это не так. Число комбинаций, для решения которых требуется всего один ход, равно 18. Это легко подсчитать: есть шесть граней и три способа перемещения каждой. Сколько комбинаций находится в двух или трех ходах от решения кубика, математикам не сложно вычислить, но более высокие числа вычислить не так уж и просто. Сегодня мы знаем, сколько существует комбинаций, которые решаются за 15 ходов, осталось найти комбинации для решения которых потребуется от 16 до 20 ходов. Вот вам и игрушка для детей и взрослых.