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

Проект МЦНМО
при участии
школы 57
Задача 110164
Темы:    [ Процессы и операции ]
[ Теория алгоритмов (прочее) ]
[ Оценка + пример ]
Сложность: 5-
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

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

Решение

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

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

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

Ответ

[]+1.

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

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

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

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