|
|
 |
Условие
Дана клетчатая полоска (шириной в одну клетку), бесконечная в обе стороны. Две клетки полоски являются ловушками, между ними – N клеток, на одной из которых сидит кузнечик. На каждом ходу мы называем натуральное число, после чего кузнечик прыгает на это число клеток влево или вправо (по своему выбору). При каких N можно называть числа так, чтобы гарантированно загнать кузнечика в одну из ловушек, где бы он ни был изначально между ловушками и как бы ни выбирал направления прыжков? (Мы всё время видим, где сидит кузнечик.)
Решение
Занумеруем клетки по порядку так, чтобы ловушки получили номера 0 и N + 1.
Пусть N + 1 = 2k. Будем каждый раз называть расстояние d до ближайшей ловушки. Наибольшая степень двойки, на которую делится d, меньше k. Если кузнечик прыгнет в противоположную сторону и не попадёт в ловушку, то он останется между ловушками, и расстояние до одной из ловушек станет 2d, а до другой 2k – 2d. Оба этих расстояния делятся на бóльшую степень двойки. Поэтому рано или поздно расстояния разделятся на 2k, что и означает попадание в ловушку.
Пусть N + 1 = 2kt, где t нечётно и больше 1. Объявим ловушками все клетки с номерами, кратными t. Пусть кузнечик стоит не в ловушке. Заметим, что он не стоит и ровно посередине между двумя ловушками, поскольку все числа вида ½ (at + bt) либо нецелые, либо кратны t. Значит, при любом названном числе у кузнечика есть прыжок не в ловушку.
Ответ
При N = 2k – 1, где k – натуральное число.
Замечания
1. 6 баллов.
2. Ср. с задачей 64612.
