Задача 98363

Темы:    [ Теория алгоритмов (прочее) ] [ Шахматные доски и шахматные фигуры ]

Сложность: 2+ Классы: 6,7,8

Условие

Автор: Шаповалов А.В.

Первоначально на каждом поле доски 1×n стоит шашка. Первым ходом разрешается переставить любую шашку на соседнюю клетку (одну из двух, если шашка не с краю), так что образуется столбик из двух шашек. Далее очередным ходом каждый столбик можно передвинуть в любую сторону на столько клеток, сколько в нём шашек (в пределах доски); если столбик попал на непустую клетку, он ставится на стоящий там столбик и объединяется с ним. Докажите, что за  n – 1  ход можно собрать все шашки на одной клетке.

Решение

Выберем центральную шашку (одну из двух, если n чётно). Каждым очередным ходом будем двигать тот столбик, в котором эта шашка оказалась, по направлению к наиболее удалённому краю доски. (Если n нечётно, то первый ход можно делать в любом направлении.) После каждого хода количество шашек в столбике, который мы двигаем, увеличивается на 1. Значит, после (n – 1)-го хода в нём будет 1 + (n – 1) = n шашек.

Замечания

5 баллов

Источники и прецеденты использования

олимпиада
Название	Турнир городов
Турнир
Дата	1997/1998
Номер	19
вариант
Вариант	осенний тур, основной вариант, 8-9 класс
Задача
Номер	3