Перейти к содержанию

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


joyfull
 Поделиться

Рекомендуемые сообщения

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

1582275047_25544.jpg

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

 

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

1582275151_544774.jpg

 Wikipedia

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

 

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

 

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

 

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

 

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

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

 

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

1582275162_43969662724_53ae94de28_c.jpg

flickr.com

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

 

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

1582274501_11222222.jpg

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

 

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

Смотрите также
1581495668_1.jpg

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

Ссылка на комментарий
Поделиться на другие сайты

Присоединяйтесь к обсуждению

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

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

 Поделиться