Математика для гуманитариев: живые лекции | страница 14

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). Изменятся ровно две пары.

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

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

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

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

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

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

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

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