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

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

Условие

Дана клетчатая полоска (шириной в одну клетку), бесконечная в обе стороны. Две клетки полоски являются ловушками, между ними – 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.

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

олимпиада
Название Турнир городов
Турнир
Номер 29
Дата 2007/2008
вариант
Вариант весенний тур, сложный вариант, 8-9 класс
задача
Номер 3

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

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