Mоск MO (1980) Полицейский и гангстер

[Red_Herring]

Вот задача

http://www.problems.ru/view_problem_details_new.php?id=79385 писал(а):

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

На Олимпиаде она предлагалась в значительно более слабом варианте а) $r > {\frac{l}{3}}$; б) $r > {\frac{l}{4}}$ (и в книжке решения нет), а на сайте—во всей красе!

Во всей ли?
(1) Можно ли перейти через ${\frac{l}{7}}$?
(2) Можно ли доказать, что нельзя—т.е. если Гангстер знает наперед все ходы Полицейского, то он сможет избежать поимки?
(3) Или хотя бы доказать (2) скажем при $r<{\frac{l}{10}}$?

[grizzly]

Red_Herring в сообщении #956640 писал(а):

(3) Или хотя бы доказать (2) скажем при $r<{\frac{l}{10}}$?

Ничего красивого не придумалось -- простая рабоче-крестьянская индукция с перебором вариантов. Ниже для удобства $r=1; l=10$.

Будем называть завершением цикла такую ситуацию, когда Полицейский сделал несколько шагов и либо поймал Гангстера либо вернулся в центр лабиринта. Докажем, что при завершении каждого цикла Гангстер имеет полное право быть не пойманным при реализации одной из двух ситуаций:
(1) Гангстер может находиться в одном из двух коридоров на расстоянии 4 от т.$O$ в каждом.
(2) Гангстер может находиться в одном из трёх коридоров: в двух -- на расстоянии 2 от т.$O$, в третьем -- на расстоянии 5.5.
Рассуждаем по индукции. После цикла 1 это очевидно. Пусть это верно после цикла $k$. Простым перебором небольшого количества осмысленных вариантов убеждаемся, что после цикла $k+1$ будет реализована одна из перечисленных ситуаций: (1) или (2).

Оценку $r<{\frac{l}{10}}$ таким способом можно улучшать. Но поскольку идея решения не особенно приятная, я поленился довести её до конца.

[Red_Herring]

Спасибо

[grizzly]

(Оффтоп)

Red_Herring в сообщении #956855 писал(а):

Спасибо

Да за что вы нас благодарите?
Вам спасибо за этот аврал!
(по ассоциации из Высоцкого :)