У меня в руках старинная головоломка, она старше меня лет на 100. Изобретена в конце XIX века. Но её застали и мы, и наши родители. Она гораздо старше, чем кубик Рубика, в который потом играли после неё. Что же это такое? Давайте откроем и поглядим. Это квадратики, которых здесь 15 штук, а мест, естественно, 16. Соответственно, вот это пустое место можно использовать для того, чтобы квадратики передвигать. Задача состоит в том, чтобы из любой позиции прийти в исходную, которую вы сейчас здесь видите, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15. Вот, допустим, я беру, перемешиваю как-нибудь их: сюда, туда-сюда, перевожу их как-то вот так — перемешал. Вот возникла какая-то перемешанная позиция. Ну, вот я думаю некоторое время. Предположим, что я забыл, как именно я ходил, я некоторое время думаю, ну, вот начинаю так, наверное, этот сюда квадратик, этот сюда пошел. Так, этот сюда, так, вот сюда ставим семерочку. Ага, вот! Мы вернулись в исходную позицию. Но если я более долго буду это вот всё перемешивать, то понятно, что возвращаться в исходную позицию будет тоже дольше, и возникает такое умение — умение играть в «пятнашку». Ну, как вот бывают люди, которые очень быстро собирают кубик Рубика. Взяли, раз, и всё — кубик собран. Так же в «пятнашку». Есть профессионалы игры в «пятнашку», в наше время были такие профессионалы, и в общем, им разберешь эту игру, вот так вот квадратики подвигаешь, двигаешь. Они — раз-раз-раз-раз-раз, и буквально за несколько секунд всё возвращается в исходную ситуацию. что, если я все квадратики выкину на стол и потом обратно соберу? Можно и тогда тоже вернуться в исходную позицию? После того как вы некоторое время потренируетесь, вы обнаружите, что если вы соберете квадратики произвольным образом, выкинув предварительно их на стол, то вы придете либо к такой позиции, либо к вот такой. То есть к позиции, в которой 15 и 14 переставлены местами. Вопрос о том, можно ли из вот такой позиции по правилам игры перейти в такую, задал более 100 лет назад один зубной врач. И сказал, что тому, кто научится это делать, он заплатит очень большие деньги. Начался такой бум, целый «пятнашечный» бум, все играли в «пятнашку», все пытались превратить вот такую позицию по правилам игры в ту, в которую они переставлены. Ну понятно, что картинку надо было очень сильно от этого менять, как-то вот так пертурбировать её. И в конце концов складывать, складывать, складывать, чтобы окончательно получилось здесь 13, 14, 15. Но ни у кого ничего не получалось. Потом пришли математики и установили сделать это невозможно. То есть если я поменяю руками 15 и 14 местами, то ни при каком умении игры в «15», сколько бы я ни тренировался, и сколько бы долго я в неё ни играл, я никогда не получу на выходе исходную позицию. И эта теорема не очень простая, но мы её с вами полностью докажем, мы обнаружим то, что математики называют словом «инвариант» — некоторую величину, которая зависит от расположения здесь квадратиков. Может быть определена для любого расположения квадратиков, которое только здесь ни существует в этой коробочке, и величина эта принимает всего два значения. Причем значения эти разные для исходной позиции и для позиции, при которой я поменял эти два квадратика. И что будет установлено — это что в процессе игры, когда вы передвигаете все эти квадратики на доске по разрешенным правилам, эта вот величина не меняется, поэтому и говорят, что она — инвариант. Ну а если так, то значит, действительно, прийти из позиции, в которой эти квадратики поменяны в исходную — невозможно. Для того чтобы это доказать, нам понадобится некоторая подготовительная работа, потому что вот здесь это доказательство достаточно сложное, и нужно привести несколько примеров более простых игр, в которых тоже требуется что-то, что математически невозможно, но установление математической невозможности занимает гораздо меньшее время, ну и как бы оно наглядно следует из свойств игры, почти что сразу. Поэтому мы первым делом познакомимся с несколькими играми похожего свойства, но более простыми. А потом уже вернемся к игре в «15» и полностью докажем эту теорему.