Олимпиадная задача "Бегущий кабан" по математике для 8-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.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь