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

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

Условие

Три прямолинейных коридора одинаковой длины l образуют фигуру, изображённую на рисунке. По ним бегают гангстер и полицейский. Максимальная скорость полицейского в 2 раза больше максимальной скорости гангстера. Полицейский сможет увидеть гангстера, если он окажется от него на расстоянии, не большем r. Доказать, что полицейский всегда может поймать гангстера, если:   а)  r > l/3;   б)   r > l/4;   в)   r > l/5;   г)   r > l/7.


Решение

  Договоримся, что полицейский всегда движется с максимальной скоростью. Сначала он "прочёсывает" коридор OC. Убедившись, что гангстера там нет, полицейский удаляется в коридор OA на расстояние 2r и затем возвращается в точку O. Пусть отсюда он не увидел гангстер. Заметим, что тогда он не может находиться в коридоре OC: если бы он за время отсутствия полицейского в точке O попытался перебежать из коридора OB в коридор OC, то к моменту возвращения полицейского в точку O расстояние от гангстера до O было бы не больше, чем r.

  а) Если  l ≤ 3r,  то гангстер не может находиться и в коридоре OA, и полицейский ловит его, "прочесав" коридор OB.

  б) Пусть  3r < l ≤ 4r.  Тогда гангстер может находиться в коридоре OA, но на расстоянии от O , большем 2r.
  Теперь полицейский отправляется в коридор OB на расстояние 3r. Вернувшись в точку O и не увидев гангстера, полицейский знает, что в коридоре OB гангстера нет. Но и в коридоре OC гангстера нет (если гангстер находился в коридоре OA, то на расстоянии от O, большем 2r, и потому до возвращения полицейского в точку O, гангстер не сможет перебежать в коридор OC так, чтобы при этом оказаться от O на расстоянии, большем r). Осталось "прочесать" коридор OA.

  в) Пусть  4r < l < 5r.  Тогда гангстер может находиться в коридоре OB, но на расстоянии от O, большем  (3r + r) – 3r/2 = 5r/2.
  Дальнейшие действия полицейского заключаются в том, чтобы углубляться то в коридор OB, то в коридор OA на все большие расстояния, но так, чтобы гангстер не смог перебежать в коридор OC. Каждое такое "углубление" вместе с последующим возвратом в точку O будем называть циклом. Два первых цикла уже описаны.
  Пусть после n-го цикла полицейский знает, что в коридоре OC гангстера нет, а в коридоре OX (где  X = A  при нечётном n и  X = B  при чётном n) гангстер может находиться только на расстоянии от O, большем yn. Тогда в следующем цикле полицейский отправляется в другой коридор на расстояние  yn + r.  Вернувшись в точку O, полицейский знает, что в коридоре OC гангстера нет, а в только что исследованном коридоре гангстер может находиться только на расстоянии от O, большем  yn+1 = (½ (yn + r) + r) = ½ (yn + 3r).  Если же  yn + r ≥ l – r,  то в исследованном коридоре гангстера вообще нет.
  Так как  3r – yn+1 = ½ (3r – yn),  то  3r – yn = 21–n(3r – y1) = 21–nr,  то есть  yn = 3r – 21–nr.  Гангстер ловится, если  yn + r ≤ l – r  при каком-нибудь n, то есть если  21–nr ≤ 5r – l.  Поскольку  l < 5r,  то после достаточно большого числа циклов гангстер ловится.

  г) Пусть  5r ≤ l < 7r.  Положим  ε = ½ (7r – l).  Полицейский действует так, как описано в п. в), пока при каком-то не окажется, что  yn ≥ 3r – ε  (из формулы для yn следует, что когда-то это произойдёт). После этого полицейский углубляется в очередной коридор (скажем, OA) на расстояние  l – r.
  Вернувшись в точку O и не увидев гангстера, полицейский знает, что в коридоре OA гангстера нет, а в коридоре OC гангстер не может находиться от O на расстоянии, большем   (l – r) – (3r – ε) = 3r – ε.  Затем полицейский углубляется в коридор OC на расстояние  4r – 2ε.  Вернувшись в точку O и не увидев гангстера, полицейский знает, что в коридоре OC гангстера нет (в противном случае гангстер был бы пойман, оказавшись в коридоре OC от полицейского на расстоянии, меньшем  (3r – ε) + ½ (4r – 2ε) – (4r – 2ε) = r),  а в коридоре OA гангстер не может находиться на расстоянии от O, большем
(4r – 2ε) – r = 3r – 2ε.  Затем полицейский идёт в коридор OA на расстояние  4r – 4ε,  затем в коридор OC на расстояние  4r – 8ε,  снова в коридор OA на расстояние  4r – 16ε  и т. д. Когда окажется, что надо идти на отрицательное расстояние, полицейский понимает, что гангстер находится в коридоре OB.

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

журнал
Название "Квант"
год
Год 1980
выпуск
Номер 9
Задача
Номер М645

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

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