Цель игры в 15 – расположить плитки по порядку. А сейчас математики решили противоположную задачу – как внести в систему беспорядок.
Вы, вероятно, играли в игру в 15. Эта игра бесит, но затягивает; в её коробке 4х4 есть 15 плиток и единственное пустое место. Цель – двигать плитки, размещая их в порядке увеличения цифр, или, как в некоторых вариантах игры, составляя из них изображение.
Игра стала одним из самых популярных подарков с момента изобретения в 1870-х. Она также привлекла внимание математиков, более ста лет изучавших решения подобных головоломок различных размеров и удивительных конфигураций.
Теперь появилось новое доказательство, решающее загадку в обратном порядке. Математики Ян Чу и Роберт Хью из Университета Стони-Брук подсчитали количество ходов, необходимое для превращения упорядоченного игрового поля в беспорядочное.
Задачу о рандомизации игры в 15 сформулировал в 1988 году Перси Дьяконис. Он предположил, что для рандомизации головоломки произвольного размера n понадобится n3 ходов. Поэтому для рандомизации поля 4х4 потребуется 43, или 64 хода, и 1000 ходов для поля 10х10 (хотя такие поля тоже называют «игрой в 15», на других полях может быть любое количество квадратиков, составляющих идеальный квадрат).
Дьяконис, математик из Стэнфордского университета, предположил, что его версия задачи об игре в 15 является частным случаем более крупного класса похожих вопросов рандомизации. Многие из них связаны с фундаментальными особенностями реального мира, к примеру, обмен спаренных оснований в ДНК, приводящий к мутации, или разделение молекул, происходящее при таянии льда.
Поняв задачи о рандомизации игры в 15, Дьяконис надеялся разобраться с тем, как упорядоченные системы в общем случае рассыпаются, приходя в однородно перемешанное состояние.
В таких случаях, как игра в 15, случайность формируется пошагово. Представьте идеально упорядоченное поле, у которого в левом верхнем углу стоит плитка «1», а в правом нижнем находится пустой квадратик. Затем сдвиньте плитки так, чтобы пустое место сдвинулось на одно место в любом из четырёх направлений – вверх, вниз, влево или вправо (для математической элегантности Чу и Хью рассматривали поле с завёрнутыми и встречающимися друг с другом краями, чтобы плитки никогда не застревали в углах). Выбор сделайте случайным образом. Теперь конфигурация поля поменяется, оно уже будет не упорядоченным, но и не сильно беспорядочным. Повторите процесс. Чем больше вы будете двигать пустое место, тем сильнее поле будет отходить от изначальной упорядоченности.
В этом процессе важно то, что на каждом шаге последующая конфигурация поля зависит только от текущей. Это похоже на игру «Монополия» – шансы, бросив кубик, перейти на две клеточки от одного места к другому, не зависят от значений, выпадавших на кубике ранее, и приведших вас туда, где стоит ваша фишка.
Игра в 15 подбирается к беспорядку пошагово. Многие другие системы, такие, как таящий лёд, рандомизируются сходным образом. Математики изучают это явление при помощи моделей под названием «цепи Маркова«. Цепи Маркова – формальный способ изучения любого процесса рандомизации, в котором следующее состояние системы зависит только от текущего. Это передний край математического понимания случайности.
«Они как раз в такой ситуации, когда мы их ещё можем анализировать, и при этом они описывают множество интересных явлений», — сказал Ювал Перес, математик, проделавший важную работу в области теории вероятностей.
В своей новой работе Чу и Хью считали рандомизацию игры в 15 цепью Маркова. В частности, они изучали набор чисел под названием «переходная матрица». Это большой набор чисел, определяющих вероятность того, что игра в 15 перейдёт из одной конфигурации в другую, если вы случайным образом выберете, как подвинуть пустое место.
Разобраться в переходной матрице обязательно для того, чтобы подсчитать количество ходов, необходимое для рандомизации, или смешивания, упорядоченного поля. Точнее, Чу и Хью сконцентрировались на определении множества чисел, характеризующих переходную матрицу – её «собственные значения».
«Когда у вас накопится достаточно информации о собственных значениях, вы сможете получить очень точную информацию о смешивании», — сказал Хью.
В переходной матрице для игры в 15 содержится чрезвычайно большое количество информации, отражающей триллионы различных конфигураций, которые может принять даже поле размера 4х4. Напрямую с таким количеством информации математики не справятся. Поэтому вместо того, чтобы анализировать переходную матрицу на каждом шагу на пути к рандомизации, Чу и Хью поняли, как охарактеризовать среднее поведение переходной матрицы на всём пути.
Такой подход похож на то, как если бы вы захотели узнать, где вы окажетесь на игровом поле в Монополии после 1000 бросков кубика, и либо реально кидали кубик 1000 раз, либо взяли среднее значение от нескольких бросков и провели экстраполяцию.
При помощи этой техники Чу и Хью подсчитали собственные значения переходной матрицы, что и дало им точное количество ходов, необходимых для рандомизации игры в 15. Они даже получили два ответа на основе двух различных определений случайности.
В первом они считали поле рандомизированным, когда каждая плитка с равной вероятностью находится в любом заданном месте поля. По этому определению они обнаружили, что для рандомизации поля n x n понадоибтся n4 шагов (то есть, 256 шагов для поля 4х4 и 10 000 шагов для поля 10х10). Это больше, чем предсказывал Дьяконис (n3).
Второе определение случайности было более строгим. Поле случайно перемешано, когда оно с одинаковой вероятностью находится в одной из множества возможных конфигураций. Они доказали, что для достижения такой рандомизации потребуется чуть больше ходов – но не более n4 log n.
Чу и Хью продемонстрировали, что рандомизировать игру в 15 сложнее, чем предсказывал Дьяконис – что, в каком-то смысле, означает, что стирать порядок из системы приходится дольше, чем ожидалось. Благодаря им теперь игра в 15 принадлежит к относительно небольшому классу задач рандомизации, в которых «количество шагов, необходимых для рандомизации, по сути, известно», — сказал Хью.
Теперь Хью работает с Пересом над расширением доказательства. Среди прочего, их интересует, переходит ли поле в случайное состояние внезапно с увеличением размера поля. Системы с таким поведением сначала не выглядят случайными, а внезапно, после единственного шага, становятся рандомизированными.
«Мы пока не совсем понимаем, какие цепи Маркова демонстрируют такую внезапность, — сказал Перес. – Это одна из величайших загадок данной области».
