Блуждание в трех коридорах

Задача

Три прямолинейных коридора одинаковой длины d образуют фигуру, изображенную на рисунке 1.

Рис. 1.

Рис. 1.

По коридорам перемещаются гангстер и полицейский, причем максимальная скорость полицейского в 2 раза выше максимальной скорости гангстера. К сожалению, коридоры длинные, а полицейский обладает ограниченной дальностью обзора — он сможет увидеть гангстера, только если окажется от него на расстоянии не более 1.

Придумайте алгоритм, позволяющий полицейскому поймать гангстера: а) при d = 3; б) при d = 4,999; в) при любом d < 7.


Подсказка 1

Алгоритм полицейского не должен зависеть от того, что и как делает гангстер, потому что в процессе выполнения алгоритма полицейский гангстера не видит (а в тот момент, когда увидит, гангстер будет пойман из-за того, что полицейский имеет преимущество в скорости). В частности, правильный алгоритм должен работать при любом поведении гангстера, и даже в том случае, если гангстер прекрасно осведомлен о том, где в каждый момент времени находится полицейский. Поэтому фактически мы должны отыскать «кривую погони», которая позволит полицейскому отыскать гангстера в «трилистнике». А значит, мы можем считать, что по этой кривой полицейский всегда движется с максимально возможной скоростью.


Подсказка 2

Пусть полицейский начинает движение из точки A к центру трилистника O, затем проходит некоторое расстояние по коридору OB и возвращается обратно в O (рис. 2). На какое расстояние он может пройти, чтобы в момент возвращения быть уверенным, что гангстера нет в коридоре OA?

Рис. 2.

Рис. 2.


Подсказка 3

Ответ на вопрос, сформулированный в подсказке 2, равен 2. Поэтому пункт а) уже фактически решен: гангстера нет ни в коридоре OA, ни в коридоре OB, поэтому он обязан находиться в коридоре OC, и именно там его полицейский дальше и ловит.

Для решения пункта б) полицейскому нужно продолжать погоню — сначала пройти в коридор OC на такое расстояние, чтобы в момент возвращения точно понимать, что гангстер не успел перебежать из OB в OA. (Докажите, что это расстояние равно 3.) Вернувшись, он снова прочёсывает OB так, чтобы к моменту возвращения гангстер не успел перебежать из OC в OA. И так далее — разберитесь, почему этого окажется достаточным для любого значения d, меньшего 5.

Рис. 3.

Рис. 3.


Решение

а) Итак, почему при d = 3 верно то, что написано во второй подсказке? То есть, почему после «погружения» полицейского в коридор OB на глубину 2 и возврата в O можно утверждать, что гангстер находится именно в OC? Понятно, что его нет в коридоре OB, потому что, пройдя в OB расстояние d − 1 = 2, полицейский увидел конец коридора. Мог ли гангстер успеть за это время выскочить из коридора OC в коридор OA и оказаться там на таком расстоянии, на котором его из точки O не увидит полицейский? Нет, потому что вначале он находился на расстоянии >1 в коридоре OC, в конце должен оказаться на расстоянии >1 в коридоре OA, а значит, должен пройти больше чем 2. Однако за то время, пока полицейский ходил в коридоре ОB, гангстер мог пройти расстояние не больше чем половина пути полицейского, то есть (2 + 2)/2 = 2. Пункт а) решен.

б) Теперь разберемся со случаем d = 4,999. На рис. 3 показано положение полицейского после «погружения» в коридор OC на глубину 3. Вернувшись в точку O и не увидев гангстера, полицейский знает, что в коридоре OC гангстера не было по крайней мере до глубины 4. Кроме того, гангстер не мог перейти незамеченным из коридора OB в коридор OA, потому что для этого ему необходимо было пройти расстояние, большее 4, за то время, пока полицейский проходил 2 + 3 + 3 = 8, а это невозможно с его скоростью.

Обратите внимание, что второе «погружение» полицейский смог сделать на глубину 3, потому что (2 + 3 + 3)/2 < 2 + 1 + 1. Как рассчитать глубину следующего погружения полицейского (опять в коридор OB)? Он может себе позволить пройти туда на расстояние x и вернуться, если за это время гангстер не успеет выскочить из коридора OC и углубиться в OA на расстояние, большее 1. Поскольку полицейский уверен, что в коридоре OC гангстера нет по крайней мере до расстояния 3 + 1 = 4, то должно быть выполнено условие (3 + x + x)/2 < 4 + 1, то есть x < 3,5. Пройдя до x = 3,5 в коридор OB, полицейский уже знает, что в этом коридоре гангстера нет на расстоянии до x + 1 = 4,5, поэтому глубина y следующего погружения в коридор OC может быть такой, чтобы выполнялось неравенство (3,5 + y + y)/2 < 4,5 + 1, то есть y < 3,75.

Мы видим, что «глубины погружения» полицейского (поочередно в коридоры OB и OC) образуют последовательность 2, 3, 3,5, 3,75. Можем ли мы указать формулу, задающую члены этой последовательности? Безусловно. Если на n-м шаге полицейский зашел в один из коридоров на расстояние a(n), то гангстера в этом коридоре нет вплоть до расстояния a(n) + 1, а значит, следующее погружение полицейского в соседний коридор может иметь такую глубину a(n + 1), чтобы (a(n) + a(n + 1) + a(n + 1))/2 ≤ a(n) + 2. Откуда получаем, что a(n + 1) = (a(n) + 4)/2. Это рекуррентное соотношение нетрудно превратить в явную формулу для n-го члена последовательности: оно указывает, что каждая следующая точка делит пополам отрезок между предыдущей точкой и точкой 4. Иначе говоря, каждая следующая точка вдвое ближе к 4, чем предыдущая. Но это означает, что расстояние до 4 (которое в начале равнялось 2), в каждом следующем погружении сокращается вдвое, то есть 4 − a(n) = (4 − a(0))/2n. Упрощая это уравнение, получим, что 4 − a(n) = 2/2n, a(n) = 4 − 2/2n. Ясно, что начиная с некоторого n значение a(n) окажется больше чем 3,999, а значит, этого хватит для того, чтобы полностью вытеснить гангстера из коридора длины d = 4,999.

в) А вот теперь самый интересный момент. Погоня по коридорам OB и OC поочередно, как мы увидели выше, позволяет разобраться с коридорами любой длины, меньшей 5. Но как решить задачу для более длинных коридоров?

Здесь нам на помощь приходит возможность, которую мы раньше не использовали: отогнав гангстера достаточно далеко от точки O, полицейский может прочесать один из коридоров до конца (для определенности, коридор OB проходится полицейским до той точки, из которой ему будет виден конец коридора). Да, при этом гангстер сможет перескочить из коридора OC в OA через точку O, однако он не сможет уйти в коридоре OA очень далеко! Пройдя затем коридор OA на необходимую глубину, полицейский будет уверен, что гангстера там нет. А вдруг гангстер успеет за это время перейти из OC снова в OB? Да пусть успевает, лишь бы ему при этом удалось пройти в сторону OB заведомо меньше, чем удалось бы погрузиться в OA на предыдущем шаге. Если мы увидим, что такая последовательность погружений для гангстера уменьшается до 0, это означает, что рано или поздно полицейский сможет гарантировать, что в очередном коридоре гангстера нет, и тогда у гангстера останется единственный коридор, где он и будет пойман.

Все, что нам осталось, — это аккуратно посчитать все эти «погружения».

Пусть расстояние, на которое полицейский углублялся в коридоре OC перед тем, как прочесать до конца коридор OB, равно c. Так как затем в коридоре OB полицейский прошел туда и обратно расстояние d − 1, то за это время гангстер прошел не более чем d − 1 + c/2. А так как он находился от O не ближе чем на c + 1, то углубиться в OA он может не более чем на a = d − 2 − c/2. Чтобы убедиться, что на самом деле гангстера нет в OA, полицейскому нужно войти в этот коридор на глубину 2(a − 1). (Действительно, за это время гангстер сможет пройти еще не больше, чем a − 1, а значит, окажется не дальше 2a − 1 от точки O, то есть не дальше чем на расстоянии 1 от полицейского, и будет обнаружен и пойман.) Когда полицейский начинает эту проверку коридора OA, гангстер находится в OC не ближе чем на расстоянии 1 от O. Поэтому в конце проверки (когда полицейский вернется в O), гангстер сможет перебежать в коридор OB не дальше чем на расстояние b = 2a − 3. Условие «b < a», которого мы хотели добиться, эквивалентно неравенству 2a − 3 < a, то есть тому, что a < 3. Отсюда получаем необходимость d − c/2 < 5, d < 5 + c/2. Так как значение c можно сделать сколь угодно близким к 4, то d можно сделать сколь угодно близким к 7.


Послесловие

Задача о погоне полицейского и гангстера относится к серии задач гарантированного поиска (см. Pursuit-evasion). Впервые такие задачи были рассмотрены американцем Торренсом Парсонсом (Torrence Parsons) в 1978 году. Изначальная фабула задачи, которую решал Парсонс, относилась к поиску человека, потерявшегося в темной пещере. Предполагалось, что тот, кто его ищет, производит обход графа, и обнаруживает пропавшего в том случае, если оказывается в соседней с ним вершине.

Спустя несколько лет после этого, в 1982 году, была опубликована работа ленинградца П. А. Головача, в которой впервые был рассмотрен ε-поиск, то есть вместо обхода графа рассматривался путь на геометрических объектах, а условие успеха (обнаружения объекта) формулировалось в терминах достижения некоторого расстояния ε до него. В такой формулировке уже было очевидным, что искомый объект может сопротивляться обнаружению и задача сводится к тому, чтобы выяснить, в каких случаях это сопротивление может оказаться успешным.

Следует заметить, что и Парсонс, и Головач решали немного другую задачу — они искали минимальное значение количества преследователей, гарантирующее успешность поимки (при любом бездействии или противодействии). А задача об одном полицейском и гангстере появилась строго между выходом работ Парсонса и Головача, причем в весьма неожиданном месте — на Московской математической олимпиаде, в вариантах для 9 и 10 классов. Не очень понятно, знали ли тогда авторы задачи про более общую постановку, или же это оказалось случайным совпадением.

За прошедшие годы задача обросла различными вариантами и обобщениями. Так, аннотированная библиография по этому вопросу, опубликованная в 2008 году в спецвыпуске журнала Theoretical Computer Science, содержит 172 позиции, а в 2011 появился даже отдельный учебный курс для студентов — “The Game of Cops and Robbers on Graphs”.


5
Показать комментарии (5)
Свернуть комментарии (5)

  • Олег Чечулин  | 13.01.2017 | 04:42 Ответить
    Опять я, с позволения публики, докопаюсь до формулировки условия :)

    "Три прямолинейных коридора одинаковой длины d образуют фигуру, изображенную на рисунке 1.
    По коридору перемещаются гангстер и полицейский"

    Здесь написано, что фигура состоит из трёх коридоров. Но далее написано, что гангстер и полицейский перемещаются по одному коридору ;)
    То есть, два других коридора в задачу введены для отвода глаз (задач с лишними данными пруд пруди в любой области знаний), и в них полицейский и гангстер по каким-то причинам не заходят.

    Честно говоря, именно от Константина я такого ляпа и не ожидал :)
    Ответить
    • Олег Чечулин > Олег Чечулин | 13.01.2017 | 04:43 Ответить
      О, а в краткой формулировке всё нормально: "Три прямолинейных коридора одинаковой длины d расходятся из одной точки. По ним ходят полицейский и гангстер."
      Ответить
    • editor > Олег Чечулин | 13.01.2017 | 05:12 Ответить
      Поправили, спасибо.
      Ответить
  • karpanin  | 13.01.2017 | 04:56 Ответить
    Чтобы алгоритмы работали, достаточно чтобы лишь один из коридоров был определённой длинны, остальные два должны просто не быть бесконечными.
    Ответить
  • neophyte  | 14.01.2017 | 13:55 Ответить
    Комментарий к первому утверждению подсказки 3.
    Пока полицейский движется по коридору ОВ от т.О до дальности 2, гангстер приближается к т. О по коридору ОС с дальности 1. Поэтому в момент достижения полицейским точки 2 гангстер может перейти в коридор ОА.
    Ответить
Написать комментарий

Другие задачи


Элементы

© 2005-2017 «Элементы»