Олимпиадная задача по теории алгоритмов: собираем шашки на доске 1×n (Шаповалов А. В., 6-8 класс)
Задача
Первоначально на каждом поле доски 1×n стоит шашка. Первым ходом разрешается переставить любую шашку на соседнюю клетку (одну из двух, если шашка не с краю), так что образуется столбик из двух шашек. Далее очередным ходом каждый столбик можно передвинуть в любую сторону на столько клеток, сколько в нём шашек (в пределах доски); если столбик попал на непустую клетку, он ставится на стоящий там столбик и объединяется с ним. Докажите, что за n – 1 ход можно собрать все шашки на одной клетке.
Решение
Выберем центральную шашку (одну из двух, еслиnчётно). Каждым очередным ходом будем двигать тот столбик, в котором эта шашка оказалась, по направлению к наиболее удалённому краю доски. (Еслиnнечётно, то первый ход можно делать в любом направлении.) После каждого хода количество шашек в столбике, который мы двигаем, увеличивается на 1. Значит, после (n– 1)-го хода в нём будет 1 + (n– 1) =nшашек.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь