Ломаем систему: что нужно сделать, чтобы полностью перемешать поверхность кубика Рубика?

[joyfull]

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

С большой вероятностью каждый из нас как минимум держал в руках, как максимум – пытался его собрать. Это известная во всем мире трехмерная головоломка, цель которой – упорядочить цветные квадратики так, чтобы грани стали одного цвета, что редко удается новичкам. Естественно, время сборки зависит от опыта игрока, и на сегодняшний день рекорд составляет 4 секунды! И несмотря на то, что собрать кубик, в наших глазах, – трудная задача, доцент кафедры математики в университете Монаша (Австралия) Тим Гарони утверждает, что перетасовать его поверхность куда сложнее. Мы предлагаем разобраться в этом вопросе.

 

Многие ученые всерьез изучали вопрос перемешивания, но чаще всего на примере игральных карт. Например, профессора математики Дейв Бэйер из Колумбийского университета и Перси Диаконис из Гарварда даже опубликовали в 90-х годах научное исследование, которое посвятили изучению распространенного метода перетасовки игральных карт и вывели формулу их случайного смешивания, тем самым сделав значительный вклад в развитие .

 ^Wikipedia

По словам ученых, «рифленая тасовка – один из самых действенных способов максимально непредсказуемого распределения карт». То есть колода карт считается хорошо перемешанной, если порядок расположения карт является непредсказуемым, причем каждое возможное положение имеет одинаковую вероятность появления. А для того чтобы добиться нужного результата, необходимо повторить процесс перемешивания 7 раз.

 

А сколько поворотов граней требуется для того, чтобы полностью перемешать (скремблировать) кубик Рубика?

 

Число различных конфигураций кубика Рубика оценивается числом из 20 цифр – 4325 2003 274489856000. Несмотря на ужасающие данные, все же в 2010 году было доказано, что .

 

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

 

Согласно Гарони, механизм кубика Рубика может быть объяснен стохастической моделью – . Простыми словами, суть модели состоит в следующем: в условиях фиксированного настоящего будущее не зависит от прошлого (вероятность того, каким будет следующее состояние, не зависит ни от одного из предыдущих состояний). Грани в головоломке можно вращать только по трем осям – X, Y и Z – на 90, 180 или 270 градусов.

Применяя теорию цепей Маркова, можно сказать, что с увеличением числа случайных ходов – поворотов граней – вероятность квадратов оказаться в каком-либо конкретном из возможных состояний составляет 1 к 4325 2003 274489856000. Математики называют это «равномерным распределением вероятностей», поскольку каждое из состояний возникает с одинаковой вероятностью.

 

Используя метод Монте-Карло цепи Маркова, с помощью алгоритма все же можно вычислить количество перетасовки, необходимой для скремблирования кубика. Но и здесь есть загвоздка: применение указанного метода для стандартного кубика Рубика 3х3х3 требует слишком больших и сложных вычислений.

^flickr.com

Поэтому до сих пор этот вопрос остается нерешенным. Гарони предлагает использовать «карманную» версию головоломки размерами 2х2х2. В этом случае ситуация несколько проще: общее число конфигураций составляет 3674160, а «число Бога» равно 11.

 

На графике ниже показано распределение вероятностей перетасовки карманного кубика с помощью моделирования. Значение t на горизонтальной оси – это число манипуляций с гранями, а d(t) на вертикальной оси означает, «насколько далеко мы находимся от поставленной цели (полного непредсказуемого перемешивания поверхности). То есть чем меньше значение d(t), тем больше поверхность «перемешивается».

Показатель «хорошей перетасовки» появляется, когда d(t) имеет значение ниже 0,25, а t равно 19. Проще говоря, если вы повернете грани менее 19 раз, это будет означать, что карманный кубик Рубика перетасован не очень хорошо. Также стоит отметить, что с увеличением числа ходов распределение вероятностей становится более равномерным. Можно увидеть, что значение d(t) составляет 0,092 при количестве ходов в 25 раз, 0,0012 – при 50 разах и 0,00000017 – при повороте граней 100 раз.

 

В общем, если вам все-таки удалось перемешать свой кубик Рубика и опередить математиков всего мира, все что вам остается сделать – это снова его собрать.

Смотрите также

^{Обложка: Олава Аренса Рётне / Unsplash}