|
|
 |
Условие
Город представляет собой бесконечную клетчатую плоскость (линии – улицы, клеточки – кварталы). На одной улице через каждые 100 кварталов на перекрестках стоит по милиционеру. Где-то в городе есть бандит (местонахождение его неизвестно, но перемещается он только по улицам). Цель милиции – увидеть бандита. Есть ли у милиции способ (алгоритм) наверняка достигнуть своей цели? (Максимальные скорости милиции и бандита какие-то конечные, но не известные нам величины, милиция видит вдоль улиц во все стороны на бесконечное расстояние.)
Решение
Пусть милиционеры стоят на улице y = 0 в точках (100k, 0) (k = 0, ±1, ±2, ...). Приведём искомый алгоритм.
1) Милиционеры, стоящие в точках (200k, 0) (k = 0, ±1, ±2 ...) остаются на месте. Таким образом, бандит "зажат" в одной из "полос" между прямыми
x = 200l и x = 200(l + 1) для некоторого l (которое, конечно же, милиции не известно).
2) Остальные милиционеры (стоявшие в точках (100(2k + 1), 0) движутся по улице y = 0 в направлении точки (0, 0) до ближайшего к ней перекрёстка с улицей x = n, на которой ещё нет милиции. Достигнув перекрёстка, милиционер поворачивает на улицу x = n и движется вдоль положительного направления оси y, если n – чётно, и в другую сторону, если n нечётно.
Понятно, что в какой-то момент бандит будет "зажат" в вертикальной полосе ширины 1, то есть не сможет перемещаться по вертикали. Через какое-то время после этого один из милиционеров попадёт на горизонталь, где находится бандит, и увидит его.
Замечания
8 баллов
