Математики в шоке: Оказывается, разобрать Кубик Рубика – гораздо сложнее, чем его собрать!

Москва, 12:06, 31 Янв 2020, редакция FTimes.ru, автор Сергей Кузнецов.

Кубик Рубика уже 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 ходов.