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

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

Условие

На числовой прямой в точке P сидит точечный кузнечик. Точки 0 и 1 – ловушки. На каждом ходу мы называем любое положительное число, после чего кузнечик прыгает влево или вправо (по своему выбору) на расстояние, равное этому числу. Для каких P можно называть числа так, чтобы гарантированно загнать кузнечика в одну из ловушек? (Мы всё время видим, где сидит кузнечик.)


Решение

  Пусть P – число указанного в ответе вида, и дробь несократима (то есть a нечётно). Тогда и число  1 – P  имеет тот же вид (причём с тем же знаменателем). Назовём наименьшее из чисел P и  1 – P.  Если кузнечик прыгнет и не попадёт в ловушку, то он останется между ловушками, и расстояние до одной из ловушек удвоится. В результате знаменатель координаты кузнечика уменьшится вдвое. После k прыжков координата станет целой, что означает попадание в ловушку.
  Пусть P – не двоично-рациональное число. Объявим ловушками все двоично-рациональные числа. Покажем, что если кузнечик не в ловушке, он всегда может прыгнуть не в ловушку. Заметим, что полусумма ловушек – снова ловушка. Пусть названо число d. Так как  P = ½ ((P + d) + (P – d)),  и P – не ловушка, то хотя бы одна из точек  P + d  и  P – d  – тоже не ловушка. Туда и прыгнем.
  Пусть P – двоично-рациональное число, не лежащее в отрезке  [0, 1].  Тогда кузнечик каждым прыжком может удаляться от этого отрезка.


Ответ

При  P = a·2k,  где a и k – натуральные числа,  0 < a < 2k.

Замечания

6 баллов.

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

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

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

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