Задача 110164

Темы:    [ Процессы и операции ] [ Теория алгоритмов (прочее) ] [ Оценка + пример ]

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

Условие

Автор: Токарев С.И.

Мишень "бегущий кабан" находится в одном из n окошек, расположенных в ряд. Окошки закрыты занавесками так, что для стрелка мишень все время остается невидимой. Чтобы поразить мишень, достаточно выстрелить в окошко, в котором она в момент выстрела находится. Если мишень находится не в самом правом окошке, то сразу после выстрела она перемещается на одно окошко вправо; из самого правого окошка мишень никуда не перемещается. Какое наименьшее число выстрелов нужно сделать, чтобы наверняка поразить мишень?

Решение

Занумеруем окошки слева направо числами от 1 до n , а через k_i обозначим номер окошка, в которое делается i -й по счету выстрел ( i = 1 , 2, 3, ...).

Серия из []+1 выстрелов, определенная равенствами k[]+1=n и k_i =2i-1 для i[] , гарантирует поражение мишени (легко проверить, что если вначале мишень находится в m -м окошке и m[] , то результативным окажется m -й выстрел; если же m>[ ] , то мишень будет поражена последним выстрелом).

Покажем, что никакая серия из меньшего числа выстрелов требуемым свойством не обладает.
В самом деле, если произведено не более [] выстрелов, то для m=1 , 2, []+1 условием поражения мишени, находившейся вначале в m -м окошке, является равенство k_i =m + i-1 хотя бы для одного из значений i . Но каждый выстрел может обеспечить выполнение только одного из требующихся равенств. Следовательно, найдется такое число m₀[]+1 , что k_i m₀ + i-1 для i=1 , 2, [] ; это и означает, что для произвольной серии из [] (и, тем более, из меньшего числа) выстрелов существует начальное положение мишени, при котором она останется непораженной.

Ответ

[]+1.

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

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