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