‍Игра в «15»

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

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

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

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

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

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

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

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

В слу­чае игры в «$15$» таким инва­ри­ан­том ока­зы­ва­ется чёт­ность суммы двух сле­дующих чисел, $A$ и $B$. Число $A$ — это число пар пли­ток, в кото­рых плитка с большим номе­ром идёт перед плит­кой с меньшим номе­ром. Число $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$» на два непе­ре­се­кающихся семейства — «чёт­ные» и «нечёт­ные». Теперь у нас появился инструмент «пред­ви­де­ния»: если у позиции дан­ный инва­ри­ант — нечёт­ный, то эту позицию упо­ря­до­чить нельзя, даже пытаться не стоит…

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

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