ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .