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

0
14

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

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

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

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

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

 Wikipedia

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

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

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

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

Согласно Гарони, механизм кубика Рубика может быть объяснен стохастической моделью – цепью Маркова. Простыми словами, суть модели состоит в следующем: в условиях фиксированного настоящего будущее не зависит от прошлого (вероятность того, каким будет следующее состояние, не зависит ни от одного из предыдущих состояний). Грани в головоломке можно вращать только по трем осям – 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

ОСТАВЬТЕ ОТВЕТ

Пожалуйста, введите ваш комментарий!
пожалуйста, введите ваше имя здесь