Задача 109570

Темы:    [ Процессы и операции ] [ Арифметическая прогрессия ] [ Геометрия на клетчатой бумаге ] [ Индукция (прочее) ]

Сложность: 4- Классы: 8,9,10

Условие

Автор: Карпов Д.В.

Натуральные числа от 1 до 1000 по одному выписали на карточки, а затем накрыли этими карточками какие-то 1000 клеток прямоугольника 1x 1994 . Если соседняя справа от карточки с числом n клетка свободна, то за один ход ее разрешается накрыть карточкой с числом n+1 . Докажите, что нельзя сделать более полумиллиона таких ходов.

Решение

Заметим, что карточку с числом 1 двигать нельзя. Следовательно, карточку с числом 2 можно двигать не более одного раза, карточку с числом 3 – не более двух раз, и т.д. Итак, для любого n1000 карточку с числом n можно двигать не более n-1 раз (так как мы можем положить ее только справа от карточки с числом n-1 , которая, в свою очередь, может двигаться не более n-2 раз). Значит, число сделанных ходов не превосходит 1+2+...+999=999· =499,500<500,000 .

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1994
Этап
Вариант	5
класс
Класс	9
задача
Номер	94.5.9.6