<strong>Насколько сложно собрать кубик Рубика?</strong>

Цзунчжэн Чжоу - научный сотрудник Центра передового опыта в области математических и статистических исследований Австралийского исследовательского совета (ACEMS).

Пикер Го не работает, не консультирует, не владеет акциями или не получает финансирование от какой-либо компании или организации, которые могли бы извлечь выгоду из этой статьи, и не раскрывает никаких соответствующих аффилированных лиц, помимо их академического назначения.

Партнеры

Университет Монаша предоставляет финансирование в качестве партнера-учредителя The Conversation AU.

The Conversation UK получает финансирование от этих организаций.

  • Электронное письмо
  • Твиттер
  • Facebook
  • LinkedIn
  • WhatsApp
  • Посланник

Кубик Рубика был одной из самых любимых головоломок в мире вот уже 40 лет. Для ее решения было разработано несколько различных методов, описанных в бесчисленных книгах. Опытные «спидкуберы» могут решить ее за считанные секунды.

В дополнение к таким подвигам поразительной ловкости, существует множество увлекательных математических вопросов, связанных с кубиком Рубика. Перемещение куба состоит из поворота одной из шести граней на 90, 180 или 270 градусов. Ошеломляющие 43 252 003 274 489 856 000 возможных состояний могут быть получены путем применения последовательностей ходов к решенному состоянию.

Несмотря на эту сложность, в 2010 году было показано, что кубик Рубика всегда можно собрать за 20 или меньше ходов, независимо от начального состояния. Это число называется «числом Бога», поскольку все известные методы решения, используемые людьми, обычно используют значительно больше ходов, чем это оптимальное значение.

Но как насчет противоположного вопроса: сколько ходов нужно, чтобы взломать собранный куб? На первый взгляд это звучит намного проще, чем вычисление числа Бога. В конце концов, в отличие от сборки куба, скремблирование не требует никаких навыков.

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

В прошлом году математики опубликовали аналогичное исследование головоломки 15, которая состоит из квадрата 4х4, заполненного 15 скользящими плитками и одним пустым пространством.

Что значит взбалтывать куб?

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

Применяя теорию цепей Маркова к скремблированию куба, следует, что по мере увеличения количества случайных ходов вероятность нахождения в каком-либо конкретном одном из возможных состояний становится все ближе и ближе к 1 / 43,252,003,274,489,856,000. Математики называют это «равномерным распределением вероятностей», поскольку каждое возможное состояние возникает с одинаковой вероятностью.

После любого заданного количества случайных ходов состояние куба будет случайным, но его распределение вероятностей не будет точно равномерным; некоторые состояния будут более вероятными, чем другие.

Пусть d (t) описывает, насколько распределение вероятностей после t случайных ходов отличается от равномерного распределения вероятностей. По мере увеличения количества случайных ходов ( t ) значение d (t) будет уменьшаться. Перемешиваемый куб соответствует малому значению d (t) .

Марковская цепь Монте-Карло

В теории цепей Маркова это уменьшение d (t) называется «перемешиванием». Помимо тасования карт и скремблирования головоломок, теория перемешивания цепей Маркова также имеет очень серьезные практические приложения. Одним из важнейших вычислительных инструментов современной науки и техники является метод Монте-Карло. Этот метод, как и знаменитое казино, в честь которого он назван, в основном основан на случайности. По сути, он пытается приближенно решать сложные математические задачи, используя несколько случайных догадок.

На практике для создания этих случайных состояний часто используются цепи Маркова. Чтобы понять точность этих методов Монте-Карло с цепями Маркова, ключевая задача состоит в том, чтобы оценить, насколько быстро d (t) уменьшается с увеличением t .

Карманный куб

Изучение проблемы скремблирования для стандартного кубика Рубика 3x3x3 в настоящее время является увлекательной нерешенной задачей. Однако это становится вполне управляемым, если мы обратим наше внимание на меньшую версию 2x2x2, называемую карманным кубом.

В этом кубе отсутствуют края и центральная часть, остались только угловые части. Карманный куб имеет всего 3 674 160 возможных состояний, а его число Бога всего 11.

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

Расстояние распределения карманного куба от равномерного после t перемещений. Эрик Чжоу

Итак, сколько ходов нужно использовать, чтобы полностью схватить карманный кубик? Ответ зависит от того, насколько маленьким вы хотите, чтобы d (t) было. Однако это, безусловно, правда, что количество ходов Бога недостаточно. Как минимум, нельзя использовать менее 19 ходов. Дополнительные сведения, включая код для вычисления d (t) , доступны здесь.

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

ПОПУЛЯРНЫЕ СТАТЬИ