Математика для гуманитариев. Живые лекции - Алексей Владимирович Савватеев

12 оказался в четвертой строке за счет каких-то предыдущих перемещений) (см. рис. 18).

Рис. 18. Следите только за третьей строкой.

Записываю фрагмент змейки:

… 8, 7, 6, 5, 9, 10, 11, пусто…

Нас интересует только этот фрагмент, потому что при движении, которое будет совершено, слева и справа в змейке ничего не изменится. Будет меняться только этот набор цифр. Расположение остальных пар не меняется. Внимание: «8» пошло вниз, пустышка — наверх (рис. 19).

Рис. 19. «Восмерка» и «пустышка» поменялись местами.

Как теперь будет выглядеть середина змейки? Вот так:

… пусто, 7, 6, 5, 9, 10, 11, 8…

Что произошло? Восьмерка из начала группы скакнула в конец. Какие пары свое значение поменяли? Группа из шести чисел (7, 6, 5, 9, 10, 11) целиком сохранилась. Она просто поменялась местами с восьмеркой. Значит, какие пары поменяли, как говорят математики, «свой тип монотонности», то есть возрастание сменилось убыванием (или, наоборот, убывание — возрастанием)?

Слушатель: (8, 7).

А.С.: (8, 7). Здесь теперь (7, 8); а еще?

Слушатель: (8, 6), (8, 5)…

А.С.: При том движении, которое я произвел, поменяют взаимное расположение чисел только те пары, в которых участвовало число 8. Поэтому 6 пар изменили тип монотонности. Если были возрастающими — стали убывающими, и наоборот.

Рассмотрим каждую пару в отдельности.

Было (8, 5) (числа в порядке убывания), стало (5, 8) — возрастание. Количество неправильных пар изменилось на единицу вниз. Было (8, 10), стало (10, 8), количество неправильных пар изменилось на единицу вверх. С остальными парами — то же самое. Каждый раз мы добавляем или вычитаем единицу. Не может быть, чтобы где-то (вместо плюс/минус единицы) получился нуль, так как среди указанных шести чисел нет восьмерок (ведь каждое число, написанное на фишке, единственно).

Вне зависимости от знаков, количество изменивших тип монотонности пар всегда четно. Имеется 64 способа расставить знаки, но в результате всегда в качестве суммы получится четное число. Соседние плюс/минус единички либо добавят к сумме 2, либо добавят (−2), либо взаимно уничтожатся, давая ноль:

±1 ± 1 ± 1 ± 1 ± 1 ± 1

В каждой паре соседних плюс/минус единичек получится или 0, или 2 или −2. То есть общее изменение количества «неправильных пар» может произойти на 6, 4, 0, −2, −4, −6.

Изменения происходят на четную величину, поэтому исходное количество «беспорядков» (оно было равно 8) могло стать числом 14, если все единички оказались бы с плюсом, могло остаться 8 (если бы было +1, +1, +1, −1, −1, −1). Могло стать 6, могло 4 или 2. Но никак не могло стать ни 5, ни 7.

В принципе, на этом месте я мог бы сказать «остальное проверьте сами», потому что в других случаях передвижения пустой фишки происходит ровно тот же самый эффект. Но давайте для аккуратности проверим что-нибудь еще. Например, вверх могло пойти число 14 (вместо того, чтобы опустить вниз число 8) (см. рис. 20).

Рис. 20. Еще один способ «освоения» пустого поля.

Что произойдет, где начались изменения? Только в нижних двух строках. Было 1, 2, 3, 4, 8, 7, 6, 5, а потом вместо 9, 10, 11, 14, 12, 15, 13 мы увидели 9, 10, 11, 14, 12, 15, 13. Ничего вообще не изменилось.

Давайте теперь представим себе внутреннюю пустую фишку. Скажем, если в позиции на рис. 18 клеточку 11 сдвинули к краю, а 7 сдвинули вниз (рис. 21):

Рис. 21. Семерка «переселилась» с 3-го этажа на 2-й.

Выпишем змейку до того, как подвинули 7:

1, 2, 3, 4, (8, 7, 6, 5, 9, 10, 11), 14, 12, 15, 13.

Теперь я двигаю 7 вниз и получаю вот такой фрагмент змейки:

1, 2, 3, 4, 8, 6, 5, 9, 10, 7, 11…

Выделяю в змейке группу, которая менялась.

Было: 1, 2, 3, 4, 8, (7, 6, 5, 9, 10), 11, 14, 12, 15, 13.

Стало: 1, 2, 3, 4, 8, (6, 5, 9, 10, 7), 11, 14, 12, 15, 13.

6, 5, 9, 10 переехали на шаг левее, а 7 через них перепрыгнула. Сколько будет изменений? Ровно 4. Пары опять поменялись. Правильные стали неправильными, и наоборот. Опять каждый раз мы прибавляем или отнимаем единицу. И так 4 раза. А 4 ведь — четное число, вот незадача. Опять результат меняется на четное число.

Что мы можем еще сделать? Мы могли вместо 7 подвинуть 12 (рис. 22). Тогда 12 прыгнет за пару (11, 14). Изменятся ровно две пары.

Слушатель: То есть нечетное число поменяться не может.

Рис. 22

А.С.: Ни при каких условиях. Мы уже знаем, что движение по горизонтали — бессмысленно. Получится та же самая змейка. Если мы движемся сверху вниз, то количество неправильных пар меняется либо на 2, либо на 4, либо на 6, либо ничего не меняется. Можно честно перебрать все возможные переходы снизу вверх. Можно просто понять, что никаких других вариантов, кроме четных, нет. То есть в пятнашку выиграть нельзя, потому что в стандартной исходной позиции количество неправильных пар 8, и изменить его можно только на четное число. А в требуемой позиции имеется 9 неправильных пар.

Слушатель: Из любой ли позиции выиграть невозможно?

А.С.: Почему? На самом деле из половины всех исходных позиций. Из половины невозможно, из половины возможно. Потому что в «высокой» математике учат, что половина последовательностей имеет четное число неправильных пар, а половина — нечетное[6]. Поэтому половина вариантов будет собираться в стандартную исходную позицию. Если пятнашки как угодно перемешать, вывалив из коробки и затем вставив обратно как придется, то перестановкой фишек всегда можно прийти либо к случаю «13, 14, 15», либо к случаю «13, 15, 14».

Чтобы понять, можно ли привести фишки в исходную позицию, нужно посчитать количество неправильных пар в змейке, соответствующей изучаемой исходной позиции. Если оно нечетное — привести к исходной позиции можно. Если четное — то нельзя.

Слушатель: Какие числа можно поменять местами?

Другой слушатель: Например, 1 и 3 можно поменять?

А.С.: Если я меняю 1 и 3 местами (было 1, 2, 3, — стало 3, 2, 1), то как изменилась четность? Было отсутствие беспорядков (то есть 0), стало три беспорядка. Четность, стало быть, изменилась. Так что поменять в игре «пятнадцать» 1 и 3 местами, сохраняя