|
|
 |
Условие
Три прямолинейных коридора одинаковой длины 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.
