Ответ 97

Январь 10, 2008

Из данных n пар шашек выделим по две крайние пары слева и справа (на рисунке они отделены вертикальными черточками).

Произведем два перемещения, не затрагивающие внутренние n — 4 пары шашек, но обеспечивающие рядом с ними два свободных места (см. рисунок, положение после ходов 1 и 2). Еще два перемещения, которые нужны для решения задачи в случае, если бы только и были четыре выделенные пары, пока задерживаем и обращаемся к перемещению внутренних шашек, пользуясь образовавшимися слева двумя свободными местами. По предположению, это мы сумеем сделать в последующие n — 4 хода и, как подсказывает накопленный опыт, в результате получим слева черные шашки, а справа — белые (рисунок, положение после хода n — 2). Теперь опять обращаемся к четырем парам первоначально отделенных шашек и в два перемещения (рисунок, ход n — 1 и ход n) завершаем решение.

Вся задача для n пар шашек решена в n—4+4=n перемещений.

В ходе доказательства выработалась и схема последовательности действий. Для любого заданного числа пар шашек последовательность действий состоит в сведении задачи к перемещению меньшего числа шашек, пока не дойдем до случаев, для которых решение было найдено непосредственно.

Комметирование закрыто now!