Cтр. 74

Игра в «15»
Поделиться…

Вы высыпали на стол плитки игры в «15», затем уложили их в коробку случайным образом и приготовились играть (будем считать, что «случай» привёл нас к позиции на первом рисунке). По правилам игры плитки вынимать нельзя, а можно лишь передвигать по коробке, пользуясь свободным квадратным полем.

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

Допустим, что, пытаясь собрать позицию, вы получили почти то, что требуется, — на «правильных» местах расположились все плитки, кроме двух: только плитки с номерами 14 и 15 оказались переставленными («почти упорядоченная» позиция).

Оказывается, добавку «почти» нельзя убрать, барьер непреодолим: невозможно перейти из этой «почти упорядоченной» позиции к полностью упорядоченной.

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

Одна из идей, позволяющих доказать неразрешимость задачи, — выявление и использование свойств (характеристик) фигурирующих в ней объектов.

Инвариантом называется свойство объекта, которое не меняется при выполнении определённых преобразований. Если найден инвариант, значения которого для двух объектов не совпадают, то превратить один объект в другой рассматриваемыми преобразованиями не удастся. Иными словами, нахождение инварианта, «различающего» два данных объекта, доказывает неразрешимость задачи превращения одного объекта в другой.

Применительно к нашей задаче про игру в «15» подобный подход подсказывает: надо придумать такую инвариантную (относительно разрешенных движений плиток) характеристику позиции, которая отличалась бы у полностью упорядоченной позиции и у «почти упорядоченной» позиции.

В случае игры в «15» таким инвариантом оказывается чётность суммы двух следующих чисел, $A$ и $B$. Число $А$ — это число пар плиток, в которых плитка с большим номером идёт перед плиткой с меньшим номером. Число $B$ — это номер строки, в которой находится пустое поле. Например, в позиции на первом рисунке пять «неправильных» пар — $(4,2)$, $(4,3)$, $(4,1)$, $(2,1)$, $(3,1)$ — поэтому $A=5$. Число $B$ в этом примере равно 2. Убедимся, что чётность суммы $A+B$ является инвариантом.

Действительно, если игрок передвигает плитку горизонтально, то относительное расположение номеров не меняется, числа $A$ и $B$ тоже не меняются.

Если игрок перемещает плитку вертикально (в соседнюю строку), то оба числа, $A$ и $B$, поменяют чётность. Число $B$ — по определению, так как номер строки изменится на единицу. Чётность $A$ изменится из-за того, что при вертикальном сдвиге плитки её номер «перепрыгивает» через три числа (сдвиг вниз — через последующих, вверх — через предыдущих), а «перепрыгивание» через каждое число изменяет $A$ на $+1$ или на $-1$. Например, в позиции на первом рисунке при сдвиге плитки «3» вниз номер 3 «перепрыгнет» через номера 1, 5 и 6. Из одновременного изменения чётности чисел $A$ и $B$ следует, что чётность суммы $A+B$ не изменится.

Итак, чётность суммы $A+B$ — инвариант. Этот инвариант делит все позиции игры в «15» на два непересекающихся семейства — «чётные» и «нечётные». Теперь у нас появился инструмент «предвидения»: если у позиции данный инвариант — нечётный, то эту позицию упорядочить нельзя, даже пытаться не стоит…

В наших примерах первые две позиции — «нечётные», а третья, полностью упорядоченная — «чётная». Поэтому упорядочить ни первую, ни вторую не удастся.

А вот свести первую позицию ко второй по правилам игры действительно было можно: оказывается, все «нечётные» позиции эквивалентны, сводимы одна к другой. Также эквивалентны между собой и все «чётные» позиции, в частности, любую из них можно упорядочить. Это можно доказать с помощью раздела математики, называемого теорией групп.

Дополнительная информация

  • Другой инвариант (дополнительная иллюстрация) обсуждается в статье из журнала «Квант».

Литература

  • Долгов О. Игра в 15 // Журнал «Квант». 1974. № 2. Стр. 26—33.