|
|
 |
Условие
Кузнечик умеет прыгать по полоске из n клеток на 8, 9 и 10 клеток в любую сторону. Будем называть натуральное число n пропрыгиваемым, если кузнечик может, начав с некоторой клетки, обойти всю полоску, побывав на каждой клетке ровно один раз. Найдите хотя бы одно n > 50, которое не является пропрыгиваемым.
Решение
Предположим, что кузнечик пропрыгал полоску из 62 клеток. Покрасим 8 левых её клеток белым, следующие 10 – чёрным, потом снова 8 – белым и так далее. Всего будет 32 белых клетки и 30 чёрных. Поскольку разность количеств белых и чёрных клеток больше 1, то был прыжок между белыми клетками. Но такие прыжки невозможны.
Ответ
n = 62.
Замечания
1. Рассмотрим полоску из 63 клеток. Увеличим в решении один из белых кусков на одну клетку. Тогда разность количеств белых и чёрных клеток увеличится на единицу и количество возможных прыжков между белыми клетками – тоже. Поэтому снова получается противоречие. Так можно сделать с каждым из четырёх белых кусков. Таким образом, числа 63, 64, 65, 66 тоже не пропрыгиваемы.
Аналогично, уменьшая в решении чёрные куски на одну клетку, можно показать, что числа 59, 60, 61 не пропрыгиваемы.
2. Нетрудно показать, что числа от 17k – 1 до 19k + 1 включительно, где k натурально, пропрыгиваемы. В частности, числа 51, 52, ..., 58, а также все числа, большие 117, пропрыгиваемы.
3. 10 баллов.
