23. Игра в 15

Решая задачу о конях, мы по сути дела доказали такое утверждение: На (8 ´ 8)-доску нельзя поставить более 32 не бьющих друг друга коней. Как уже говорилось выше, такие доказательства невозможности играют большую роль в комбинаторике.

В 1879 г. американский составитель шахматных задач и этюдов, головоломок и различных игр Сэмюэль Лойд Свел с ума Европу и Америку квадратной коробочкой с 15 шашкаМИ. Коробочка имела 16 полей, а на шашках были нанесены числа от 1 до 15. Одно поле в коробочке было свободно и требовалось, передвигая каждым ходом одну шашку на свободное поле, перевести положение, ИЗображенное на рис. 5, А, в стандартное положение (рис. 5, Б). За решение задачи была предложена крупная сумма денег. Фабрикант, выпускавший игру, быстро разбогател — рассказывают, что свящеННики не выпускали из рук коробочки с шашками во время богослужения, МАшинисты решали задачу, ведя поезда, торговцы ЗабыВали открывать свои магазиНЫ. Но никому не Удавалось Найти решение проблемы.

Горячка прошла лишь после того, как в 1880 г. былА Доказана неразрешимость задачи Лойда. Чтобы изложитЬ Это доказательство, нам придется поясНИть, что называется Беспорядком (или Инверсией) в перестаНОвке чисел. Возьмем перестановку 3142. В ней число 3 стоит перед 1 и 2, хотя и больше них. Это создает два беспорядка. Еще один беспорядок возникает из-за того, что число 4 стоит перед числом 2. Всего в этой перестановке три беспорядка.

Если переставить два рядом стоящих числа, то количество беспорядков изменится на 1: или на 1 увеличится, если до перемещения меНЬшее число стояло перед большим, или на 1 уменьШИтся. Поэтому если число БеспорядКов было четным (нечетным), то оно стаНЕт нечетным (четным). Четность числа беспорядков называют Четностью NеPecmановки.

ВыяснИМ, что произойдет с чЕТностью перестановкИ, ЕСли переставить два далеких друг от друга числа, например числа А и B в перестановке... А... B... Пусть Между Ними стоит R других чисел. Тогда перемещениЕ моЖНо выполнить в три этапа — сначала R перестановками соседНИх чИСел поставить число А рядом с числом B, ЗАтем переставИТь меЖДу собой А и B и, наконец, еще R перестанОВками соседних чисел отправить B на то место, где раньше стояло B. Всего мы сделаем 2R+1 перестановок соседних чисел, т. Е. обязательно НЕчетное число, а так как при, каждой такой перестановке четность числа беспорядков меняется, то в конце всей операции четность перестановки изменится.

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

< Предыдущая		Следующая >