ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ
ВЫПУСК 61
Л. Л. ПЕТРОСЯН, Б. Б. РИХСИЕВ
ПРЕСЛЕДОВАНИЕ
НА ПЛОСКОСТИ
8
МОСКВА «НАУКА»
ГЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
19 9 1
ББК 22.18
П31
УДК 519.7
Рецензент
доктор физико-математических наук М, С, Никольский
Петросян Л. А., Рихсиев Б. Б.
П31 Преследование на плоскости,— М.: Наука. Гл.
ред. физ.-мат. лит., 1991,—96 с,—(Попул. лекции
по мат.; Вып. 61).
ISBN 5-02-014154-2.
Содержит популярное изложение элементов теории диф-
ференциальных игр и некоторых геометрических способов
решения игр преследования на плоскости, базирующихся на
использовании стратегии параллельного сближения (П-стра-
тегия). Для конкретных задач преследования приведены и
обоснованы оптимальные способы поведения преследующе-
го и убегающего игроков.
Для широкого круга читателей, включая школьников
старших классов, интересующихся математикой.
„ 1402010000-072
П 053(02)-91	41’90
ББК 22.18
ISBN 5-02-014154-2
©«Цаука», физматлит, 1991
Ты уж и прежде, я помню, бежал
пред моим Пелиасом
Или забыл, как тебя одного изловив
я у стада,
Гнал по Идейским горам и с какой
от меня быстротою
Ты убегал? И назад оглянуться не смел
ты, бегущий!
С гор убежал ты и в стены Лирнесса
укрылся; но в прах я
Град сей рассыпал, ударив с Афиной
и Зевсом Кронидом.
Гомер. Илиада,
Песнь двадцатая, строки 187—192
ВВЕДЕНИЕ
Лиса Р гонится за кроликом Е*). Естественно, лиса
стремится поймать кролика за кратчайшее время, а кро-
лик стремится избежать поимки. Если лиса и кролик
имеют возможность изменять направление своего движе-
ния как угодно, то очевидно, что кролик будет убегать
по прямой от лисы, а лиса будет направлять свое движе-
ние на кролика. В результате лиса и кролик будут пере-
мещаться вдоль прямой, соединяющей их начальные по-
ложения (рис. 1). Однако даже в случае, когда Р и Е
будем считать точками, для математического обоснова-
ния этого, на первый взгляд тривиального, результата
оказывается необходимым доказать ряд вспомогательных
*) Первые буквы английских слов соответственно pursuief
преследователь, evader — убегающий.
1*	3
теорем из элементарной планиметрии. Задача усложняет-
ся, если точки Р и Е могут перемещаться лишь внутри
некоторого выпуклого множества на плоскости, т. е. ког-
да лиса преследует кролика на огражденном участке, или
если в преследовании участвует несколько точек (лис)
Р\, Р2, ..., Рт. Здесь возникают новые математические
задачи, многие из которых не решены и в настоящее
время.
В предлагаемой книге в доступной форме излагаются
различные задачи преследования, в которых участвуют
объекты, совершающие простое движение на плоскости.
Простым движением называется движение с постоянной
по величине скоростью, при этом направление движения
может изменяться произвольным образом. Определение
наилучших способов преследования и убегания, выясне-
ние самой возможности встречи — вот основные вопросы,
которые возникают при изучении конфликтных задач пре-
следования по существу.
Задачи преследования являются типичными примера-
ми дифференциальных игр. Теория дифференциальных
игр — сложная и разветвленная дисциплина, изучение ко-
торой требует глубокого знания многих специальных раз-
делов математики. Фундаментальный вклад в развитие
этой теории внесли советские математики Л. С. Понтря-
гин и Н. Н. Красовский.
Для исследования задач преследования с простым
движением требуется гораздо меньший запас знаний, по-
этому возникла идея изложения основных результатов на
языке, доступном для учащихся старших классов.
Задачи преследования с простым движением изоби-
луют интересными результатами, которые стали путе-
водной нитью в построении современного обширного
здания теории дифференциальных игр. Для их получе-
ния широко используются геометрические конструкции
и методы. Несмотря на внешнюю простоту постановки,
многие задачи преследования с простым движением на
сегодня являются серьезными математическими пробле-
мами.
Книга рассчитана на школьников старших классов,
интересую'щихся математикой. Опа не предполагает ни-
каких предварительных знаний, однако желательно зна-
комство с методом координат, понятиями вектора, геомет-
рического места точек и др. В то же время нетрадпци-
онность предлагаемого материала может потребовать не-
малого времени и терпения для глубокого усвоения.
4
В конце каждого параграфа приводятся упражнения,
решение которых поможет более глубокому пониманию
основных результатов.
В конце книги приведены нерешенные задачи для
исследования. Авторы считают, что для нахождения их
решения школьнику вполне достаточно внимательно изу-
чить предлагаемую книгу, хотя, конечно, наличие мате-
матических способностей было бы также желательным.
Авторы выражают благодарность Ю. С. Осипову за
поддержку, В. И. Благодатских и Н. Ю. Сатпмову за
внимание к работе.
ГЛАВА I
ГЕОМЕТРИЯ ПРОСТОГО ДВИЖЕНИЯ
§ 1.	Простое движение.
Постановка задачи преследования
В настоящем параграфе мы дадим определение про-
стого движения точки на плоскости, обратив особое вни-
мание па движение по ломаным с конечным числом вер-
шин, которое будет использовано нами в дальнейшем;
опишем две основные игры преследования на плоскости.
1.1.	Простое движение. Пусть точка Р начинает дви-
жение на плоскости из начального состояния (положе-
ния) xq. Если отмечать ее текущие положения, то мы по-
лучим на плоскости некоторую непрерывную кривую, ко-
торая называется траекторией движения. Будем произво-
/дить отсчет пройденного пути вдоль
траектории от начальной точки х0.
Во всяком движении длина пути s,
пройденного точкой Р, зависит от вре-
мени. Это обстоятельство позволяет
записать s как функцию времени: s —
= s(t) (рис. 2). Если известен способ
перемещения точки Р по этой траекто-
рии, то можно установить формулу,
“	определяющую положения точки на
Рис. 2 траектории в любой момент времени,
т. е. закон движения точки.
Траектория движения точки Р на плоскости может
представлять собой как прямую, так и кривую линию.
Соответственно этому движения разделяются на прямо-
линейные и криволинейные.
Простым движением называется такое движение, при
котором расстояние, пройденное точкой Р из начального
состояния xq, является линейной функцией времени:
6
здесь t — время, в течение которого происходило движе-
ние, s(Z)—путь, пройденный точкой Р из начального со-
стояния хо за время t, а величина р, представляющая
собой путь, проходимый точкой Р в единицу времени,
называется линейной скоростью точки. При простом дви-
жении величина р является постоянной и не зависит от
времени.
Таким образом, простое движение точки Р из началь-
ного местоположения хо на плоскости есть движение по
любой криволинейной траектории, исходящей из этой
точки, с постоянной линейной скоростью р. На рис. 3
изображены различные примеры простых движений из
ТОЧКИ XQ.
Простое движение точки Р может рассматриваться в
выпуклом множестве S на плоскости, т. е. в процессе
движения точка Р не покидает множество S. Напомним,
что множество называется выпуклым, если отрезок, со-
единяющий две любые его точки, целиком содержится в
этом множестве. На рис. 4 приведен пример простого
движения точки Р в квадрате.
1.2.	Простое движение по ломаным. Всюду в даль-
нейшем мы будем рассматривать лишь подкласс простых
движений, а именно всевозможные движения по лома-
ным с конечным числом вершин. Это означает, что мы
будем предполагать в дальнейшем, что точка Р, двигаясь
с постоянной линейной скоростью р из начального поло-
жения хо, может изменять направление своего движения
лишь конечное число раз. Отметим, что любое простое
движение может с достаточной степенью точности быть
аппроксимировано (приближено) простым движением по
ломаным с конечным числом вершин.
7
Изучим закон движения точки Р по ломаным с ко-
нечным числом вершин. Предположим, что на плоскости
введена ортогональная система координат хОу и в мо-
мент времени t = 0 точка Р находится в положении xq =
= (ж01, ^02) (рис. 5, а). Пусть точка Р в момент времени
t = 0 начинает движение в некотором фиксированном на-
правлении с постоянной линейной скоростью р. Это рав-
носильно тому, что точка Р, начиная с момента времени
t = 0, движется с некоторой постоянной вектор-скоростью
wo = (wqi, W02), гс'01 + «02 = р2 (рис- 5, б).
Точка Р, двигаясь с вектор-скоростыо wo в промежут-
ке времени [0, i], пройдет путь, длина которого равна
s = pi = ]/w201 + ipq2-t = I w011 = I iw01,
где |wol—длина вектора Wq. Если символом P(t) =
= (Pi(Z), ^2(0) обозначим положение точки Р в момент
t 0, Р(0) = «о, то будем иметь (рис. 5, а)
P(i) = xo + iwo
или в координатах
P(i)==(Pl(i)', Pi{t)) = (xOl + tlVOi, XQi + tWoi). (1)
Таким образом, при движении точки Р с вектор-ско-
ростыо wo закон ее движения описывается уравнени-
ем (1).
8
Пусть в момент времени t = t\ точка Р изменяет на-
правление своего движения и начинает перемещаться с
ПОСТОЯННОЙ вектор-скоростью Wi=(^n, ^12), W11 + U'12~
= р2 (рис. 5, б). Точка Р, продолжая движение с вектор-
скоростью wi из начального положения Р(Ц), в проме-
жутке времени [4, Z], t t\, пройдет путь, длина кото-
рого равна s = (t — ti)p — I (i - ti)' \vt I. Тогда при t A ti
имеем
P(Z) = P(ii) + (i-ii)wi
или в координатах
Р(*) = (Л(0, P2(f)) =
= (Pi(4) + (i-	Рг(4) + (£- 4)»12)'.	(2),
Если в формуле (2) учесть, что Р (4) = (яти + 4^oi, алэг ~h
+ 4^02) (см. (1)), то для точки P{t) при t > ti получаем
Р(0 = (Р>(/),Р2(0) =
= (.Toi + £1U?O1 + (£—£]) Шп, £02 + tilVQ2 + (t ~~ tl) U212) . (3)
Таким образом, закон движения точки Р на промежутке
времени [0, 4] (4 — момент изменения направления дви-
жения точки Р) описывается уравнением (1), а при t>
5- 4, когда Р двигается с вектор-скоростью wi,— уравне-
нием (3). Последующие изменения направлений движе-
ния точки Р приводят нас к аналогичным формулам.
Однако по предположению точка Р может изменять на-
правление движения лишь конечное число раз, поэтому,
начиная с некоторого момента времени t = tk, где к —
некоторое натуральное число, точка Р при всех £ > 4
будет перемещаться с некоторой постоянной вектор-ско-
ростью
"Т == (гглп	wki + wk2 = Р2-
Аналогично формулам (1), (3) можем получить
P(£) = P(4) + (£-4)ws,	£>4,
или в координатах
P(0 = (Pl(i);	=
= (Pi(4) + (£- t^WM, Р2(4) + (£- 4)1Щг) =
= (xqi + t[Woi + (4 — tt) wn + ... + (4 — 4-i) 1Щ-1 ] +
+ (f- 4) Wkl, £02 + tlW02 + (4 - tl) w12 + . . .
... + (4- tk-i)wk-i2 + (t - tk)wk2),
wo = (H',oi, И2О2), Wi=(«?n, и/12)', ..., Wft-1 =(г^Л-11, ^-12),
9
Wi = (wn, Wa)— постоянные вектор-скорости, выбранные
точкой Р в моменты времени 0, ii, i2, ..th соответствен-
но. Мы определили закон движения точки Р вдоль лома-
ной с началом в точке Р (0) и с вершинами в точках Р(it),
Р(Ц), ..P(tk). Таким образом, закон движения точки
Р по этой ломаной па отрезке времени [0, ij описыва-
ется уравнением (1), где vvo = (woi, ид®), w-’oi + ^ог = Р2—
вектор-скорость, выбранная точкой Р в момент времени
t = 0; на отрезке времени [it, i2] — уравнением (3), где
wi = (»п, wiz), и;2! + ii%2 = p2 — вектор-скорость, выбран-
ная точкой Р в момент времени t — ib и т. д.; начиная
с некоторого времени t = tk — уравнением (4), где =
= (гЩ1, иц2), ид2! + гг|2 = р3—вектор-скорость, выбранная
точкой Р в момент времени t — th.
Отметим, что движение точки Р по ломаным с конеч-
ным числом вершин можно также рассматривать на лю-
бом конечном отрезке времени [0, 0].
1.3.	Игра преследования с простым движением. Пусть
на плоскости задано выпуклое множество S. Точки Pt,
Р2, .. ., Рт и Е перемещаются в S, обладая простым дви-
жением с постоянными линейными скоростями Pl, р2, ...
.. ., pm и о соответственно*). Используя терминологию
теории игр, совокупность точек Pi, Рг, .... Рт назовем
преследующим игроком или нарядом преследователей Р,
а Е — убегающим игроком. Движение наряда Р и игрока
Е начинается в момент t = 0 из начальных положений
Р\ (0), Р2(0), ..., Рт(0), Е(0). Положения игроков Р\,
Р2,   Рт, Е в момент t > 0 обозначим соответственно
Pi (t), Pz(t), ..., Pm(t) и E(t).
Мы будем говорить, что наряд Р осуществил встречу
с Е, если хотя бы один из преследователей Р, наряда Р
осуществил встречу с Е, т. е. когда впервые положение
Е совпадает с положением хотя бы одного преследовате-
ля Pi из наряда Р. Преследование нарядом Р убегающе-
го Е начинается в момент времени t = 0 и завершается,
когда наряд Р осуществляет встречу с Е. Потребуем, что-
бы в процессе движения все преследователи из наряда
Р и убегающей Е не покидали множества 5. Целью на-
ряда Р является встреча с убегающим Е за минимальное
время, а цель убегающего Е — оттянуть момент встречи
или избежать ее, если это возможно.
*) Как было отмечено в п. 1.2, здесь и всюду в дальнейшем
рассматриваются только простые движения но ломаным с конеч-
ным числом вершин.
10
В каждый момент времени t > 0 игроку Е известно
свое положение и положение всех преследователей в этот
же момент времени. Каждый преследователь Р< из на-
ряда Р в момент времени t > 0 знает положения всех
членов наряда, включая себя, положение игрока Е, а так-
же направление движения игрока Е в этот момент време-
ни t, однако ему неизвестны будущие маневры Е, т. е.
Pi не знает, когда и как будет изменять игрок Е на-
правление своего движения в будущем.
Такую задачу преследования будем называть игрой
преследования с простым движением и обозначать Г(т,
1; 5), подчеркивая при этом зависимость от числа пре-
следователей и вида множества S. В случае, когда 5 сов-
падает с плоскостью, такую игру обозначим Г(пг, 1).
При необходимости также будем использовать запись
Г(РЬ Р2, ..., Pm, Е- S) или Г(Р1, Р2, ..., Рт, Е).
Конечное число 0 назовем оптимальным временем
преследования в игре Г (т, 1; 5) относительно началь-
ных положений Pi(0), Р2(0), ..., Р™(0) и £(0), если
выполнены следующие условия:
а)	для любых движений игрока Е существует способ
поведения наряда Р, гарантирующий ему встречу с Е
не позже, чем за время 0;
б)	существует такой способ поведения игрока Е, что
наряд Р не может осуществить встречу с Е до момента 0.
Если для конечного числа 0 выполнено только усло-
вие а), то число 0 назовем гарантированным временем
преследования относительно начальных положений Р\ (0),
Р2(0), ..., Рт(0) и Z? (0), а если для конечного числа 0
выполнено только условие б), то число 0 назовем гаран-
тированным временем избежания встречи относительно
начальных положений Pi(0), Рг(О), . ..,	Р„,(0)
и Е (0).
Пусть 0 — оптимальное время преследования относи-
тельно положений Pi(0), Р2(0), . .., Р™(0) и Е(0). Тог-
да любой способ поведения убегающего Е, при котором
наряд Р не может осуществить с ним встречу до момента
0 (условие б)), назовем оптимальной стратегией игро-
ка Е. Способ поведения наряда Р, при котором гаранти-
руется встреча с Е за время не позже, чем за время 0
(условие а)), назовем оптимальной стратегией наряда Р.
Под решением игры T{m, 1; S) мы будем понимать
нахождение оптимальной стратегии наряда Р, оптималь-
ной стратегии игрока Е и оптимального времени пресле-
дования.
11
Мы будем говорить, что в игре Г(т, 1; 5) из началь-
ных положений РЦО), Рг(0), .. Рт(0) и Е(0) возмож-
но убегание, если существует такой способ поведения
убегающего Е, что наряд Р не может осуществить с ним
встречу на любом конечном отрезке времени [0, 0]. Это
означает, что если перед началом игры Е поставил перед
собой задачу избежать встречи с нарядом Р в течение
любого конечного, но фиксированного заранее времени О,
то у него существует способ поведения, гарантиру-
ющий выполнение этой задачи при любых действиях
наряда Р.
1.4. Игра с «линией жизни». Пусть па плоскости за-
дано выпуклое множество S, не совпадающее с пло-
скостью. Границу S обозначим буквой L и назовем ли-
нией жизни. Точки Р|, Рг, .. ., Рт и Е, т. е. наряд пре-
следователей Р и убегающий Е, перемещаются в S, об-
ладая простым движением с постоянными линейными
скоростями pi, рг, ..., рт и о соответственно. Так же,
как и в игре Г(тп, 1; S), движение наряда Р и убегаю-
щего Е начинается в момент t = Q из положений РЦО),
Рг(О), ..., Рт(0) и Р(0); предполагается, что игроки Р
и Е в каждый момент времени t 0 обладают той же
информацией, что и в игре Г(т, 1; S). Цель наряда Р —
не допустить достижения границы — линии жизни L —
игроком Е до встречи с нарядом Р. Цель убегающего
Е — достижение линии жизни L, при этом избегая встре-
чи с Р до момента достижения L. Такую задачу пресле-
дования с простым движением назовем игрой с линией
жизни и будем обозначать G (т, 1; S). Если для началь-
ных положений Pi (0), Рг(О), . . ., Р,„(0) и Е (0) суще-
ствует способ поведения наряда Р, гарантирующий до-
стижение его цели при любых движениях Е, то способ
поведения назовем оптимальной стратегией наряда Р и
будем говорить, что в игре G(m, 1; 5) из начальных по-
ложений Pi(0), Рг(0), .... Р,„(0) и Е(0) выживание не-
возможно. Это означает, что если в игре G(m, 1; 5) из
начальных положений Pi(0), Рг(0), .. ., Р„, (0) и Е (0)
выживание невозможно, то оптимальная стратегия наря-
да Р гарантирует встречу с убегающим Е до достижения
им линии жизни L.
Если для начальных положений РЦО), Рг(О)', ...
.. .. Р„. (0) и Р(0) существует способ поведения убегаю-
щего Е, гарантирующий достижение его цели, то этот
способ назовем оптимальной, стратегией Е и будем гово-
рить, что в игре G(m, 1; S) из начальных положений
12
Pi(O), Рг(О), . .	Р,„(0) и Е(0) возможно выживание.
Это означает, что если в игре G (т, 1; 5) из начальных
положений Pi(0), Рг(0), ..Рт(0) и Е(0) выживание
возможно, то оптимальная стратегия Е гарантирует ему
достижение линии жизни L до встречи с Р.
Упражнения
1. Пусть Р(0) = (0, 0) и Р(0) = (0, 1), а игроки Р и
Е, начиная с момента времени t = 0, перемещаются с по-
стоянными вектор-скоростямн и —(2, 0), 7=(1, 0) соот-
ветственно. Найдите
а)	закон движения точек Р и Е, т. е. формулу для
положений P(t) и E(t) в каждый момент времени t > 0;
б)	точку и момент встречи Р с Е.
2. Рассмотрим игру Г(1, 1; S), где р = 2, о = 1 и
5 = {(ж, у): z/ = Q},
т. е. игроки Р и Е перемещаются в процессе игры лишь
на оси абсцисс.
а)	Докажите, что оптимальное время преследования
в игре Г(1, 1; 5) относительно начальных положений
Р(0) = (0, 0) и £(0) = (1, 0) равно 0=1. Оптимальная
стратегия для Р — перемещение с вектор-скоростыо и =
= (2, 0), для Е — перемещение с вектор-скоростыо v =
= (1,0).
б)	Найдите решение игры Г(1, 1; S) относительно
начальных положений Р(0) = (а, 0) и £(0) = (6, 0), а Ь.
3.	Рассмотрим игру <7(1, 1; 5), где р = 2, о=1 и
S = {(х, у): — 2 < х < 2, у — 0}
с линией жизни L = {(—2, 0), (2, 0)}, состоящей из двух
точек.
а)	Если Р(0) = (0, 0), то укажите множество всех на-
чальных положений £(0), из которых в игре Г(1, 1; S)
возможно выживание.
б)	Рассмотрим игру <7(1, 1; 5) относительно началь-
ных положений Р(0) = («, 0), — 2 С а < 2, и £'(0) = (6, 0),
— 2 b С 2. Определите, при каких значениях парамет-
ров а, b возможно выживание.
13
§ 2. Множество достижимости,
окружность и точка Аполлония
В этом параграфе будем предполагать, что 8 совпа-
дает с плоскостью и наряд Р состоит из одного пресле-
дователя Р.
2.1. Множество достижимости. Пусть преследователь
Р перемещается на плоскости в соответствии с простым
движением с постоянной линейной скоростью р > 0.
Множество всех точек z = (x, у) на плоскости, в кото-
рых может оказаться игрок Р в момент времени t, ис-
пользуя всевозможные движения по ломаным с конечным
числом вершии, начиная движение в момент t — 0 из
точки P(fi), назовем множеством достижимости игрока Р
к моменту t. Обозначим Н (A', R) (8 (A; R)) круг (ок-
ружность) с центром в точке А и радиусом R (см. спи-
сок обозначений).
Справедлива следующая
Лемма 1. Множество достижимости игрока Р к мо-
менту образует круг с центром в точке P(Q) и с
радиусом pt.
Доказательство, а) Пусть z е S (Р (0); pi), т. е.
z лежит на границе круга Я(Р(0); pi) (рис. 6, а). Тогда
Р может оказаться в точке z, двигаясь по полупрямой
[Р(0), z) (см. список обозначений), поскольку по полу-
прямой [Р(0), z) можно двигаться только в направлении
P(0)z, и длина пути, пройденного за время t с постоян-
ной линейной скоростью р, равна s(i) — pt = ]P(0)z|.
б) Пусть "Efl(P(0j; pt)\S(Р(0); pt), т. е. z—внут-
ренняя точка круга Я(Р(0); pt). В этом случае суще-
ствует достаточно много ломаных с конечным числом вер-
шин, двигаясь по которым, Р может оказаться в точке z
14
в момент времени t. Ограничимся лишь указанием одно-
вершинной ломаной. Для этого проведем серединный
перпендикуляр к отрезку [Р(0), z] (рис. 6,6) и на нем
отметим такую точку А, что 1Р(0)Л1 = pt/2. Очевидно,
что А е/7(Р(0); pt). Игрок Р может попасть в точку z
в момент t, перемещаясь до момента времени t/2 по по-
лупрямой [Р(0), Л), затем в течение такого же време-
ни — по полупрямой [Л, z).
в) Пусть z^77(P(0); pt), т. е. точка z лежит вне
круга 7/(Р(0); pt) (рис. 6, в). Так как игрок Р за вре-
мя t может пройти лишь путь, длина которого равна pt,
и pt < lP(0)zl, то очевидно, чт
в точке z в момент времени t.
Лемма доказана.
2.2. Окружность и точка
Аполлония. Пусть преследова-
тель Р и убегающий Е перемеща-
ются на плоскости в со-
ответствии с простым движе-
нием с постоянными линейны-
ми скоростями р и о, р > о > О,
и в начале игры
1Р(0)Р(0)! = Ь>0.
Предположим, что игрок Е,
начиная с момента вре-
мени t = 0, перемещается по
не может оказаться
некоторой полупрямой
[Е(0), В) (рис. 7). Пусть игрок Р, зная это направле-
ние движения игрока Е, начиная с момента времени
---------------------------------------->
t = 0, перемещается по некоторой полупрямой [Р(0), С),
обеспечивая встречу с Е в точке М. Тогда должно вы-
полняться равенство
I	№!или Р | Р(0) Л/1 о | Р(0) м [.	(5)
------->
Для различных полупрямых [Р(0), В) получаем раз-
личные точки встречи М, удовлетворяющие (5).
Лемма 2. Геометрическое место точек М =(х, y'j,
удовлетворяющих уравнению (5), является окружностью.
Доказательство. На плоскости выберем систе-
му координат хОу таким образом, чтобы £(0) = (0, 0),
15
Р = (О, — Ь). Тогда
\Е (0)Л/| = ТгЧ7?, |Р(0)М\ = Ь2+(г/ + &)2;
подставляя в (5), получаем
рУж2 + у2 — ol/х2 + (у + Ь)г,	(6)
Возведя в квадрат обе стороны уравнения (6), получим
р2 (х2 + у2) = о2 [ж2 + (у + Ь)2],
(р2 — о2) х2 + (р2 — о2) у2 — 2Ьо2у = Ь2<з2,
, , / bo2 V / а?ь V
X -J- I 11 —- —5-т =	2	2 I
\р -</
Из формулы (7) следует, что геометрическое место точек
М = (ж, у), удовлетворяющих уравнению (1), является
окружностью S(O[-, Ri), где
Р (0) ^1 = \Р (0) Е (0) | + | Е (0) <9Д =	=
р — о р о
(10)
/> _ ро I Р (0) Е (0) I рой
И — г 2	“ 2	2*	U1/
р — О	р — О
Лемма доказана.
Окружность S(O\' R\j была известна математикам
древнего мира и называется окружностью Аполлония, со-
ответствующей положениям Р(0) и Е(0). Наиболее уда-
ленную от Е(0) точку М на окружности Аполлония
5(<9i; 7?i) назовем точкой Аполлония и обозначим
А(75(0), Е(0)). Круг R\) назовем кругом Апол-
лония.
Лемма 3. A(P(0), E(0))==S(Oi; Z?i)D[P(O)', Е(0)).
Доказательство. Пусть М — точка на окруж-
ности Аполлония	Z?i), отличная от точки А =
~S(Op, 7?|)Л[Р(0), Е(0)) (рис. 7). Треугольник О^МА
равнобедренный, так как Ю1)Й| = ]€>1Л| = R\. Отсюда для
треугольника Е(0)М4 имеем
^Е(0)ЛЛ < ^E(V)MA,
16
следовательно.
|5(0) М\ < |5(0) АI,
т. е. А—точка на окружности Аполлония S(Op 5Д,
наиболее удаленная от Eq. Лемма доказана.
Из формул (9) и (И) следует, что
15 (0) Д|= 15 (0) | + 7?х =	(0)'  = Д}- (12)
Приведем некоторые свойства точки и окружности
Аполлония.
Лемма 4, Пусть М — некоторая точка на окружно-
сти Аполлония S(Op Ri) и игроки Р и Е перемещаются
----------------------->. ---------->.
по полупрямым [Р(0), М) и [5(0), Л/'), соответственно.
Тогда для каждого t, 0 < t < 15(0)il/|/o, отрезок
[P(Z), E(t)] параллелен отрезку [5(0), 5(0) J.
Доказательство. Зафиксируем некоторое t, 0 <
< t < 15(0)М\/о. Тогда для положении P(t) и 5(1) име-
ем (рис. 7)
15(0)5(1)1 =oi, 1Р(0)Р(.£) I = pt. (13)
Рассмотрим ДР (0) ME(0) и ДР(t)ME(t). Из формул (5)'
и (13) имеем
|В(0)М|	I Д (0) Д(<)1 _ и
| Р (0) М I	I Р (0) Р (t) I Р ’
откуда	(14)
| Е (0) М I -I Д(0) E(t) ] I Е р) М I а
| Р (0) М | - | Р (0) Р р) | “ | Р(*)ЛЛ ~ Р‘
Из формул (14) получим, что ДР(0)11/5(0)=° ДР(/)Л75(1)
(так как угол ДР (0)1175(0) общий для обоих треуголь-
ников). Следовательно, отрезок [Р (0), 5(0)] параллелен
отрезку [Р(1), 5(1)] при любом t, 0 < t < |5(0)М]/о.
Лемма доказана.
Лемма 5. Пусть М—некоторая точка на окружно-
сти Аполлония S(Op R\) и игрок Е перемещается по по-
лупрямой [5(0), 47). Тогда преследователь Р не может
осуществить встречу с Е до момента времени 15(0)717]/о,
т. е. \Е(0)М\/о — наименьшее время, за которое Р может
осуществить встречу с Е.
Доказательство. Зафиксируем некоторое t, 0 <
<t< |5(0)71/[/о. Игрок 5 в момент времени t оказывает-
ся в положении E(t), |5(0)5(/)| = st (рис. 8). Из лем-
мы 1 имеем, что при любом способе перемещения игро-
2 Л. А. Петросян, Б. Б. Рихспев	17
ка Р точка Р(t)е= Н(Р(0); pt). Обозначим Р' = 5(Р(0);
pt)) Я [7>(0)Л/). Треугольник P(O)P'£(t) тупоугольный.
Действительно, отрезок [Р(0), Е(0)] параллелен отрезку
[P(t), E(t)] (см. лемму 4), поэтому
Л £(0)Р(0)Р' + P(0)P'£(t) = 180°
и А. £(0)Р(0)Р'< 90°. Отсюда получим, что в треуголь-
нике P(6)P'E(t)
pt= |P(0)P'l < lP(O)£(t)l.	(15)
Из (15) имеем, что E(t)&Я(Р(0); pt), следовательно,
игрок Р при любом способе перемещения пе может ока-
заться в момент времени t в
точке E(t).
Таким образом, если иг-
рок Е перемещается по
[£(0), М), то игрок Р не мо-
жет осуществить встречу с Е
за время t, где t< I E(0)l/i /о.
С другой стороны, из
определения окружности
Аполлония следует, что если
Р будет перемещаться по по-
-----------------:->.
лупрямой [Р(0), Л/), то
встреча с Е произойдет в мо-
мент времени |£(0)Л/1/о.
Лемма доказана.
5(0i; Pi)—окружность, А =
Рис. 8
Лемма 6. Пусть
= А(Р(0), Е(0))— точка Аполлония. Тогда
а)	окружности S(OpR^, S ^Е (0); и S (0);
—— I касаются в одной точке А;
Р—
б)	Н (Ог; RJ с2Н(е (0); Д) <= Н [р (0); р-^);
в)	момент времени t = р является наименьшим мо-
ментом времени t > 0, для которого выполнено включение
Я(£(0); ot)<=H(P(0), pt).	(16)'
Доказательство. Утверждения а) и б) непосред-
ственно следуют из определения точек О], А и радиуса Ri
(см. (8) — (12) и рис. 9).
18
2*
19
в) Из утверждения б) следует, что при i = &/(р — о)
соотношение (16) выполнено. Зафиксируем t,
0^t<—.	(17)
р — а	' '
Тогда из формулы (17) имеем
(р — o)t<b, pt < b + at.	(18)
Рассмотрим точку В(1)е 77(£’(0); at) (рис. 10) такую, что
В(/)<Е(0), <?i),	\E(0)B(t)\ = at. (19)
Тогда из формул (18), (19) получим
|Р(0)В(()1 = |Р(0)£(0)| + |£(0)В(1) I = b + at>pt.
Отсюда
B(t)<£H(P(Q)- pt),
т. е. для любого момента времени t, O^.t<Z суще-
ствует точка B(t)t= Н(Е(0); at) и B(t)<£ Н(Р(0); pi),
т. е. соотношение (16) не вы-
полнено. Лемма доказана.
Л е м м а 7. Пусть М —
точка на окружности Апол-
лония S(Oi, Ri), и игроки Р
и Е, начиная с момента вре-
мени 1 = 0, перемещаются
по полупрямым [Р(0), М) и
[Е(0), М) соответственно.
Тогда окружность Аполло-
ния, соответствующая какой-
либо паре промежуточных
положений P(t) и E(t), 0<
< t < \Е (0) Л7|/о, касается
окружности S(Op, 7?i) в точ-
ке М.
Доказательство. За-
фиксируем t, 0 < t < 1/7(0),
М\1а. Пусть 5 (О2; ^2) —
ответствующая положениям
P(t) и E(t). Обозначим Oz=(P(t), E(t)) 0 (Оь М)
(рис. И). Из формул (8) —(12) имеем О2 е [Р (/), E(t)),
\E(t)O'2\ =	I p(t) 0'21 =	(20)
'	p“ — CT	[)' — o-
r> _ po | P (О Л (Q|	/9 1 \
2Q
Учитывая, что IР(t) Е(t) I > 0 при 0 < t < |£(О)ЛЛ/п,
из формулы (20) получим
I Р (°) 1 _ o2|P(Qg(0l _ О2
\Р{1}ЕЩ\	(р2 - о2) \Р	Р2- о2'
Из формулы (9) и учитывая, что \Р(0)Е(0) I = Ъ, имеем
l£(°>°il _	6о2 о2
|Р(0)£(0)|	(р2-о2)ь	р2’-о2’	{ >
Поскольку (Р(0), E(0))ll(P(/), Е(1)) (см. лемму 4), из
формулы (23) и теоремы Фалеса следует
) (0)	|Т?(/)О2| о2
]Р(0)£(0)|	|Рф£(()Гр2-а2'
Отсюда и из формулы (22) получаем, что Ог = О2, т. е.
М]. Треугольники Е(0)ЛЮ1 и E(t)MO2 подоб-
ны, следовательно,
\ОМ\ 1С>ЛЛ
I Z? (0 О21 = | Е (0) Ol | ;	(24)
отсюда и из формул (9), (И), (20), (21) получим
|й(0О21 • |°rwl ро|Р(рЕ(/)( р
I а- 7 1 -	| Е (0) О11	" л -i “ 2'
(25)
2	2
р — ст
Так как O2e[^i, 2W], из формулы (25) следует, что
окружности 5(Oi; 7?i) и 5(О2; Р2) касаются в точке М.
Отсюда также следует, что
II (О2; /?2)сЯ(01; 7?j).
(26)
Лемма доказана.
Упражнения
4.	Пусть P(0)sS—некоторое выпуклое множество
па плоскости и в процессе движения с постоянной линей-
ной скоростью р > 0 точка Р не может покинуть множе-
ство 5. Доказать, что в этом случае множество достижи-
мости игрока Р из начального положения Р(0) к момен-
ту времени t имеет вид
5ПЯ(Р(0); р/).	(27)
5.	Пусть Я(Р(0); pi) — множество достижимости игро-
ка Р к моменту времени t (лемма 1), точка Me
^5(Р(0); pt) п игрок Р, начиная с момента времени
21
t — Q, перемещается по полупрямой [Z’(O), М). Рассмот-
рим множество достижимости P(P(<i); р(< —<i)), где
О < t\ < t, т. е. множество достижимости игрока Р из на-
чального положения P(t\) к моменту времени t (за вре-
мя t — <i). Доказать справедливость следующего соот-
ношения:
2ИеЯ(Р(^); p(f-^))с Я(Р(0); pt). (28)'
6.	Пусть 5(0^ Я]) и А — окружность и точка Апол-
лония, соответствующие начальным положениям Р(0) и
Р(0). Доказать, что А — точка на окружности S{Op, R\),
наиболее удаленная от точки Р(0).
7.	Пусть игрок Р перемещается на плоскости с посто-
янной линейной скоростью р > 0, £>() и хеЯ(Р(0);
р(<)\5(Р(0); pt) (см. доказательство леммы 1, утвер-
ждения б)). Рассмотрим некоторую одновершинную ло-
маную [Р(0), A, z] такую, что игрок Р, перемещаясь до
момента времени |Р(О)А|/р по полупрямой [Р(0), А),
а затем, перемещаясь по полупрямой [A, z), в момент
времени t оказывается в точке z. Зафиксируем точку z и
рассмотрим множество всех таких одновершинных лома-
ных [Р(0), А, г]. Найти геометрическое место точек А.
8.	Пусть р > о > О, S(0\; Hi) и А(Р(О); Е(0))—точ-
ка и окружность Аполлония, соответствующие положени-
ям Р(0) и £(0), М — точка на окружности S(Op, 7?i), от-
личная от А(Р(О), Е(0)), и игроки Р и Е, начиная с мо-
мента времени t = 0, перемещаются по полупрямым
	> -------------
[Р(0), М) и [£(0), М) соответственно. Найти геометри-
ческое место точек Аполлония, соответствующих всем
промежуточным положениям Р(<) и E(t), 0 С t С
|Р(О)Л/|/о.
9.	Пусть р > о > О, М — точка на окружности Апол-
лония S(Oi; R\), соответствующей положениям Р(0) и
Р(0), и игроки Р и Е, начиная с момента времени t = О,
перемещаются по полупрямым [Р(0), М) и [2Г(0), М)
соответственно, а 5(Ог; Ра) и Aj — окружность и точка
Аполлония, соответствующие некоторой паре промежуточ-
ных положений P(ti) и E(t{), 0 «5 ti А |Р(О)Л/|/о.
Доказать неравенство
|Р(0)Ш)1 + \E(ti)Ai\ А |Р(0)А[,	(29)
где А — точка Аполлония, соответствующая положениям
Р(0) и Р(0).
22
§ 3. Стратегия параллельного сближения
Пусть преследователь Р и убегающий Е перемещают-
ся на плоскости в соответствии с простым движением с
постоянными линейными скоростями р и о, р> о>0. Си-
стему координат на плоскости выберем таким образом,
чтобы в момент времени t = 0 игроки Р и Е находились
Рис. 12
в положениях Р(0)' = (0, —Ь) и Е(0) = (0, 0), где Ъ —
= IP(0)F(0) I > 0. Укажем для игрока Р один способ
преследования игрока Е.
Пусть игрок Е, начиная с момента времени 4 = 0,
перемещается по полупрямой [Р(0), Л1) (рис. 12, «),
т. е. с вектор-скоростыо vx = (пп, v12), vh + ь>1-2 = оа
(рис. 12, б). По условию игры в момент времени 1 = 0
игрок Р знает Р(0)’, Е(0) и [£(0)', т. е. вектор-ско-
рость vi. Пока Е перемещается с вектор-скоростыо vi —
= (уц, Р12), предпишем для Р, начиная с момента време-
ни t = 0, движение с вектор-скоростыо
Uj = (uw и12) = (vu, Ур2 — 1^X1),	(30)
23
т. е. по полупрямой [Р(0), Pi), P(O)P1ffui (см. список
обозначений).
Пусть в момент времени t = t\ > 0 игрок Е решил
изменить направление своего движения и начал переме-
щаться по некоторой полупрямой [£(ii), Ла), т. е. с век-
тор-скоростью v2 =(f2i, ь'22), п21 + v22 = при этом пред-
положим, что на промежутке времени [О, Zj встреча Р с
Е не произошла. Тогда, начиная с момента времени t = tt,
игроку Р предпишем движение с вектор-скоростью
(31)
т. е. по полупрямой [Z’(O), Р2), P(0)P2Hii2.
Если игрок Е в некоторый момент времени t2 > /1 вновь
изменяет направление движения, то игрок Р изменяет
направление своего движения описанным выше способом,
и т. д.
При таком способе преследования игроком Р игрока Е
для всех t > 0 (до момента встречи Р с Е) отрезок
[P(t), E(t)] параллелен отрезку [Р(0), £(0)]. Действи-
тельно, при 0 «5 t ti из формул (30) и (31) для P(t) =
= (Pi(t), P2(t)) и Е(t) = (£'[(!), E2(t)) имеем (см. (1))
В (!) = (Bj (£), Е2 (<)) — (tvn, ^12);
р (0 = (Л (0> рг = (^п’1 Кр2 — vii — ь)>
т. е. Pi(() = £](/) при всех	следовательно, от-
резок [P(t), E(t)] параллелен отрезку [Р(0), Е(0)] на
этом промежутке времени. В частности, [Z’(O), P(O)jH
ll[P(ii), £(ii)]. Однако на отрезке [ib i2] W21 = П21, или,
что то же, Е\(t) = Pt (i), следовательно, [Р(<), Р(£)Р
П[Р(£), .£(£])] II [Р(0), £(0)]. При t > t2 доказательство
проводится аналогично.
Такой способ преследования игроком Р убегающего Е
назовем стратегией параллельного сближения или TL-стра-
тегией. На рис. 13, а, б в случаях р > о и р = о соответ-
ственно указаны примеры траекторий игрока Р при при-
менении им П-стратегип.
Следующая лемма в случае р > о устанавливает связь
П-стратегпи с окружностью Аполлония S(Oi; Pi), соот-
ветствующей положениям Р(0) = (0, —Ь) и £(0) = (0, 0).
Лемма 8. Пусть р > о, М—некоторая точка на
окружности Аполлония S(Op, Pi) и игрок Е перемещает-
24
ся по полупрямой [£(0), М). Тогда П-стратегия предпи-
сывает для Р движение по полупрямой [Р(0), М).
Доказательство. Перемещение игрока Е по по-
лупрямой (рис. 14, а) означает, что он двигается с
вектор-скоростью (рис. 14, б)
V = (^1, V1 + У2 = Р2>
vtt£(O)J/. Тогда П-стратегия предписывает
ка Р движение с вектор-скоростью
(32)
для игро-
(33)
25
и = (uv и2) = ]Zp2 — v{
Из формул (32) и (33) для P(t) и E(t) при
имеем
£(0 = (£1(0, ^2(0) = (^М>	(34)
р (С = (Л (0,	(0) =	- ь + t /р2-^). (35)
Определим момент времени t > 0, при котором проис-
ходит встреча Р с Е, т. е. P(t)— E(t). Для этого доста-
точно выполнения равенства
P2(t)=E2(t),	(36)
поскольку из (34) и (35) имеем Pi(t) = Ei(t) при всех
£ > 0. Воспользуясь (34) и (35), уравнение (36) можно
переписать в виде
tv2 = — Ъ + t ]/”р2 — и?,
откуда
Из неравенств
р2>о2 =	+ 1^2,
Р2 - И? > Vl
]Лр2 -	| Р2 | > *>2
следует, что в формуле (37) знаменатель
)Лр2 _ _ у2 > 0.	(38)
Подставляя (37) в (34) и (35), получим, что встреча Р
и Е происходит в точке
Р^) = Е^) =
(39)
Легко убедиться, что точка, определяемая формулой (39),
лежит на окружности Аполлония S(Oi; 7?i), т. е. коорди-
наты точки (39) удовлетворяют уравнению (см. (7))
гг2 + у2
to2 V
Р2=-<т2)
apb \2
р2 — о2/
(40)
--------->
Таким образом, если Е перемещается по [£(0), М), а Р
применяет П-стратегию, то встреча с Е произойдет на
26
окружности Аполлония 5(0]; R\), т. е. П-стратегия пред-
писывает для Р движение по [Р(0), М). Лемма доказана.
Лемма 9. Пусть р > о 5s 0; тогда для любого v =
= {v\, v-P), v2 + l>2 = о2, имеет место неравенство
У р3 — v2 — v2
р — и.
(41)
Доказательство. Умножим обе стороны неравен-
ства (41) на ]/р2 — и2 + v2 >0 (см. (38)):
(Ур2 — v2i)Z — v2 > (р — а) (]/"р2 — и? + р2),
р2 — v\ — v2 >(р — и) (j/p2 — v2! + v2),
р + и > ]/р2 — Hi + v2.
Последнее неравенство справедливо для
/	\	2 ,	2 о
= (vv v2)> vr + v2 = cf , поскольку
Р>УP2 — I't
любого V =
Лемма доказана.
Упражнения
10.	Проверить, что точка, определяемая форму-
лой (39), удовлетворяет уравнению (40).
И. Пусть р > о > 0 и игроки Р и Е в момент времени
£ = 0 находятся в положениях Р(0) = (0, 0) и £(0) =
= (а, 0), а > 0. Определить закон движения точки Р в
следующих двух случаях:
------->
а)	Е движется по полупрямой [Р(0), £(0)), а Р ис-
пользует П-стратегию;
б)	Е движется по полупрямой [£(0), Р(0)), а Р ис-
пользует П-стратегию.
12.	Пусть р > о > 0, Е перемещается по некоторой
---------------->
полупрямой [£(0), М), а Р использует П-стратегию,
перемещаясь при этом по полупрямой [£(0), N). Дока-
зать, что всегда
АЕ(0)Р(0)У < 90°.
27
13.	Пусть М — точка на окружности Аполлония
S(O[; РД, соответствующей положениям Р(0) и /ДО),
----------------------------------------------------->
игроки Р и Е перемещаются по полупрямым [Р(0), М)
и [2?(0), М) соответственно, а а = £АЕ(0}М,----------=
= А- АР (0)М, где А = А (Р(0), Е(0)) — точка Аполлония.
Доказать равенство
о sin а — р sin р.
14.	Пусть р = 1, о = 1, Р(0) = (0, 0), £’(0) = (2, 0)'.
Рассмотрим квадрат К с вершинами в точках (2, 1),
(4, 1), (4, —1), (2, —1). Предпишем игроку Е движение
вдоль границы квадрата К по часовой стрелке. Пусть Р
использует П-стратегию. Определите траекторию движе-
ния Р до момента встречи с Е и момент встречи.
ГЛАВА II
ИГРА ПРЕСЛЕДОВАНИЯ НА ПЛОСКОСТИ
§ 4. Преследование на плоскости
с одним преследователем
В этом параграфе рассмотрим игру Г(1, 1)*). На
плоскости преследователь Р и убегающий Е перемеща-
ются в соответствии с простым движением с постоянны-
ми линейными скоростями р и о. Преследование начина-
ется в момент времени t = 0 из начальных положений
/ДО) и £(0),
|Р(0)£(0) I =6>0.
Рассмотрим случай р > о. Пусть S((?o, Ro) и Ао—
окружность и точка Аполлония, соответствующие поло-
жениям Р(0) и Е(0) (см. § 2, п. 1.2).
Теорема 1. Пусть р > о; тогда в игре Г(1, 1) из
начальных положений Р(0) и Е(0) возможно завершение
преследования и оптимальное время преследования рав-
но 0 = 6/(р — о). Оптимальной для преследователя Р яв-
ляется li-стратегия, а оптимальным для убегающего Е —
*—• ' "    >
движение по полупрямой [£(0), Ло).
Доказательство. Пусть убегающий Е перемеща-
------------------------>
ется по полупрямой [£(0), Ао). Из леммы 5, когда М\ —
= А о, следует, что Р не может осуществить встречу с Е
до момента времени
I g (°) -4ol = Ъо Ъ __е
ст (р — о)-ст р — ст ’
т. е. если Е перемещается оптимальным способом, то Р не
может осуществить встречу с ним до момента времени 0.
*) В литературе по теории игр Г(1, 1) называют «преследова-
ние корабля катером-перехватчиком в открытом море».
29
Теперь докажем, что если игрок Е перемещается ка-
ким-то другим способом п двигается по некоторой лома-
ной траектории, а Р использует П-стратегию, то встреча Р
с Е произойдет не позже, чем за время 0.
Не ограничивая общности, предположим, что в начале
игры Р и Е находятся в положениях Р(0) = (0, — Ь) и
^(0) = (0, 0).
Пусть игрок Е, начиная с момента времени t = 0,
-------->
перемещается по некоторой полупрямой [Е(0), Pi)
(рис. 15, а), т. е. с вектор-скоростыо (рис. 15, б)
vi = (уи> М + у1з = °2-	(42)
Поскольку П-стратегпя предписывает для игрока Р дви-
жение с вектор-скоростыо (см. (30))
U1 (W11>	= (у11’ 'VР2	у11)>	(43)
то из (42) и (43) для положений Р(£) и E(i) при £>0
имеем (см. (1))
р(0 = (Л (С, р2(0) = (^п> - ь -м/р2 -Mi),
£ (t) = (Et (t), Е2 (t)) = (tvlv tv12);
>0
отсюда и из леммы 9, когда v = vi, при t Ss 0 получаем
W — P2(t) = Ъ — «(]/р2 —	— р12) < b — t (р — о). (44)
Пусть игрок Е в момент времени t = ti решил изменить
направление своего движения и начал перемещаться по
“ ............................... >
некоторой полупрямой [2?(£i), В2), т. е. с вектор-ско-
ростью
v2 = (п21, п22),	+ Р22 = о2,	(45)
Тогда П-стратегия предписывает для Р, начиная с мо-
мента времени t = fj, движение с вектор-скоростью
и2 = (н21, н22) = (н21, ]/"р2 — ^21),	(46)
и из (45) и (46) для положений P(i) и E(t) при t 5s ti
получаем (см. (2))
Р(0 = (Р1(0,Р2(/))=	______
= (^1 Gl) + (t — tl) V2V Р2 (Q + (^ — P2 — ^21) !
£(0 = ^(0, ^(i)) =
= (Pi(ii) + (i - ii)P2i, £’2(iti) + (i- ii)P22).
Отсюда при t 5® tt получаем
E% (О P2 (0 = E2 (^1) P2 (^1) (^	Q (j/"P2	^21 ^22)*
(47)
Из (44), в частности, при t = i; следует
ВД)- P2(«i)^&-Mp-°)’-	(48)
Теперь из леммы 9 и формулы (48) получаем, что
(см. (47)) при t > t\
E2(t)-P-2(t)^ b - «i(p - o)~(t - ti) (p - o) =
= b — i(p — 0),
t. e. неравенство (44) верно и при t t\. Если игрок Е
в некоторый момент времени t = i2 снова изменяет на-
правление своего движения, то вполне аналогичным об-
разом можно показать, что при t i2
Е2(1)-P2(t)^ b - t(p - о)
0 Т. д,
31
Таким образом, если движение Е происходит по не-
которой ломаной, а Р использует П-стратегию, то для
всех t О
E2(t) — Р2(0^ Ъ - Z(p - о).	(49)’
Поскольку при таком способе преследования Pi(t) = ^i(^)
для всех f 2? 0, то очевидно, что встреча Р с Е происходит
в момент времени t, когда E2(t) — P2(t) = 0, т. с.
E2(t) = P2(t).
Правая часть неравенства (49) обращается в нуль в
момент времени
отсюда получаем, что левая часть неравенства (49) обра-
щается в нуль в некоторый момент времени t, I С 9, т. е.
E2(t) = P2(t) в момент времени ?, следовательно, встреча
32
Р с Е происходит за время, не превосходящее 9. Теоре-
ма доказана.
Теорема 2. Пусть р > а и игрок Р использует П-
стратегию-, тогда при любом способе движения игрока. Е
на плоскости встреча Р с Е происходит в круге Н (О0, Ro).
Доказательство. Из теоремы 1 следует, что при
любом способе перемещения игрока Е по ломаным траек-
ториям встреча Р с Е произойдет за время, не большее
чем 9 — Ь/(р — о).
Рассмотрим некоторую траекторию игрока Е на плос-
кости до момента встречи с Р. Пусть ii,	^-1, Е,
О < t\ < ... < ZA-i < < 0,— моменты времени, когда Е
изменяет направление своего движения. Из леммы 4 сле-
дует, что отрезок (Р(0), £(0)1 параллелей каждому из
отрезков [Р(М,Ж)], [P(t2), E(t2)],	[P(tk), E(tk)]
(рис. 16,а). Пусть S(Op, Rt), S{02-, R2),..., S (Ok_p, Rk-i),
S(Ok; Rk)~ окружности Аполлония, соответствующие по-
ложениям P(Z|) и E(tP), P{ti) и E(t2), ..., P(4-i)
п£(^-1), P(fft) п £(£). Из определения окружности
Аполлония S(Ok; Rk) следует, что встреча Р с Е проис-
ходит на S(OA; /?й). Очевидно, что
5(Oft; Rk)c=H{Ok- Rk).	(50)
Из формулы (26) вытекает, что (рис. 16, а, б)
1ЦОк, Rk)^II(Ok_}- Rk^<=...ccH(Op, R^H{O0- Ro),
отсюда п из (50) получаем утверждение теоремы. Теоре-
ма доказана.
Упражнения
15. Докажите, что если р < о. то в игре Г(1, 1) из
любых начальных положений Р(0) и £(0), |P(0)E(0) I >
> 0 возможно убегание.
16. Пусть р>о>0, H(P(0); pt), //(£(0); ей)— мно-
жества достижимости игроков Р и Е соответственно из
начальных положений Р(0) и £(0) к моменту времени I.
а)	Докажите, что существует такой момент времени
t\ > 0, что
Я(Р(0)’, pt^H(E(O), of,)'.
б)	Обозначим символом t наименьший момент вре-
мени to, для которого имеет место предыдущее включе-
ние. Докажите, что t = 9 (оптимальное время преследо-
вания в игре Г(1, 1) из начальных положений Р(0) и
£(0)).
17. Рассмотрим игру Г(1, 1; S), где S — выпуклое
множество. Пусть в момент времени i = 0 игроки Р и Е
3 Л. А. Петросян, Б. Б. Рихсиев	33
находятся в S(P(0)'eS, £(0)eS)' и в процессе пресле-
дования не могут покинуть множество S. Доказать, что
в этом случае
6	\Р^}Е (0) |
Р -о
является гарантированным временем преследования.
§ 5. Преследование в полуплоскости
с одним преследователем
В этом параграфе мы рассмотрим игру Г(1, 1; £),
где L — полуплоскость с границей I и р > о > 0. Пресле-
дователь Р и убегающий Е в момент времени i = 0 на-
ходятся в положениях Р(0) п £(0), |Р(0)£(0) I > 0,
Расстояние от точки Р(0) до прямой I обозначим бук-
вой Ь. На плоскости введем систему координат хОу та-
ким образом, чтобы (рпс. 17, а)
L — Цх, у): у 0), Р(0) = (0, — b'j.
Мы будем говорить, что решение игры Г (1, 1; L)
сводится к решению игры Г(1, 1), если оптимальное
время преследования в игре Г(1, 1; L) совпадает с опти-
мальным временем преследования в игре Г (1, 1) относи-
тельно положений Р(0) п Е(0). Зафиксируем положение
Р (0) игрока Р; тогда существуют такие положения £(0)
игрока Е, что решение игры Г(1, 1; Л) из этих началь-
ных положений Р(0) и Р(0) сводится к решению игры
Г(1, 1). Справедлива следующая
34
(51)
то Е окажется в
для положений
(52)
5(0], 7?i), соот-
Лемма 10. Решение игры Г(1, 1; L} из начальных
положений Р(0) и /?(0) сводится к решению игры
Г(1, 1) тогда и только тогда, когда выполнено одно из
следующих условий: а) полупрямая [Р(0), £(0)) не пе-
ресекается с прямой I; б) полупрямая [Р(0), Е(0)) пе-
ресекает прямую I и имеет место неравенство
\Е{0)Р\>\Р^Р\	(
о	р ’
где D = [Р(0)\ £ (0)) П I.
Доказательство леммы предоставляется читателю.
Отметим геометрический смысл неравенства (51): ес-
ли игроки Р и Е будут перемещаться по полупрямым
[/ДО), D) и [£(0), D) соответственно,
точке D позже игрока Р.
Поэтому будем предполагать, что
Р (0) и Е (0) выполнено неравенство
|Д(0)£>| I Р (0) £> |
о	р *
В этом случае окружность Аполлония
ветствующая положениям Р(0) и Е(0), пересекается с
прямой I в двух точках. Символом М* обозначим ту из
них, которая лежит на большем расстоянии от точки
2Г(0), или любую из них, если обе лежат па одинаковом
расстоянии от Р(0), и назовем ее точкой Аполлония в
игре Г(1, 1; А).
Приведем сначала решение игры Г(1, 1; А) в одном
частном случае.
1. Случай [Р(0)£’(0) )-L Z. Предположим, что игрок Е
находится в начале игры в точке £’(0) = (0, —а),
(рис. 17, б).
Неравенство (52) в этом случае принимает вид
—	,	(53)
op’	v '
т. е. если игроки Р и Е, начиная с момента времени
t — 0, будут двигаться по полупрямым [Р(0), 0) и
[£(0), 0) соответственно, то игрок Е окажется в точке
О = (0, 0) раньше игрока Р. Окружность Аполлония
S (О0, Во), соответствующая положениям Р(0)==(0, —б)
и £(0) = (0, —а), где (см. (9) — (12))
d' /а Ь® аР А о'	а)	/^,/л
3’	35
I , -i / Ь2ог - а2р2 Д
пересекается с / в двух точках 1^± |/	, vj.
Так как обе эти точки лежат на одинаковом расстоянии
от точки £(0), то в данном случае точкой Аполлония
в игре Г(1, 1; L) для начальных положений Р(0) =
= (0, — Ъ) и £'(0) = (0, —а) является точка
(/“	2	2 2	\
у о).	(55)
Из (55) имеем
|^(0)М0*| = оУ^^.	(56)
Пусть игрок Е, начиная с момента времени t — 0, пе-
ремещается по некоторой
Рис. 18
положений Р(Д и £’(^1)
1лупрямоп [Е(0), В), а игрок
Р применяет П-стратегию.
Предположим, что при таком
движении существует мо-
мент времени t — при ко-
тором имеет место равенство
(рис. 18)
iymj_ тощ, (57)
о	р 2 v '
где Di = [Р(0)’, Р(0))П/-
точка пересечения полупря-
мой [Р(0), £(0)) и границы
I, т. е. в момент времени
t —1\ неравенство (53) для
выполняется. В момент вре-
мени t = t\ выполняется также условие
| Е (0) Е (fj | _ | Р (0) P(Q|
(58)
Очевидно, что такая полупрямая [£(0), В} всегда суще-
ствует, например, этим свойством обладает полупрямая,
параллельная границе полуплоскости L.
Рассмотрим семейство полупрямых [£(0), Р), для
которых такой момент ti существует, На каждой из по-
лупрямых этого семейства зафиксируем точку P(fi),
удовлетворяющую (57), (58), и рассмотрим множество
таких точек Е =(х, у).
36
Справедлива следующая
Лемма 11. Геометрическое место Е = (х, у) явля-
ется куском параболы.
Доказательство. Из определения П-стратегии
следует, что при ее использовании игроком Р положению
£’(ii) = (x, у) будет соответствовать положение P(fi) =
— (х, z) игрока Р, т. е. абсциссы точек E(ti) и Р(Г)
совпадают. Отсюда, учитывая, что (рис. 18)
имеем
|£(0)£(Л)1 = Ь.2 + (у + а)2,
IP(0)P(£i) I = l^2+(z+ Ь)2,
|£(ft)Z)il = у, |P(£i)Z)1| = z.
Соотношения (57) и (58) можем переписать в виде
/? + (у 4- а)2 = /? + (z 4-b)2
а	р *
У =	(59)
а р ‘
Из второго уравнения (59) имеем
Возведя в квадрат обе части первого уравнения системы
(59) и учитывая (60), получаем
Р2 [х2 + (у + а)2] = о2
(\ 2
-у- + fr)
р2х2 + р2у2 + 2р2ау + р2а2 = о2х2 + р2у2 + 2paby + с2Ь2,
2р (а& — ра) у — (о2 — о2) а:2 — (о2&2 — р2а2),
_ о2 — а2 2 оЬ 4- ра	(61)
~ 2р ('Jb — ра) Х 2р '
Мы получили уравнение параболы. Легко убедиться,
что парабола (56) пересекает прямую I в точках — М*
и Мо. Следовательно, в уравнении (61) (см. (55))
(62)
Таким образом, геометрическое место точек Е ==
= (z, y)e=L, удовлетворяющих условпям (57) и (58),
является куском параболы (61), где переменная х удов-
летворяет условию (62) . Лемма доказана.
37
Параболу (81) с ограничением (62) назовем грани-
цей перехода пгры Г(1, 1; L) к игре Г(1, 1) из началь-
ных положений Р(0) и £(0) п обозначим З’о. Теперь
выясним геометрический смысл кривой 2?о. Пусть игрок
Е, начиная с момента времени t = 0, перемещается по не-
которой полупрямой [£(0), В), пересекающей кривую
S’o, а игрок Р применяет П-стратегию. Тогда в момент
времени t = ti, когда точка Е(Р) оказывается на 2м,
решение пгры Г(1, 1; L) из положений P(fi) и E(tt)
сводится к решению игры Г(1, 1). Справедлива сле-
дующая
Лемма 12. Пусть М — точка на окружности Апол-
лония S(O0- Но) относительно положений Р(0) и £(0).
Полупрямая [£(0), Л7) пересекается с кривой 2м тогда
и только тогда, когда M^S(Oo', £о)П(£\/), т. е. если
----------------------------------------------->.
игрок Е перемещается по полупрямой [£(0), Л/), где
Л/.е=£(О0; H0)f)(L\l), и Р использует П-стратегию, то
существует момент времени t — t\ такой, что для поло-
жений P(ti) и Е (fj) выполнено условие (57).
Лемма 13. Пусть игрок Е, начиная с момента вре-
мени f = 0, перемещается по некоторой полупрямой
[£(0), В), при этом Р использует П-стратегию, а в мо-
мент времени t ~ ti для положений P(fi) = (Pi(fi),
Р2(Р)) и E(ti) = (£t (f)), £o(fi)) выполнено условие
a ' p ’
(63)
Тогда имеет место неравенство
| £ (0) £ (f3) | + | E (/J < | < | E (0) M* I, (64)
где Л/*— точка Аполлония в игре Г(1, 1; L) относитель-
но местоположений P(fi) и Е(ft).
Доказательство. Пусть игрок £, начиная с мо-
мента времени t — 0, перемещается с вектор-скоростью
v = (t’i, г2) (рпс. 19, б); тогда П-стратегпя предписывает
для Р движение с вектор-скоростью п =	|/"р-—
(см. (30)). Учитывая, что (см. рпс. 19, д) £(fj) = (fjVi,
—а + ри2), £ (Д) = (Мп — ^ + М^Р2 ~ л) (см. (34),
(35)), из формул (55) и (63) имеем
д,. _ (уА-мЛщ Л* ~‘Л)’ f‘, о).
38
отсюда	______________________
) I /(-& + н/р2-<-(“«+«•
V р — о
(65)
Теперь из (56), (65), учитывая, что E(ti)=oth нера-
венство (64) можем переписать в виде
zi + Т'-гЦ'(- & + г1/р2 -	~ (~ а + W <
И р — о
Перенесем й в правую часть неравенства (66). Учиты-
вая, что  z	> 0, возведем обе стороны не-
V Р2 — О2
равенства (66) в квадрат. Тогда получим
b /р2 —	— аи2 У & — а1 ]/р2 — о2.	(67)
Поскольку b > а, то
&]/'р2 — г-д — аи.2 > а (]/р2 —- к2 —	0.
Возведя в квадрат обе стороны неравенства (67), по-
лучим
54’? + а2 (р2 — г2) — 2аЪи, ]/р2 — v\ 0,
39
отсюда
(bv2 — а]/~р2 —	0.
Лемма доказана.
Лемма 14. Пусть игрок Е, начиная с момента вре-
мени t — 0, перемещается по некоторой полупрямой
[Е(0), 2?), пересекающейся с кривой З’о, и в момент
времени t — t\	а игрок Р использует П-стра-
тегию. Тогда имеет место неравенство (ср. (64))
\E(Q)E(t1)\ + \E(t1)D1\^\E(Q)M*\,	(68)
где D\ — \P(tP), E(i|))nZ.
Доказать лемму предоставляем читателю.
Теорема 3. Пусть р>о>0 и для начальных по-
ложений Р(0) и Е (0) выполнено неравенство (53). Тогда
в игре Г(1, 1; L) оптимальное время преследования
/~bi _ а±
равно 6=1/ —--------ъ (см. (56)). Оптимальной для игрока
F Р О'
Р является П-стратегия, а оптимальным для игрока Е —
движение по полупрямой [Е(0), л/*).
Доказательство. Пусть убегающий Е перемеща-
ется по полупрямой [Е(0). М*) (см. рпс. 17,6). Из лем-
мы 5, когда Л/1 = Л/0. следует, что Р не может осуще-
ствить встречу с Е до момента времени (см. (56))
| Е (0) < |
а
т. е. если Е перемещается оптимальным способом, то Р
не может осуществить встречу с ппм до момента вре-
мени 9. 
Пусть игрок Е перемещается в полуплоскости не обя-
зательно оптимальным способом и двигается по некото-
рой ломаной, а Р использует П-стратегпю. Тогда из тео-
ремы 1 (см. упражнение 17) следует, что встреча Р с Е
происходит за время 9|, пе большее чем	Пока-
жем, что 91 С 9. Здесь возможны два случая: а) встреча
Р с Е происходит в некоторой точке ЛЛ Z; б) встреча
Р с Е происходит в некоторой точке е L\l.
а)	Рассмотрим первый случай. Пусть Е(Р), Е(£г)<
..., E(^-i), Е^Д—вершины ломаной траектории игрока
40
Е (рис. 20), где 0 < t\ < /2 < . • • < h-i < tk < 0i и к —
некоторое натуральное число. Обозначим Л72’ • ••
...,4/4-!, Mk,точки,Аполлония в игре Г(1, 1; L), соот-
ветствующие положениям P(ti) и Е {ti), P(t%j и E(tp), ...
..., P(fft-i) и £*(^_1), Р(^) и E(th\.
Из леммы 13 следует, что
I Е Е (th) I + I Е (th) Л/£ КI £ Л/|,
| Е (tk_2) Е I + I Е (th^ Л/:_! |< I Е (/ft_2) Л/.:_21„
•...............................................(69)
\E(tl)E(,ti)\ + \E(t2)M*\^\E(t1)M*\,
\E(Q)E(i1)\ + \E(t1)M*1\^\E(O)M*o\,
где М1 = М*. Сложив неравенства (69), получаем
s~\E(0)E(t1')\ + \E(tl)E(t2)\ + ...
.,. + | Е {tk^ Е (th) | + | Е (tk) Ml | < I Е (0) М0*|, (70)
где s — длина пути, пройденного игроком Е на проме-
жутке времени [0, 01], т. е. до момента встречи с Р.
Из (70) и (56) следует
т. е. в рассматриваемом случае встреча Р с Е произойдет
за время, не большее чем 9.
б)	Рассмотрим второй случай, т. е. встреча Р и Е
происходит в некоторой точке L'\l в момент времени
(рис. 21). Пусть E(11), E(tt), .... Ш-,),
£(А)— вершины ломаной траектории игрока Е, где 0<
< ti < 12 < • • • < tk-i < th < 9i и /с —некоторое натураль-
ное число. По условию теоремы для начальных положе-
ний Р(0) = (0, — Ь) и £'(0) = (0, —й) выполнено нера-
венство (см. (52))
|£(0)Р|	|Р(0)Д|	,71)
Проверим это неравенство для точек P(fi) п £(ii), Р(1г)
и E(h), ..., P(th) и E(th). Возможны два случая: 1) су-
ществует такой наименьший индекс 1 i к, что
l^(fi)-p1Klf(t0Ddi	(72)
41
Рис, 21
где — E(ti))r\l (отрезок [P(ti'), Е(1>)] перпен-
дикулярен l, так как P использует П-стратегию); 2) для
всех индексов i, 1 г =< /с,
Wj <- \РУг)Рг\	(7Ч)
Пусть имеет место первый случай. Из (72) следует
(см. лемму 10), что решение игры Г(1, 1; L) из началь-
ных положений Р(0) и E(t{) сводится к решению игры
Г(1, 1). Поскольку i — наименьший индекс, для которо-
го выполняется (72) (см. (71)), то для положений
P(fi-i) и E(ti-i) выполнено неравенство
R0-1R-1I |Р(0-1)Д»-1!	,74)
а	р ’	'	'
где Di-i = [P(ti-i), £(£t-i))fU (если i = 1, то полагаем
£о = О).
Рассмотрим параболу SVi (рис. 21), т. е. границу
перехода от игры Г(1. 1; L) к игре Г(1, 1) относительно
начальных положений P(F(-i) и ^(Л-i) (см. (57) —
(59), (61), (62)). Из (72) п (74) и леммы 12 следует,
что существует единственный момент времени
Л,] такой, что	E(tt)) П S’,-i = E(J), т. e. в мо-
мент времени t игрок Е, перемещаясь вдоль отрезка
[E(if_i), E(ti)], пересекает параболу S’t-i. Таким обра-
зом, в момент времени t = t выполнено равенство (см.
(51), (57))
\PWD’\ \E(iW\
......  =	  .—	.	I / D)
где D' = [P(F) , E(t)) П I = (£i (F), 0) , следовательно (см.
лемму 10), решение пгры Г(1. 1; Z) из положений P(t)
и Е (Т) сводится к решению пгры Г(1. 1). Из теоремы 1
вытекает, что в игре Г(1, 1) из положений P(t) и Е (F)
встреча Р с Е произойдет за время, не большее чем
р - о *
(76)
Из формул (75) и (76) имеем (см. рис. 21)
|Р(О£Т)1 = I Р (7) Д' I - I £ (7) Д' I = I Д (7) Д'|
р — о	р — а	а
Отсюда и из (76) получаем, что для длины пути s',
пройденного игроком Е с момента времени t — t до
43
момента встречи с Р, имеет место оценка
s' — \E(t)E(t,')\ + |£’(Z,)£’(Z,+ i) I +...
...+ \E(QE^)\^\E(t)D'\. (77)
Из леммы 14 следует, что
| Е Е (Z) | + | Е (t) D' | < | Е (t^)	(78)
где — точка Аполлония, соответствующая положе-
ниям Р(£,-1) и	Из леммы 13 получаем
I Е (£;-2) 7s | + | E (ti-i), 9/;_j |	| E Mi_2 j.
| E ((J E (t2) | + | E M*2 | < | E (ZJ M* |,	(79)
\Е(О)Е^\ + \Е^)М*\^\Е(О)М*о\.
Выпишем выражение для длины пути s, пройденного
игроком Е с момента времени t — 0 до момента встре-
чи с Р:
s= '5(0)£(Z,)l + \E(ti)E(t2)\ +...+ |E(Z(_1)F(Z)I +
+ \E(t)E(tt)\ + ...+ \E(tk)E(Bi)\.
Теперь, используя неравенства (77), получаем оценку
IE(O)E(Z,) I + \E(h)E(h) I + ...
...+ \E(t(-^E(tt)\+ \E(tt)E(t) \ + \E(t}D'\.
Складывая неравенства (78), (79), получаем
\E(O)E(t1)\ + \E(t1)E(tz)\+ ... + \E(tl.1)E(ti)\ +
+ \E(t{)E(i)\ + \E(T)D'\<\E(Q)Ml\
и получаем оценку s | Е (0) МJ|, т. е. время до момен-
та встречи
е, < -Г <	_ е.
1 а	о
Аналогично показывается, что и во втором случае
(см. (73)) существует момент времени 01) такой,
что решение игры Г(1, 1; L) из положений P(i) и Е(1)
сводится к решению игры Г(1, 1). Используя это обстоя-
тельство, мы п в этом случае можем получить оценку
(76). Теорема доказана.
44
2. Общий случай.
Теорема 4. Пусть р > о > 0 и для начальных по-
ложений Р(0) и Я(0) выполнено неравенство (52). Тог-
да в игре Г(1, 1; А) оптимальное время преследования
Q = \Е(0)М*\1а, где М* — точка Аполлония в игре
Г(1, 1; Л) для положений Р(0) и £(()), Оптимальной
для Р является- П-стратегия. а оптимальным для Е —
я
движение по полупрямой [.£7(0), М*).
Доказательство. Пусть игрок Е, начиная с мо-
мента времени t — 0, перемещается по полупрямой
--------
[£(0), М*}, тогда из леммы 5 (Mi = М*) следует, что Р
не может осуществить встречу с Е до момента времени
|£(О)Я*|/о = 0.
Пусть теперь игрок Е перемещается в полуплоскости
L по некоторой ломаной траектории, а игрок Р использу-
ет П-стратегию. Покажем, что в этом случае встреча Р
с Е произойдет не позже, чем за время 0.
Через точку М* проведем прямую Z|, перпендикуляр-
ную полупрямой [Р(0), Я(0)), и символом Я обозначим
полуплоскость с границей Ц,
содержащую точки Р(0) и
Е(0) (рпс. 22). Рассмотрим
игру Г(1, !;• Я) из началь-
ных положений Р(0) и Я(0).
Очевидно, что точка М* яв-
ляется точкой Аполлония в
игре Г(1, 1; Li) из началь-
ных положений Р(0) и Е(0)
и [Р(0), Я(0)) -L Z], При лю-
бом способе перемещения
игрока Е из начального по-
ложения Е (0) па промежут-
ке времени [0, 9] в полу-
плоскости L его траектория
содержится в множестве
достижимости Н(Е(0); 00) П
и имеет место включение
Рис 22
L к моменту времени 0,
Я(Я(0); 00) П £ <= Я(Я (0); G0)П
Здесь Я(Я(0); 00) П Я —множество достижимости игро-
ка Я к моменту времени 0 в полуплоскости L\.

Поскольку [5(0), 5(0)]-L I], из теоремы 3 получаем,
что в игре Г(1, 1; Li) при любом способе перемещения
игрока па промежутке времени [0, 0] в полуплоскости
Li и, в частности, в множестве Я (5(0); 00) П Li, т. е.
когда игрок Е перемещается в полуплоскости Li (дей-
ствуя как бы в игре Г(1, 1; ЕД) встреча Р с Е произой-
дет не позже чем за время 0 = |Е(0) Следователь-
но, в игре Г (1, 1; L) из начальных положений 5(0) и
Е (0) встреча Р с Е произойдет не позже чем за время
0. Теорема доказана.
Упражнения
18.	Докажите лемму 10.
19.	Рассмотрим игру Г(1, 1; 5), где р>о>0 и L —
= {(z. у): у<0), 5(0) = (0, -&), &>0.
Найдите множество всех начальных положений 5(0)’,
для которых решение игры Г(1, 1; L) из начальных по-
ложений 5(0) и 5(0) сводится к решению пгры Г(1, 1).
20.	Докажите лемму 12.
21.	Рассмотрим игру Г(1, 1; £). Пусть р > о > 0,
Р(0)е£, Е(0)е5 и Я(5(0); pi)0 L, Я (5(0); о«)П L -
множества достижимости игроков Р и 5 к моменту вре-
мени t при условии, что игроки не могут покинуть полу-
плоскость L.
а)	Докажите, что существует такой момент времени
С > 0, что
Я (5(0); р(,) 0 5 с Я(5(0); р«1)'П5.
б)	Обозначим t наименьший момент времени t, для
которого имеет место предыдущее включение. Докажите,
что ( — оптимальное время преследования в игре Г(1, 1;
£) из начальных положений Р(0) и 5(0).
22.	Рассмотрим игру Г(1, 1; 5), где р>о>0. За-
фиксируем начальное положение Р(0) пгрока Р и рас-
смотрим множество всех начальных положений 5(0) =
= (х, у) пгрока 5 таких, что [5(0), 5(0))-LZ и выпол-
нены неравенства (52), (53). Докажите, что в игре
Г(1, 1; L) оптимальное время преследования 0 достига-
ет наибольшего значения, когда Е(0)еЕ
23.	Докажите, что в игре Г(1, 1; 5) при р < о воз-
можно убегание.
24.	Рассмотрим игру Г(1, 1; L) из начальных поло-
жений Р (0), 5(0) игроков 5и5пр>о>0. Пусть по-
Лупрямая [Р(0)Р(0))’ пе перпендикулярна к границе I,
для положений Р(0) и Е(0) выполнено неравенство
(52) и М* — точка Аполлония в игре Г(1, 1; L). Дока-
жите, что в этом случае оптимальной будет также сле-
дующая стратегия игрока Р: перемещаться вдоль полу-
прямой [Р(0), М*) До момента времени t, когда впервые
точка E(t) попадает па перпендикуляр [Р(0, D (0 ] или
на полупрямую М*), т. е.
P(t)s[P(f), AZ*]U[P(f)', Z)(t)],
где Z)(i) = (Pi (7), 0) (P(7) = (Pi(/)', P2(F))). Начиная c
момента времени t = t использовать П-стратегию.
§ 6. Преследование на плоскости
с несколькими преследователями
Рассмотрим в этом параграфе игру Г(т, 1). Пресле-
дование происходит на всей плоскости, и наряд Р состоит
из т преследователей Pi, Р2, ,.Рт, т > 2. Игра начи-
нается в момент времени t — О из положений РДО),
Р2(0), ..Рт(0) и Е(0). Буквой К обозначим наимень-
содержащий точки
ший выпуклый
Pi(0), Ра(0), ..., Рт(0), а
символом Ко — границу мно-
жества К (см. список обо-
значений) .
Всюду в этом параграфе
будем предполагать, что в
игре Г(т, 1) для начальных
положений Pi(0), Р2(0), .,.
..., Рта(0) и £(0) выполнено
условие
многоугольник,
Р (0)
£(0)£ К\К0,	(80)1	Рис. 23
т. е. игрок Е в начале игры не «окружен» преследовате-
лями из наряда Р (рис. 23).
Мы будем говорить, что решение игры Г (Рь Р2; Р) =
— Г (2, 1) сводится к решению игры Г(1, 1), если опти-
мальное время преследования в игре Г (2, 1) совпадает с
оптимальным временем преследования в одной из игр
Г(РЬ Е) или Г(Р2, Р), т. е. для обеспечения встречи за
оптимальное время наличие в наряде Р — {Pi, Р2) одного
из преследователей является излишним.
47
Будем говорить, что наряд Р применяет П-стратегию,
если каждый преследователь Р, из наряда Р применяет
П-стратегию.
Сначала приведем решение игры Г (2, 1)', т. е. рас-
смотрим случай, когда наряд состоит из двух пресл-едо-
вателей Pi и Р-г. Легко заметить, что в игре Г (2, 1) для
любых начальных положений Pi(0), Рг(0) и Е(0) вы-
полнено условие (80).
1. Игра Г(2, 1). Рассмотрим случай pi = p2 = p>0.
Не ограничивая общности, будем предполагать, что в на-
чале игры Р\ и Рг находятся в положениях Pi (0) =
= (—6, 0) и Рг(0) = (6, 0) соответственно, где b > 0
(рис. 24). (Очевидно, что в случае 6 = 0 решение игры
Г (2, 1) сводится к решению игры Г(1, 1).)
а)	Пусть игрок Е в начале игры находится в поло-
жении £(0) = (—а,
(ср. (52), (53)).
а
а
0), а>0, и выполнено неравенство
(81)
Символом Мх обозначим точку с координатами
= \ (81 82)
\ У р* ®	/
Теорема 5. Пусть pi = p2=p>o, игроки Pi, Р% и
Е в начале игры находятся в положениях Р( (0) = ( —Ъ, 0),
Р2(0) = (6, 0) и Е(0) = (—а, 0) соответственно и выпол-
нено неравенство (81). Тогда в игре Г(2, 1) из началь-
ных положений Pi(0), Ра(0) и Е(0) оптимальное время
I Е (0) М* I Л)? _ а2
преследования равно 0 =-1----:---= "у ~------~ЛСР- (56))
48
Оптимальной для наряда P — {Pt, Р2} является И-страте^
гия, оптимальным для Е — движение по полупрямой
[Ё^МГ).
Доказательство. Обозначим
L\ = {(х, у): х С 0),
Еч = {(.г, у): х > 0},	(83)
I — {(х, у): х — 0).
Введем двух псевдоигроков Е* и Е*. В начале игры
они находятся в положениях Ех (0) = (— а, 0) п £, (0) =
= (а, 0) соответственно, т. е. в момент времени t = 0
Е* (0) — Е (0), При t > 0 движения псевдоигроков Еу и
Е*2 определяются следующим образом. Если игрок Е
перемещается в L\, то движение совпадает с Е, дви-
жеппе получается симметричным отоораженпем дви-
жения Е относительно прямой /; если игрок Е, пересе-
кая I, переходит в полуплоскость Lz, то движение Е.г
совпадает с Е, а движение Ег получается симметричным
отображением движения Е относительной прямой I. Та-
ким образом, псевдоигрок при всех перемеща-
ется в полуплоскости Ц, а псевдоигрок Ег — в L2 и в
каждый момент времени положение E(t) игрока Е
совпадает по крайней мере с одним из положений £\(0
или Е2 (/) псевдоигроков Е2 и Е2.
Рассмотрим две игры преследования в полуплоскости
(см. (23)): Г(Р1, £*; LJ из начальных положений Рг (0) =
= (-М) и £*(0)=(—а, 0). [РД0), Е*(0))±ЦТ(Р2, Е2-
£г)аз начальных положений Рг (0) — (£>, 0) и £2(0) = (a, 0),
[Р2 (0), Е2 (0)) I I. Легко убедиться, что точка М* (см.
(82)) является точкой Аполлония в обеих играх- Г (Рх, Е*;
Л) и r^ E'-Lt).
Пусть игрок Е перемещается по полупрямой
---.---->
[£ (0), Л/i); тогда из теоремы 3 следует, что игрок Pt
не может осуществить встречу с Е = а Р2 — с псев-
допгроком Ег до момента времени 0. Так как при лю-
бом г, O^i<0, в ДР (0) Е2 (г) Е (г) (см. рис, 24)-
|р2(0)р;(о1<|рио)^(01>
4 Л, А. Петросян, Б. Б. Рихспен	49
то игрок Р2 также не может осуществить встречу с Е до
мом ента времени 0.
Пусть теперь игрок Е перемещается по некоторой ло-
ман ой траектории, а наряд Р использует П-стратегию. Из
теоремы 3 следует, что в играх Г(Р1, Е*; L^, Г (Р2,
£2; Т2) из начальных положений Л(0) и Е* (0), Р2 (0) и
Е2 ( 0) соответственно возможно завершение преследо-
вания не позже, чем за время 0i, 0j «5 0, т. е. Рх (0Х) =
= Е\ (0J и Р2 (0Х) = Ег (0J. Так как положение игрока
Е в момент времени i = 0i совпадает по крайней мере
с одним из положений Ег (0,) или Е.г (0г), то в игре
Г(2, 1) из начальных положений Pi (0), Р2(0) и Е (0)
возможно завершение преследования не позже, чем за
время 01	0. Теорема доказана.
б)	Пусть игрок Е в начале игры находится в поло-
жении Ё(0) = (—а, с), с^О, с > 0, и выполнено нера-
венство (80) (рис. 25). Символом М2 обозначим точку
Аполлония в игре Г (Pi, Е; Lt):
Ml = (0, у*).
Теорема 6. Пусть pi = p2 = p>o, игроки Pi, Р2 и
Е в начале игры находятся в положениях Pi (0) = (—b, 0),
Р2 (0) = (5, 0) и Е(0)~(—а, с) соответственно и выпол-
нено неравенство (80). Тогда в игре Г (2,1) из началь-
ных положений Pi(0), Т2(0) и Е(0) оптимальное время
преследования 0 «= | Е (0) Ml l/п (ср. с теоремой 4). Оп-
50
тимальной для наряда P — {Pi, Р^} является YI-стратегия,
оптимальным для Е — движение по полупрямой [.£7(0),	)•
Доказательство. Введем двух псевдоигроков
£* и Ег. В начале игры они находятся в положениях
Е* (0) = (— а, с) и £2 (0) — с) соответственно, т. е.
в момент времени t = 0 положение Ег совпадает с поло-
жением £, £j(0) = £(0). При i >0 движение игроков
£j и Ег определяется следующим образом. Если игрок
£ перемещается в Е\ (см. (83)), то движение Ех совпа-
дает с £, движение £2 получается симметричным ото-
бражением движения £ относительно прямой I (см.
(83)); если игрок £, пересекая I, переходит в полупло-
скость Ьг, то движение £2 совпадает с £, а движение
£j получается симметричным отображением движения £
относительно прямой I.
Рассмотрим две пгры: Г (Рр £*; Zq) из начальных
положений Pi(0) ==(—&, 0)и£*(0) = (—а, с); Г(Р2, Е^', L2)
из начальных положений Р2(0) = (Ь, 0) и £2(0) — (а, с),
Далее доказательство теоремы 6 может быть продолжено
аналогично доказательству теоремы 5 с использованием
теоремы 4.
2. Игра Г (иг, 1). Рассмотрим случай pi>p2>...
,.. > pm > о. Буквой 0 обозначим наименьший момент
времени t > 0, для которого выполнено условие (см. уп-
ражнение 16)
m
Н(Е(0),ое)с \J H(Pt(0);PlQ).	(84)
1=1
Теорема 7. Пусть pi > р2 > ... > рт > о и для на-
чальных положений РД0), РДО), ..., Рт(0) и £(0) вы-
полнено условие (80). Тогда в игре Г(иг, 1) оптимальное
время преследования равно 0.
В основе доказательства теоремы 7 лежит следующий
геометрический факт.
Лемма 15. Пусть К' — наименьший выпуклый мно-
гоугольник, содержащий точки А[, Л2, ..Ат, и
т
H(A;R)cz U Я (А; Я),
i=l
где R > 0, R, > 0 для всех 1=1, 2. .... т. Предположим,
что точка А лежит на границе К' или вне ее. Тогда
4*	51
существует такое k, l^k^m, что Н (A; R~)<=^H(Ak; RPj,
или существуют i и j, i=£j, 1 < i < m,	такие,
что
H(A- R)cH(At-, Rt)UH(Aj; R,),
t. e. круг H(A; R) можно покрыть не более чем двумя
кругами из совокупности кругов H(Ait R6), i — 1,2,..m.
Из леммы 15 получаем, что если для некоторого мо-
мента временп 0 имеет место включение (84), то най-
дутся два индекса о, г2, h h, такие, что
Н (Е (0), об) cz Н (Рц (0), Pii0) U Н (Р^ (0), р.26).
Однако в этом случае оптимальное время преследования
в игре Г(т, 1) совпадает с оптимальным временем пре-
следования в игре Г(2, 1) между нарядом Р — [Pt .Р^],
состоящим из двух преследователей Р^Р^, и убегаю-
щим Е, которое равно 0 (см. теорему 6). Это и доказы-
вает теорему 7.
Упражнения
25.	Рассмотрим игру Г (2,1), где pi 7- р2 > о > 0. За-
фиксируем начальные положения Pi(0) и Р2(0) игроков
Pi и Р2. Найдите множество всех начальных положений
Е(0) игрока Е таких, что решение игры Г (2, 1) из по-
ложений Pi (0), Р2(0) и Е(0) сводится к решению игры
Г(1, 1).
26.	Найдите решение игры Г (2, 1) из произвольных
начальных положений Р\ (0), Р2(0) и Е(0) в следующих
случаях:
a)	pi = р2 > о > 0;
б)	pi > р2 > о > 0;
в)	pi > р2 = о > 0.
27.	Докажите, что в игре Г (2, 1) при условии pi <
< р2 < о возможно убегание.
28.	Рассмотрим игру Г(2, 1) из начальных положе-
ний Pi(0) = (—Ь, 0), Р2(0) = (5, 0) и Е(0) = (—а, с), где
pi=p2>o>0 и выполнены неравенства (см. теорему 5)
а
о
р ’
О 0,
и пусть Л/*=(0, у*) (см. рис. 25).
Докажите, что в этом случае следующая стратегия
наряда P = {Pi, Р2) также будет оптимальной: игроки Р[
и Р2 перемещаются по полупрямым [РДО), Jf*) и
52
[Р2(0), Л/*)' соответственно до момента времени t, когда
впервые точка E(t) попадает на границу треугольника
т. е.
P(F)e[P1(i)P2(O]U[P1(i)JP]U[P2(i)JP],
далее, начиная с момента времени t = i, наряд Р =
= {Pi, Рг) использует П-стратегпю.
29.	Докажите лемму 15 в случае, когда т = 3, Rt> R,
i = i, 2, 3.
30.	Докажите теорему 7 в случае, когда т = 3, pi >
> Р2 > рз > о и	где Л'— треугольник с верши-
нами в точках Р\ (0), Рг(0), Рз(0).
ГЛАВА III
ИГРА С «ЛИННЕИ ЖИЗНИ»
§ 7. Преследование с одним преследователем
В этом параграфе мы найдем решение игры G(l, 1; S)
с «линией жизни» в случае, когда S — выпуклое множе-
ство на плоскости с границей I. Разберем подробно слу-
чай, когда множество S представляет собой полупло-
скость. Напомним, что в игре G(1,1,S) цель игрока Р
состоит в том. чтобы не допустить достижения границы —
линии жизни I — игроком Е до встречи с Р. Цель убега-
ющего Е — достижение линии жизни Z, избегая при этом
встречи с Р до момента ее
достижения. По условиям
игры игрок Р в процессе
преследования не может
покинуть множества S.
1. Случай полуплоско-
сти. Выберем систему коор-
динат таким образом, что-
бы ось абсцисс совпадала
с границей I полуплоско-
сти, а множество S пред-
ставлялось в виде (рис. 26)
S={(r, у)-. у^О}, Р(0) =
= (0, -&)es, E(0)^S,
&>0.
la). Рассмотрим под-
случай р > о > 0.
Теорема 8. Пусть р > о > 0. Тогда в игре G (1, 1; S)
невозможно выживание игрока Е в S тогда и только
тогда, когда круг Аполлония Н(Ор, 7Ц) относительно на-
чальных положений игроков Р(0), Е(0) не пересекается
с границей I полуплоскости S.
54
Доказательство. Предположим, что H(Oi, 7?1)П
П/ = 0, и пусть E(t) — некоторая ломаная траектория Е
из начального состояния £(0)eS. Тогда согласно тео-
реме 2 при использовании игроком Р П-стратегии точка
встречи Р с Е содержится в круге Аполлония II (Oi, Ri),
а поскольку И (<9|, Ri) HZ = 0, то Е не может достичь гра-
ницы I множества 5 до его встречи с преследователем Р.
Покажем, что в этом случае траектория P(Z) игрока Р
не покинет множества 5. Траектория E(Z) является лома-
ной с конечным числом вершин. Обозначим эти вершины
Е(0), E(Z|), ..., E(th), ..., E(tn), где t = t„ — момент
встречи. Поскольку Н(О\, /?i)HZ = 0, то все вершины
—5, /с = 1, 2, ..., п. Пусть Р(0), P(Zi), ..Р(Е), 
..., P(tn)— вершины ломаной траектории Р, реализовав-
шиеся при использовании им П-стратегип и при условии
движения Е по траектории E(t). Количества вершин на
ломаных траекториях E(Z), P(t) совпадают, и эти верши-
ны проходятся пгрокамп в одни и те же моменты вре-
мени tk, к = 1, 2, ..., п. Рассмотрим полупрямую [Е(0),
E(Zi)) п пусть Mi — точка ее пересечения с окруж-
ностью Аполлония 5(Oi, /?|). Тогда по определению
П-стратегии имеем, что P(h) принадлежит отрезку
[Р(0), ЛД], п поскольку Р(0)е5, Mi <=S, то из выпук-
лости 5 получаем, что P(Zi)e5. Пусть теперь Н(О2; IE) —
круг Аполлония относительно начальных положений
Е(С), P(ti). Согласно теореме 2 Н(О2; И?) <= II (О
сЗ, Рассмотрим полупрямую [E(Zi), E(t?)) и пусть М2 —
точка ее пересечения с окружностью Аполлония S(O2; Ri)
относительно положений Р(Е), Е (t\). Тогда по опреде-
лению П-стратегии P(t2) принадлежит отрезку [P(ti),
ЗД], и поскольку Р (Е) е 5, Л/2 — 5, то из выпуклости 5
получаем, что Р(?г)е5 и т. д. Предположим, что P(ZA)!=
s S. Рассмотрим теперь круг Аполлония II(Ok+i, Rk<.i)
относительно положений E(Zft), P(tk). Согласно теореме 2
H(Ok+i, Rk+[)c:H(Ok, R8)<=-...<= II(О2, R2)<=H(Oi, Ri)<=S.
Рассмотрим полупрямую [E(th), E(tk+i)) п пусть Mk¥i —
точка ее пересечения с окружностью Аполлония
5(О),+ |; Rk+i) относительно местоположений P(ZS), E(tk).
Поскольку P(tk+i) принадлежит отрезку [P(tk¥t), AZh+i]
п P(tk)^S, Mh+i^S, то из выпуклости 5 получаем, что
Р (tk+i)<= S. Таким образом, мы показали, что все верши-
ны Р(0), Р(Е), ..., Р(Е), ..., P(tn) ломаной P(t) при-
надлежит 5, тогда из выпуклости 5 получаем, что
и ломаная траектория P(t) принадлежит 5 при
О t А
55
Пусть теперь H(Oi, 0 и пусть М е H(Q\, ЙД 9
,П I. Предпишем игроку Е движение из точки Е (0) по
полупрямой [£(0), М). Пусть М\ — точка пересечения
полупрямой [£(0), М) с окружностью Аполлония
£i). Поскольку Л/е[£(0), ЛЛ) и 5 выпукло, то или
М\ <^1, пли М\ 5, Но М\ есть точка встречи при условии,
что игрок £ движется по полупрямой [£ (0) Л7) и игрок Р
использует П-стратегпю. При этом движение игрока Р
прямолинейно, т. е. игрок Р перемещается по полупря-
мой [£(0, ЛЦ) п при любом способе движения Р встреча
с £ до достижения им точки М невозможна (лемма 5).
Следовательно, в этом случае у игрока Р не существует
способа преследования, который бы мог обеспечить встре-
чу с £ до момента достижения им «линии жизни» точки
М <= I — границы множества S. Теорема доказана.
16). Подслучай р = о > 0.
Теорема 9. Пусть р = 6 > 0. В игре G(l, 1; 5)
всегда Е может достичь границы I множества S до его
I
поимки преследователем, кроме случая, когда полупря-
мая [£(0), £(0)) пересекает I и перпендикулярна I.
Доказательство, Если полупрямая [£(0), £(0))
не пересекает I п не параллельна I, то £, двигаясь по
--------
полупрямой [£(0), £(0)), очевидно, достигает I, оста-
ваясь в процессе движения от игрока Р на расстоянии,
не меньшем чем i£(0)£(0) I (рис. 27).
56
Рассмотрим теперь случай, когда полупрямая (F(0),
Р(0)) параллельна I или пересекается с I, но не перпен-
дикулярна I. В этом случае Е всегда может достичь I,
двигаясь в направлении к границе по полупрямой
[Е(0), Н) параллельно перпендикуляру, проведенному
к отрезку [£(0), Р(0)) (рпс. 28).
Если теперь полупрямая [£’(0), Р(0)) перпендику-
лярна I и пересекается с I, то при любом движении Е по
ломаной E(t) с вершинами в точках E(t\), ..£(£), ...
игрок Р, используя П-стратегию, движется по ломаной
P(t) с вершинами в точках P(£), ..£(£), . ., причем
полупрямые [E(tk), P(th)) всегда перпендикулярны гра-
нице I и для длин отрезков [£(£), £(£)] пмеет место
оценка
1Е(МР(<4)1 с|е(0)Р(0)|
для всех к, к — 1, 2, ... (расстояние \E(f)P(t)\ не воз-
растает в процессе движения). Кроме того, из свойства
П-стратегии (параллельность отрезка [£(£), P(t)] при
всех i > 0 отрезку [£(0), Р(0)]) следует, что полупря-
мые [E(t), P(t)) пересекаются с I и будут перпендику-
лярны I при всех t. Следовательно, Е не сможет достичь
I до его встречи с Р (рис. 29).
57
Однако игрок Е, двигаясь по полупрямой
[Р(0), £7(0)), может гарантировать отсутствие встречи
с Р в течение сколь угодно большого отрезка времени;
Теорема доказана.
2. Случай круга.
Теорема 10. Пусть р>6>0 и S — круг. В этом
случае в игре G(l, 1; 5) невозможно выживание игрока
Е в S тогда и только тогда, когда круг Аполлония
JI(01, 2?|) относительно начальных положений Р(0),
£(0) не пересекается с границей I круга S.
Доказательство проводится вполне аналогично .
доказательству теоремы 8. Если Н(О\, Л|)П I = 0, то для '
любого движения E(i) игрока Е, исходящего из началь-
ного положения E(0)eS при использовании игроком Р
П-стратегпи, точка встречи Р с Е содержится в круге
Аполлония Н(О\, 7?|), т. е. не может достичь границы I
круга S до его встречи с преследователем Р. Остается
лишь показать, что в этом случае траектория P(t) игро-
ка Р не покидает множества 5. Это легко установить,
используя выпуклость круга S и дословно повторяя соот-
ветствующие рассуждения, приведенные при доказатель-
стве теоремы 8. Аналогично получаем, что Е всегда мо-
жет избежать встречи в S при Н(О\, Ri) I ¥= 0.
Теорема It. Пусть р — 6 > 0. В С?(1, 1; 8) из всех
начальных состояний Е(0), Р(0), 1Е(0), Р(0)| > 0, воз- i
можно выживание.
Доказательство. Очевидно, что для выживания '
игроку Е достаточно двигаться по полупрямой
[Р(0), ЕДО)) до момента достижения границы I круга S.
Упражнения
31.	Пусть р 'ж- о > 0, Е(£) — некоторая ломаная траек-
тория Е из начального положения Е(0) с вершинами
Е(Е), Е(О), .... Е(А), ..., Е(£) п игрок Р использует
П-стратегию. Докажите, что в этом случае Р будет пере-
мещаться по ломаной траектории, исходящей из началь-
ного состояния Р(0) с тем же числом вершпн, располо-
женных в точках ЕДЕ), P(h), • • •, ЕДА), ..., P(t„), т. е.
изломы траекторий игроков Р и Е происходят в одни
п те же моменты времени.
32.	Пусть р>о>0 и 5 — произвольное выпуклое
множество на плоскости. Покажите, что в игре G (1, 1; 8)
58
невозможно выживание тогда и только тогда, когда круг
Аполлония Н (О,; Z?t) относительно положений Р(0),
Е (0) не пересекается с границей I множества S.
33.	Рассмотрим игру G(l, 1; 5), р > о > 0, при допол-
нительном предположении, что игрок Р в процессе дви-
жения может пересекать границу I множества 5. Выве-
дите необходимые и достаточные условия невыживания
игрока Е в S в случае, когда S — произвольное (не обя-
зательно выпуклое) множество на плоскости.
34.	Рассмотрим игру G(l, 1; 5), р = о > 0, в случае,
когда 5 — произвольное ограниченное выпуклое множе-
ство на плоскости. Докажите, что если |Р(0)2?(0) I > 0,
то в этом случае всегда возможно выживание.
35.	Пусть р > о > 0, S — полуплоскость с границей I
и в игре 0(1, 1; S) из начальных положений Р(0), £’(0)
выживание невозможно (т. е. круг Аполлония 1ЦО\; ЯД
относительно нескольких положений Я(0). Я(0) не пере-
секается с Д. Рассмотрим модификацию G'(l, 1; 5) игры
G(l, 1; 5), в которой целью игрока Е является макси-
мальное сближение с границей I множества S, а целью
игрока Р является встреча с Е на возможно большем
удалении от границы. Найдите оптимальный способ по-
ведения игроков Р и Е в игре G'(l, 1; 5).
36.	Найдите оптимальный способ поведения игроков
Р п Я.в игре G'(l, 1; 5) в случае, когда р>о>0 и S —
произвольное выпуклое множество на плоскости.
§ 8. Построение зон убегания и зон встречи
Продолжим исследование игры G(l, 1; 5) с «линией
жизни» в выпуклом множестве S на плоскости.
Положим p/o—w, w>i. Множество начальных поло-
жений P(0)eS, E(0)e.S игроков Р и Е, при которых
возможно выживание в игре 0(1, 1; 5), называется зо-
ной убегания. Зону убегания для фиксированных Saw
мы будем обозначать У3(5; w). Аналогично, множество
начальных положений P(0)eS, Е(0)е5 таких, что в
игре 0(1, 1; S) выживание невозможно, называется зо-
ной встречи. Зону встречи для фиксированных S и w мы
будем обозначать через ВЗ (S; w).
Очевидно, что'множества У3(5; w'j и B3(S; w~) не
пересекаются между собой, а объединение этих множеств
(при 1Р>1) совпадает с множеством всевозможных пар
{Р(0), Я(0).}, где Р(0)е5, Я (0)е5.
59
Теорема 12. Пусть заданы игры (7(1, 1; SJ,
G(l, 1; 5г), ..G(i, 1; S„) с линией жизни, где Si, S2, • • •
..Sn — выпуклые множества на плоскости, п — некого-
/ п \
рое натуральное- число, и игра G 1, 1; р| 5; ]; тогда
\ /
/ п	\	п
ВЗ п = п В3(5г-;гс).
V=1	J	i=l
п
Доказательство, Заметим, что пересечение П S,
1=1
выпуклых множеств S,-, i = 1, 2, ..п, является выпук-
лым и поэтому определение игры с линией жизни в мно-
п
жестве П S; корректно,
i—i
Пусть начальные положения {Т’(О), Е (0)} =
(п	\
П S,;w .Это означает, что если преследование
i=i	у
начинается из положений Р(0), £"(0), то игрок Е не мо-
71
жет достичь границы множества П до его встречи с
п
преследователем Р; так как Si zz> П Si, то он тем более
i=i
не может этого сделать в игре (7(1, 1; S,) и, следователь-
но, {Р(0), Р(0)} - B3(S,; w) при i — 1, ,,га, т. е.
{Р (0), Е(0)} е= П ВЗ (Su о,),
i=l
и мы получаем, что
ВЗ ( П S,; дэ П В3(5;;гс),
\г—1	/	1=1
Пусть теперь {Р (0), Е (0)} е П В3(5г;ш). Это оз-
1-1
начнет, что игрок Е не может достичь границы ни одного
из множеств S( до его встречи с преследователем в S(,
п
т. е. он не может достичь и границы множества П Si до
i=i
его встречи с Р в этом множестве, а поэтому {Р (0),
Е (0)} е ВЗ f П S-; иЛ и ВЗ Г П S,; и;') cz П ВЗ (S;; w),
\i=l	/	\i=1	/	i=1
Теорема доказана.
60
Теорема 13. Пусть = piM >	= Рг/о2; тогда
ВЗ (5; №1)= ВЗ (5; w2).
Доказательство. Пусть {Р (0), £(0)} е ВЗ (5; w2).
Тогда круг Аполлония В (О2; Ri) относительно началь-
ных положений Р(0), 2Г(0), рассчитанный для скоростей
рг, 02 игроков Р и Е, содержится в S. При этом его
радиус
в - immi
2	Р2/°2 - °2/Р2 '
Радиус круга Аполлония 7?i) относительно тех
же начальных положений Р(0), £(0), но для скоростей
Pi, 01 игроков Р, Е
р _ I р (°) £ (°) I
1	Р^-^/Р/
Центры кругов Н(Ой RP) и Н(О2-, Rz) расположены на
одной прямой (Р(0), £(0)). Обозначим символами At,
Bi точки пересечения прямой (Р(0), £(0)) с окруж-
ностью Аполлония S(Oi; RP) и символами А2, В2 — точки
пересечения прямой (Р(0), 2?(0)) с окружностью Апол-
лония 5(О2; RP) (рис. 30). Тогда имеем
РIЕ (0) Ву |
IД (0) р (0) I
<р|Р(0)Р2| =
I Д (0) р (0) I
1	11	Р!~ °!	Р2-°2
(см. (10), (И)) и R2>R\. Следовательно, H(Oi; 7?])с:
с//(О2; Rz), и поскольку П(О2-, R2)c S ({Р(0), Е(0))е
= B3(S; ггг)), то /7(Oi; R})<=S, т. е. {Р(0), Е(0)}е
eB3(Si; wi\- Теорема доказана.
61
Определим вид зоны встречи B3(S; w) для случая
полуплоскости. Зафиксируем точку Р(0) и рассмотрим
множество всех возможных начальных положений Е(0),
для которых Р может гарантировать встречу с игроком Е
в S. Это множество будем обозначать B3P<0)(S; iv). По-
строим множество B3P(0)(S; w) для случая, когда S'-
полуплоскость (рпс. 31).
Беря за центр точку Р(0) = (0, — Ь), выведем в поляр-
ных координатах уравнение геометрического места тех
точек Е(0) = (г, ф) (см. список обозначений), для кото-
рых встреча происходит на границе I множества S. Это
множество совпадает с множеством тех начальных со-
стояний £(0), для которых круг Аполлония H{Ot; R\)
касается границы I множества S. Из формул (11), (12)
имеем:
D | Р (0) Е (0) | ро гро
•“1 -------2	2	2
о — о~ о — а
го2
р — а
где г = |Р(0)£’(0) I. Тогда из треугольника P(0)O'#i
(рис. 31) получаем соотношение
2
т гра . гр	/Ог\
Ь = 08~~<?~ + c°s <₽•	(85)
62
Если начальное положение Е(0) игрока Е таково, что
его полярные координаты (г, ср) удовлетворяют нера-
венству
2
-2rpq 2 + —г cos <р — b > 0,	(86)
р — а р — з'
то круг Аполлония Н(О}; 7?i) относительно начальных
положений Р(0), Е(0) пересекает границу I области S
и игрок Е может избежать встречи в S. В то же время
из любой другой начальной точки Е (0) (при фиксиро-
ванном начальном положении Р(0)) игрок Е не может
достичь границы I области S до его встречи с Р. Таким
образом, неравенство (86) определяет множество
УЗг(0) (5; w), а противоположное неравенство — множе-
ство ВЗР(0)(5; и-).
Уравнение границы (85) множества УЗр1о)(5’; иД
можно записать в виде
/ ,..2	\
,	/ га	if	\
О = Г ----------1---5---- cos ф
I W — 1 If" — 1 I
или
Поскольку w — р/о > 1, уравнение (87) представляет со
бой уравнение ветви ги-
перболы с фокусом в
точке Р(0), симметрич-
ной относительно прямой
[Р(0), О).
Проведем построение
множества B3E(ot (5; w)
для случая полуплоско-
сти (рпс. 32). Беря за
центр точку £(0) = (0, с),
выведем в полярных
координатах уравнение
геометрического места
тех точек Р(0) = (г, ф), для
которых встреча происхо-
дит на границе I множест-
ва S. Это множество сов-
падает с множеством тех
начальных положений Р(0), для которых круг Аполлония
Н(СЕ; Pi) касается границы I множества S. Длина отрезка
[£(0), GJ равна (см. (11)) го2/(р2 — о2). Из треугольника
63
E(0)OiO' (рис. 32) получаем соотношение
с = "Г...Тcos Ф + ТР° f	(88)
р — а	р — а
Если начальное положение Р(0) игрока Р таково, что его
полярные координаты (г, ф) удовлетворяют неравенству
2
2--° 2 + 2~ ~ " "2 COS ф — С > 0,	(89)
р — О р — о
то круг Аполлония Н{0\\ относительно начальных по-
ложений /ДО), Е(0) пересекает границу I области 5, и Е
может набежать встречи в S. В то же время из любого
другого начального положения Р(0) (при фиксированном
начальном положении Е(0)) Р может гарантировать встре-
чу с Е до его достижения границы I множества S. Таким
образом, неравенство (89) определяет множество
УЗЕ(0)(5; w), а противоположное неравенство определяет
множество ВЗр(О) (S; w).
Уравнение границы (88) множества УЗЕ(о, (5; w) мож-
но записать в виде
/ w ,	1
с == г -----—5------cos ф
М-i ш2-1
или
(,?  1)
1 -Г — c°s ф
Поскольку 0 < 1/w = о/р < 1, то в полярных координатах
это уравнение представляет собой уравнение эллппса с фо-
кусом в точке Е(0) не центром в точке А.
Упражнения
37.	Пусть р>о>0 и 5 — полуплоскость. Выведите
уравнение границы множества УЗ^оДЗ; w) в декартовых
координатах.
38.	Пусть р > о > О и S — полуплоскость. Выведите
уравнение границы множества УЗЕ(о, (5; и>) в декартовых
координатах.
39.	Пусть р > о > 0. В игре G(l, 1; 5) постройте мно-
жество УЗР(0)(5; w) в случае, когда множество S являет-
ся квадратом, выпуклым многоугольником, кругом. Для
64
этих же случаев произведите построение множества
УЗ£(0) (S; iv).
40.	Пусть в игре G(l, 1; S) начальные положения
Р(0), Е(0) игроков Р и Е принадлежат зоне убегания,
т. е. {Р(0), £(0)} е У3(5; щ). Докажите, что существует
такая полупрямая [£(0), М), что при движении пгрока Е
вдоль нее и при любом способе движения РЦ) пгрока Р
пара точек {Р(Ц, £ЦЦ будет всегда принадлежать зоне
убегания до момента достижения игроком Е границы I
множества S, т. е. у пгрока Р нет способа движения, обес-
печивающего выход пары {ПЦ), E(t)} из множества
УЗ(5; w).
41.	Пусть в игре G(l, 1; 5) начальные положения
/’(О), Е(0) игроков Р и Е принадлежат зоне встречи, т. е.
{/’(0), £(0)1 е B3(S; w). Докажите, что при использова-
нии игроком Р П-стратегии и при любом способе движе-
ния игрока Е пара точек {P(t), Е(Р)} будет принадлежать
зоне встречи до момента встречи игроков Р и Е, т. е.
у игрока Е нет способа движения, обеспечивающего вы-
ход пары UJ(£),	113 множества B3(S; w).
§ 9. Преследование с несколькими преследователями
В этом параграфе мы исследуем игру G(m, 1; S) пре-
следования с линией жизни с нарядом преследователей
Р = (Pj, ?2, • • •, Р^,}, состоящим из т преследующих игро-
ков и одним убегающим Е. Задача наряда Р — осущест-
вить встречу с Е в полуплоскости S хотя бы одним из его
участников Р„ i = 1, .. ., т, до момента достижения игро-
ком Е границы I полуплоскости S. Цель пгрока Е проти-
воположна. Здесь мы будем предполагать, что участники
наряда Р могут в процессе преследования покидать мно-
жество S.
1. Игра <7(2, 1; 5). Здесь S — полуплоскость с грани-
цей I и pi 3s рг 3s о > 0.
Теорема 14. Пусть piSsp2>o>0. В игре
G(2, 1; 5) из начальных положений РДО), Рг(О), £(0)
выживание невозможно тогда и только тогда, когда пере-
сечение кругов Аполлония Н (Op Н (О2; R2), соответ-
ствующих начальным положениям РДО), £(0) и Р%(0),
£(0) соответственно, не пересекается с границей I мно-
жества S.
Доказательство. Пусть
Н(Ор, Л1)ПН(О2-, R2){\1 = 0,
5 Л. А. Петросян, Б. Б. Гпхсиет)	65
т. е. не существует общих точек между границей I полу-’
плоскости S и пересечением кругов Аполлония Н(О\; 7?1)Л
Л Н{02-, Ri). Пусть E(t) — некоторая ломаная траектория
Е из начального положения Е(0) и наряд Р использует
11-стратегию. Обозначим E(tP^,E(tP^ соответствую-
щие точки встречи игроков Pi и Р2 с Е. Пусть для опре-
деленности tp.^tpj тогда встреча осуществится в S
в том случае, когда Е 6= 5\Z. Из теоремы 2 имеем,
что точка встречи Е(ip ) при использовании П-страте-
гии игроком Pi принадлежит кругу Аполлония //(Оц R\),
т. е. Е ) <= Н (Оу, PJ. Она также принадлежит кру-
гу Я(О2; Р2), так как в противном случае игрок Р2 при
использовании П-стратегии мог бы осуществить встречу
раньше, чем за время ip , но tP^'^tP^. (Е не может вый-
ти за пределы круга Аполлония, избежав встречи, если Р2
использует П-стратегню.) Таким образом, точка встречи
Е (tP ) Е Н (Оу, Ry) Q Н (<?2; /?2). Аналогичное включение
имеет место и при ipf>ip2- Обозначим буквой:
М ту из точек Е и Е [tp^, для которой значение
времени встречи минимально (т. е. точку с минимальной
величиной tPi, i = 1, 2). Точку М назовем точкой встре-
чи. Таким образом, мы показали, что множество точек
встречи при использовании П-стратегии нарядом Р —
— (Pi, Р2} принадлежит пересечению кругов Аполлония
Н (Oi; Л1)ПЯ(О2; Ri)- Следовательно, если множество
Н(Ог, /?1)П И (О2-, Ri) не пересекается с I, то Е не может
избежать встречи в S. Покажем теперь, что если
Н(О\-, R\)I\H(O2-, R2) пересекается с границей Z, то игрок
Е всегда может избежать встречи. Действительно, если
пересечение с I непусто, то существует точка М е I одно-
временно лежащая на границе множества I/(Oi; Ri) П
П//(О2;Я2) (рис. 33).
Пусть для определенности М e5(Oi; R}). Кроме того,
поскольку M^H(Oi’, 7?1)ПЯ(О2; Р2), то М е= II(О2; Р2).
Рассмотрим прямолинейное движение Е из начального по-
ложения £(0) в точку М. При таком движении встреча
Е с Р\ происходит в точке М на границе I (если Р\ ис-
пользует П-стратегпю) и игрок Р> не может осуществить
встречу с Е до достижения игроком Е точки М (лемма 5).
Покажем, что игрок Р2 также не может осуществить
встречу с Е до достижения им точки М. Здесь возможны
два случая: точка М лежит на границе круга Аполлония
66
Н (Ог; 7?г) п точка М является внутренней точкой круга
Н (<72; й2). В первом случае М принадлежит окружности
Аполлония 5(О2; Лд) и согласно лемме 5 встреча с Е
до достижения точки М невозможна. Пусть теперь М
является внутренней точкой круга Аполлония Н(О2; R2)',
Рис. 33
тогда согласно лемме 5 встреча в любой точке отрезка
[/ЦО), Л/] с Е невозможна.
Таким образом, игрок Е. перемещаясь из Е(0) в М.
гарантирует выживание в S. Теорема доказана.
2. Игра G(m, 1; S). Рассмотрим случай, когда S полу-
плоскость.
Теорема 15. Пусть pi А р2 А .. . А р,„ > о u S — по-
луплоскость с границей I. Тогда в игре G(m, 1; S) невоз-
можно выживание в том и только том случае, когда пере-
пг
сечение кругов Аполлония П	относительно
7=1
начальных состояний Р,(0), А(0), i = 1, .. ., m, не пере-
секается с границей I множества S.
Доказательство. Дословно повторяя доказатель-
ство теоремы 14 (в п. 1), можно убедиться в том, что мно-
жество точек встречи при использовании П-стратегии на-
рядом Р = {Р\, Р2> .. ., Рт} принадлежит пересечению кру-
т
гов Аполлония П	Таким образом, если
i-1
т
П	не пересекается с I, то выживание невоз-
1=1
т
можно. Пусть теперь множество П Н (Ор, Ri) пересека-
г=1
5*	67
ется с Z, тогда, повторяя рассуждения второй части дока-
зательства теоремы 14 и используя выпуклость множества
7П
П Н {Oi, Рч) как пересечения выпуклых множеств (кру-
г=1
гов Аполлония), приходим к выводу, что в этом слу-
чае Е всегда может обеспечить выживание, двигаясь из
Е (0) прямолинейно в одну из точек границы I, принадле-
т
жащую границе множества П Н (Од 7?;), Теорема до-
j=i
казана.
Пусть Р\(0), Рг(0), . .Рт(0) и £(0)— начальные по-
ложения участников наряда Р\, Р2, . . ., Рт и Е. Проведем
перпендикуляр (Л,; В.) через середину А, отрезка
)ZJ,(0), £'(0)j. Обозначим £< полуплоскость с границей
т
(А,-. 5(), содержащую точку £(0). Пусть К = П £г,
i=i
Имеет место следующая
Теорема 16. Пусть pi = р2 — • • • = р™ = о и S —
полуплоскость с границей I. Тогда в игре G(m, 1; S) воз-
можно выживание в том и только в том случае, когда
множество К имеет непустое пересечение с границей I
множества S.
Ф. Л. Черноусько получил следующий результат.
Теорема 17. Пусть pi р2 С . ..	р,„ < о, S — вы-
пуклое множество, не лежащее на одной прямой, и
lA(0)£’(0) I > 0, г — 1, 2, ..., т; тогда в игре G(m, 1; S)
возможно выживание игрока Е из начальных положений
7*1(0), Р2 (0), .. ., Рт(0) участников наряда Р = l/'i, Р2, .. .
. .., Р„} и Е (0) игрока Е.
У п р а ж п е п и я
42.	Пусть р1 5г р2 > о > 0 и S — произвольное выпук-
лое множество па плоскости. Покажите, что в игре
G(2, 1; S) невозможно выживание тогда и только тогда,
когда пересечение кругов Аполлония ZZ(<9i; 7?1)П
П П (Ог; В?) относительно начальных положений 7*1(0),
£(0) и 7*2(0), £(0) не пересекается с границей I множе-
ства 5.
43.	Рассмотрим игру С(2, 1; S), pi > рг > о, при до-
полнительном предположении, что участники Р\ и Р2 на-
ряда Р в процессе движения могут пересекать границу I
множества S. Выведите необходимое и достаточное усло-
68
btie невыжпвания игрока Ё в S в случае, когда S — про-
извольное (не обязательно выпуклое) множество на пло-
скости.
44.	Докажите теорему 16 в случае т = 2, а теорему 17
в случае т = 3.
45.	Сформулируйте и решите упражнения 42, 43 для
игры G(m, 1; S).
46.	Пусть pi 7? р2 > о > 0. Постройте множество
У3р;(0)>р2(0) (5, uj в игре G(2, 1; 5) в случае, когда S —
полуплоскость.
ГЛАВА IV
ИГРЫ ПРЕСЛЕДОВАНИЯ,
ПОЛНОЕ РЕШЕНИЕ КОТОРЫХ НЕИЗВЕСТНО
§ 10. Преследование в угле*)
Предположим, что преследование происходит в угле
а с вершиной в точке О и наряд Р состоит из одного пре-
следователя Р. Обозначим игру преследования в угле сим-
волом Г(1, 1; а), а величину угла а в радианах симво-
лом а.
а)	Пусть а = л/2, в начале игры Е находится в верши-
не угла а, Р — на биссектрисе ир = Т2о (рис. 34). Не ог-
раничивая общности, предположим, что
а = {(.г, у): х ж 0, у < 0)
и Р(0) = (Ь, -Ь), Ъ > 0.
Теорема 18. Пусть а — л/2, р = У2о и в начале иг-
ры Р и Е находятся в положениях Е(0) = (0, 0) и Р(0) =
= (Ь, — b), b > 0. Тогда в игре Г(1, 1; а) оптимальное вре-
мя преследования 0 = i£(0)P(0) 1/р = Ь/а.
Доказательство. Пусть игрок Е на промежутке
времени [0, Ь/2о\ перемещается но полупрямой [Е(0), А),
где А = (б/2, 0), и, далее, па промежутке времени [Ь/2о,
6/о]—по полупрямой [4, Е(0)). Тогда очевидно, что Е
в момент времени 0 = Ыа окажется в точке О — (0, 0), и
легко можно убедиться, что при таком способе перемеще-
ния игрока Е на промежутке времени [0, 6/о) игрок Р
не может осуществить встречу с Е до момента времена
0 = 6/о.
*) В лшерагуре по теории преследования игру Г( J, 1; а) на-
зывают игрой «крыса, загнанная в угол».
70
Пусть теперь игрок Е перемещается в угле а по про-
извольной ломаной траектории. Предпишем игроку Р сле-
дующую стратегию; перемещаться по полупрямой
--------->
[£(0), £(0)), т. е. с постоянной вектор-скоростыо и =
= (—р, р), До момента времени £, когда впервые игрок £
попадает на один из отрезков \{P\{t~), £2 (О), (£i(t), 0)]
пли {(Pi(t),	(0, P2(t))], т. е.
Е(^[(Р^,), P2(t,)), (£>(0), 0)]U
U [(£i(^i), £2^)), (0, £2(М)].
и, начиная с момента времени t = ti, использовать
П-стратегию.
Возможны два случая: tj = Ь/о пли 0 < ti < Ь/а.
В первом случае встреча Р с Е осуществляется в момент
времени В = 0 в точке О — (0, 0).
Пусть 0 < ti < Ыо и £(ti)e [(£1 (Т),	£2(ti)),
(£i(ti), 0)], где £(ti)==(& — tip, b + tip). Тогда из началь-
ных положений £(ti) и £(ti) решение игры Г(1, 1; а)
сводится к решению игры преследования в полуплоскости
Г(1, 1; £), где L — {(х, у: у =£ 0) п полупрямая [£(М,
£(ti)] перпендикулярна к границе полуплоскости L. Вре-
мя встречи из начальных положений £(ti) 11 E(tt) будет
наибольшим, если E(t\) — (b —	0) (см. упражне-
ние 22).
Из теоремы 3 получаем, что в игре Г (1, 1; L) из на-
чальных положений £(ti) = (& — tip, — b + ttp) п £’(t2) =
= (6 —tio, 0) можно завершить преследование за время,
не превосходящее (6/а — £). Следовательно, в игре
71
Г(1, 1; а)' из начальных положений Р(О) = (Ь, — Ь) и
Е(0) = (0, 0) можно завершить преследование за время,
не превосходящее (й/о — <i)+ <i = b/a = 0. Теорема дока-
зана.
б)	Пусть а = л/2, игрок Р в начале пгры находится на
биссектрисе угла а, т. е. в точке P(O) = (b, — b), Ъ > 0, и
р — Т2а (рпс. 35). Введем обозначения
К1 = а П Н (5(0); &),
К3 = а\(^ и К2).
Теорема 19. Пусть р = 12а и игрок Р в начале иг-
ры находится в положении P(Q) — (b, — b), Ъ > 0. Тогда
1) если Е(0)^К2, то решение игры Г(1, 1; а) из на-
чальных положений Р(0) и
7г(0) сводится к решению игры
Г(1, 1);
2) если Е(0)^Кз, то реше-
ние игры Г(1, 1; а) из на-
чальных положений Р(0) и
£(0) сводится к решению игры
Г(1, 1; L);
3) если Е (0)s К\, то в игре
Г(1, 1; а) оптимальное время
преследования относительно на-
чальных положений Р(0) и
Е(0) 0 = 6/а.
Доказательства утвержде-
нии 1) и 2) могут быть полу-
чены проведением элементар-
ных вычислений, а доказательство утверждения 3) впол-
не аналогично доказательству теоремы 18.
в) Пусть а =л/2, р = ]'2а и в начале игры Р и Е на-
ходятся в положениях /3(0)==(«, —с), а > 0, с > 0, и
2?(0) = (0, 0) (рпс. 36). Через М обозначим такую точку
на биссектрисе угла а, что
|Р(0)ЛП = \МО\.
Справедлива следующая
Теорема 20. Пусть а = л/2, р = У2а и в начале
игры Р и Е находятся в положениях Р((У) — (а, —с), а > 0,
72
У
Рпс. 36
с > 0, и Е'(О) = (О, 0). Тогда в игре Г(1, 1; а) оптималь-
ное время преследования относительно начальных поло-
жений Р(О) и Е(0)
а 2 |-Р (0) Л/|
Р
Упражнения
47. Рассмотрим игру Г(1, 1; а), где а — л/2, р =/2<т
и в начале игры Р и Е находятся в положениях Р(0)==
= (b, —b), Ъ > 0, п Е(0) = (0, 0). Пусть игрок Е на проме-
жутке времени [0, Ь/2ст] перемещается по полупрямой
[£(0)	, где А = (Ь/2, 0), и, далее, на промежутке вре-
мени [&/2сг, £/а]— по полупрямой [Л, £(0)). Докажите,
что игрок Р не может осуществить встречу с Е до момента
времени 0 = Ь/а.
48. Найдите решение игры Г(1, 1; а) в следующих
случаях:
1)	а = л/2, р>Т2о и в начале игры Е находится в
вершине, а Р — на биссектрисе угла а, |Р(0)£(0) |> 0;
2)	0 < а < л/2, р cos(a/2)> а п в начале игры Р на-
ходится на биссектрисе угла а, Е(0)еа, |Р(0)Е(0)! > 0;
3)	0 < а < л/2, р cos (а/2) С о и в начале игры Е на-
ходится в вершине угла а, Р(0)^а, |Р(0)£(0)1 >0.
49. Найдите решение игры Г(1, 1; 5) в случае, когда
5 — квадрат с вершинами в точках (1, 1), (1, — 1),
(-1, -1), (-1, 1), Р(0) = (0, 0), £/)М и р - 12а.
50. Найдите решение игры Г(1, 1; 5), где S — равно-
сторонний треугольник, в следующих случаях:
1.	р == 2о/1'3, в начале игры Р находится в точке пе-
ресечения биссектрис треугольника S, Е(0)<^$,
,Р(0)£(0)! > 0;
2.	р>2, P(0)eS, £(0)е5, \P{0)E{Q) \ > 0.
51.	Докажите, что в игре Г(1, 1; а), 0 < а л, при ус-
ловии р о возможно убегание.
§ И. Случай, когда убегающий
«окружен» преследователями
В этом параграфе исследуем игру Г (иг, 1) в случае,
когда для начальных положений Pi(0), Рг(О), , . ., Рт(О)
и £(0) выполнено условие (см. (80)) £(0)<s К\К0, где
73
К — наименьший выпуклый многоугольник, содержащий
точки Pj (0), Р2(0), ..Рт(0), а Ко — граница многоуголь-
ника К.
1. Игра Г (3, 1), а) Рассмотрим случай pi = р2 — рз =
= 2а и в начале игры Рь Р2, Рз находятся в вершинах
равностороннего треугольника К со стороной а > О,
IP1 (0)Р2(0) != 1Р2(0)Р3(0)| = IPi(О)Рз(О) I -я (рис. 37).
Обозначим буквой О точку пересечения биссектрис тре-
угольника К.
Теорема 21. Пусть pi — р2 = рз = 2а. Тогда
(рис. 38)
1)	если £(0)^ К\ U ZG U Кз, то решение игры Г (3, 1)
сводится к решению игры Г(1, 1);
2)	если £(0)е К[2 U К?з U Kis, то решение игры Г(3, 1)
сводится к решению игры Г (2, 1);
3)	если Е(0)^ П(О; а/2УЗо), то в игре Г(3, 1) опти-
мальное время преследования из начальных положений
РДО), Р2(0), Рз(О) и £(0)
е =
2 УЗо
Доказательство. Ограничимся указанием опти-
мальных стратегий убегающего Е и наряда Р в случае
£(0)еЯ((9; а/(21'3о)).
Пусть точка М такова, что |£(0)Л/! + [Л£О| ~
— аЦЖЗв). Оптимальная стратегия игрока Е: переме-
щаться по полупрямой [£(0), М) до момента времени
74
1Е(0)Л/1/а и перемещаться по полупрямой [Л/, О) на от-
резке времени [!£(0),lf l/o, а/(21'3о) I.
Оптимальная стратегия наряда Р: перемещаться участ-
никам наряда Pi, Рг, Рз, начиная с момента времени t = О,
по полупрямым [Л (0)£(0)), [Р2(0)£’(0)), [Р3(0)Е (0))
соответственно до момента времени t = t\, когда впервые
игрок Е попадает на границу Ко(М треугольника K(t\) =
= ^Pi(ti)P2(ti)P3{ti), т. е.
E(^1)e[P1(f1)P2(O)]U[P2(i1)P3(i1)]U[P1(^)P3(«1)],
а начиная с момента времени t\ применять П-стратегиго.
Доказательство лишь незначительно отличается от до-
казательства теорем 5, 18—20.
б) Рассмотрим случай pi > р2 р3 о и в начале пг-
ры Р\, Рг, Рз находятся в вершинах треугольника К,
др1(0)Р2(0)Рз(0).
Определим точку М ={х, у) следующими соотношениями:
м\ _ = ,91)
Р1	Р.З
Лемма 16. Пусть pi р2 > р3 > 0 и точки РДО),
Р2(0), Л3(0) не лежат на одной прямой. Тогда система
уравнений (91) относительно М имеет не более двух ре-
шений или вовсе не имеет решений.
Доказательство. Перепишем систему (91)
в виде
I = ИЙ(О)Л/) -
р,	р2 ’
а)	Пусть Pl > р2 > рз > 0. Множество точек М =
= (х, у), удовлетворяющих уравнению (92), представляет
собой окружность S(Ot; Rt) (ср. (о)), а множество то-
чек, удовлетворяющих уравнению (93), представляет со-
бой окружность 5(О2; Т?2), причем О\ =Д О2. Следователь-
но, множество S(Op Ht)6S(O2; Пг) состоит не более чем
из двух точек.
б)	Пусть pi = р2 > Рз > 0. Тыла множество точек 1\1 =
= (ж, у), удовлетворяющих уравнению (92), представляет
собой прямую, проходящую через середину отрезка
[/^(О), Рг(О) ], а множество точек М, удовлетворяющих
уравнению (93), представляет собой окружность 5(Оз', /?з)-
Очевидно, что прямая пересекает окружность не более
чем в двух точках.
в)	Пусть pi = р2 = рз. В этом случае точка М един-
ственная и совпадает с центром описанной окружности
к треугольнику К.
Лемма доказана.
Множество решений системы (91) обладает следую-
щими свойствами.
Лемма 17. Пусть pi С” р2 рз > 0 и точки T’i(O) ,
Z*2(0), 79з(0) не лежат на одной прямой. Тогда
а)	в треугольнике К содержится не более одной точ-
ки, удовлетворяющей системе (91);
б)	если две точки М\ и удовлетворяют системе (91)
и Н{Мр, 1/’1(0)Л/1|/р!)с К, т0 круг	!/’> (0) ЛОрО
не пересекается с внутренностью 1реуголъника К, т. е.
с множеством K\Kq, где Ко — граница треугольника К.
Справедливы следующие теоремы.
Теорема 22. Пусть р, р2 Т? Рз о и для началь-
ных положений Z’i(O), ZJ2(0), Р3(0) система (91) не име-
ет решения. Тогда решение игры Г (3, 1) из положений
Р,(0), Р2(0), Л3(0) и при любом начальном положении
Е(0) сводится к решению игры Г (2, 1).
Теорема 23. Пусть pi Л р2 Л р3 Э= а, система (91)
имеет единственное решение и
{рис. 39). Тогда
а)	если Е (())<= П {М р UJi (O)J/il/pi), то в игре Г (3, 1)
оптимальное время преследования относительно начало-
ных положений Pi(0), Рг(0), Рз(О) и Е(0) равно 0 =
= |Р1(0)Л/11/Р1;
б)	если Е (0)^11 (Му \Pt (0) Л/] |/Pi), то решение игры
Г (3, 1) из начальных положений РДО), Р2(0), Рз(0)
и £’(0) сводится к решению игры Г(2, 1).
Теорема 24. Пусть Pi > рз > рз 5s о система (91)’
имеет два решения Му М2 и
/ I (0) М, I \
Я Му, 1 11.1—111 с~ к
f’l )
а круг Н(М<р, |Р[ (0)Л/21/Р2) не пересекается с K\Kq
(рис. 40). Тогда
а) если E(0)^H(Mi; |Р| (0)9/1 |/р!), то в игре Г(3, 1)
оптимальное время преследования относительно началь-
ных положений РДО), Рг(0), Рз(0) и £(0)
е =
Pi
б)	если Е(0)^ H(Mi, Р\ (0)9/i7Pi), то решение игры
Г(3, 1) из начальных положений /•'i(O), Рг(0), Рз(О) и
Е(0) сводится к решению
игры Г(2, 1).
Теорема 25. Пусть
Pi Р2 дм р3 Ж а система
(91) имеет два решения
М । и М2 и
£(0)^
щ //: и.:
Р3(0)
Е(0
(0)
U Н Мр,
(рис. 41). Тогда решение
игры 1(3, 1) сводится
Доказательство леммы 17 и теорем 22—25 предо-
ставляется читателю.
2.	Игра Г(;п, 1). Следующая теорема доказана
Б. II. Пшеничным.
Теорема 26. Пусть Р1 == р2 = ... = р™ = о и Е(0)е
с= К К (ср, (80)). Тогда в игре Г(т, 1) из начальных
местоположений 1,(0). /Б(0), . ...	и £’(0) воз-
можно завершение преследования га конечное время.
77
Упражнения
52.	Докажите лемму 17.
53.	Пусть р, > 0, It О, i = 1, 2, 3, и точки А], А2,
As не лежат на одной прямой. Докажите, что система
уравнений
|	_ | Л2М| - 12	|	- 13
Pi “ Р2	Рз
относительно М имеет не более двух решений пли не
имеет решений вовсе.
54.	Докажите теоремы 21—25.
55.	Докажите теорему 26 в случае т = 3, К =
= APi (0)Рг(0)Рз(0) — равносторонний треугольник со
стороной а и Е(0)—точка пересечения биссектрис тре-
угольника К.
56.	Рассмотрим игру Г(3, 1) в случае pi = р2 = рз = о
и Е(0)е К\Ко (см. теорему 26). Пусть наряд Р = {/Д
Р2, Рз) использует П-стратегию. Укажите для игрока Е
наибольшее гарантированное время убегания.
57.	Рассмотрим игру Г (2, 1; L), где L — полупло-
скость с границей I и pi = р2 = о. Из точек РДО) и Р2(0)
опустим перпендикуляры к границе I и точки пересече-
ния обозначим соответственно D> и В2. Обозначим бук-
вой К трапецию с вершинами в точках Р\ (0), Р2(0). _О2,
Пусть £(0)еД( {D,PX (0)] U [Л(0)Р2(0) ] U [Р2(0)Ь2])
и наряд Р = {P|, Р2} использует П-стратегию. Тогда
а)	докажите, что в игре Г(2, 1; L) из начальных по-
ложений Рх (0), Р2(0) н 2?(0) возможно завершение пре-
следования;
б)	укажите для игрока Е наибольшее гарантирован-
ное время преследования.
58. Рассмотрим игру Г (2, 1; L), когда L — полупло-
скость с границей Z. р, = р2 = о и 7?(0)е К\( [D|, Р(0)] U
и[РДО), Р2(0) ] 6 j/’2(0), D2]). Проведем серединные
перпендикуляры l\ и ?2 к отрезкам [Л(0), Е (0) ] и
[Р2(0). Е (0) J соответственно, обозначим
С1 = П I, c2 = l2}\ I, С3 = ?! П ?2.
Пусть IСЛС1! 5s 1 CiCi I. Т or да
а) докажите, что в игре Г(2, 1; L) п.з начальных по-
ложений ИДО), Р2(0) п Е(0) возможно завершение пре-
78
следования за время
IW3I+ISSL.
ст	’
б)’ если	Сз)', то в игре Г(2, 1; 7.) опти-
мальное время преследования относительно начальных
положений Р\ (0), Рг(0)' и Я(0) равно I/*2(0)CjI/о.
§ 12. Лев и человек *)
Рассмотрим игру Г(1, 1; 5), где S = H = H(O-, R]
— круг с центром в точке О и радиусом R > 0.
Игроки Р (лев) и Е (человек) в начале игры нахо-
дятся в положениях Р(0) и Е(0) в множестве /7((9; R\
(круговой арене), !Р(0)
£'(0)1>0, а в процессе пг-
ры не могут покинуть
Я(О; R).
Теорема 2"**). Пусть
р = о. Тогда в игре Г(1, 1;
Я) из любых начальных
положений Р(0) и Я(0),
|/’(0)£’(0) I > О, возможно
убегание.
Доказательство.
Предположим, чго Я(0) —
внутренняя точка круга Я
(рис. 42), и укажем некото-
рый способ движения игро-
ка Е. Проведем прямую 7о = (Я(О), О)-, если Я(0) = 0, то
Iq — любая прямая, проходящая через точку Я(0).
Прямая 1о делит круг Я на две равные части L'f
и Lq. Пусть для определенности Р (0) е L^. Через точ-
ку Я(0) проведем прямую 1'0=(А$, Л^), перпенди-
кулярную прямой l0, А~ е L^, А$ , Ao ,
А^ e S (0, R). Обозначим
а = |Я(О)Ло+|, & = |0, Я(0)|.	(94)
Пусть игрок Е в момент времени Z = i = 0, 1, . .., где
10 = 0, находится в Е (tt). Проведем прямую Z, = (£(£,), О),
которая делит круг Я на две равные части Li и Lt, и
Рис. 42
*) Задача «Лев и человек» и ее название предложены
Р. Радо,
**) Теорема доказана А. С. Безиковичем,
79
пусть для определенности	Через точку Е (ti)
проведем прямую l\ = (А~, Af), перпендикулярную пря-
мой Zj, Ai щ Lj , At s Lt, Aj , А( 5 (O', H).
Предпишем игроку E движение па промежутках вре-
----------------------------------------->
мени [С, Zj + J), I — 0.1, . по полупрямым [E(ti),At) , где
а / 1
о ( 2
1_
3
(95)
Покажем, что игрок Р не могйет осуществить встречу с
Е на любом конечном промежутке времени [0, 9]. Так
как р — а и Р (ti) Е~, очевидно, что Р не может осу-
ществить встречу с Е на любом промежутке времени
Докажем теперь, что при i °° последовательность
моментов времени t, Действительно, если i — 2\ то
из (95) имеем
ti
1
1 \. а / 1	1	1	1	1	1	1
^>ЪЦТ + ’4+Т + ^+8'' У+¥+ •••
я 1	1 ак /<лр\
= (96)
2/l
Из (96) следует, что t, = t2h 00 при к -> <». Следо-
вательно, для любого момента времени 0 существует ин-
декс г'о такой, что	Так как на отрезке времени
[О, ti ] возможно убегание, то тем более это возможно
на отрезке времени [0, 9]. Теперь покажем, что при
таком движении игрок Е не покидает круг Н до момента
времени 9. Легко убедиться, что для любого г‘е{1. 2,...}
2	о	2
\0E(ti)^ + ^ + ^+
О	V Т"
т. е. E(t,)^II, i=l, 2, ... (Здесь мы воспользовались
80
1 I
^-<1.1 Из выпуклости круга Я сле-
неравенством
k=2
дует, что Е(t) е Н для всех t е= [0, 6].
Теорема доказана.
Следующая теорема доказана В. И. Левиным.
Теорема 28. Пусть р = о. В игре Г (1, 1; Н) у иг-
рока Р существует способ преследования, гарантирующий
сближение с Е на любое наперед заданное расстояние
е>0 из любых начальных положений Р(0)<=Я и
Я(0)е Н.
Упражнения
59.	Рассмотрим игру Г (1, 1; 5), где S — выпуклое мно-
жество, не лежащее на прямой, и р — о. Тогда в игре из
любых начальных положений 7J(0) и 7Г(0), |Р(0)7?(0) I >
> 0, возможно убегание. Докажите это утверждение.
60.	Докажите теорему 28.
61.	Пусть 0 < р < о. Докажите, что в игре Г (1, 1; Я)’
у игрока Р существует способ преследования, гарантирую-
щий сближение с Е на расстояние <7 = <7(р, о) из любых
начальных положений P(0)s Я и 7?(0)<= Я.
62.	Рассмотрим игру Г (2, 1; S), pi — р2 — о.
а)	Докажите, что если S — квадрат со стороной а,
то в игре Г (2, 1; S) из любых начальных положений
Р(0) и 7?(0) возможно завершение преследования за
время 0 = а/а (3/2 + Т 2/2).
б)	Докажите, если S — круг радиусом а/2, то в игре
Г(2, 1; 5) из любых начальных положений Р(0) и 7?(0)
возможно завершение преследования за время 0 —а/о(1 +
.+ V2/2).
63.	Рассмотрим игру Г(2, 1; Я), где Н(О; Я)—круг,
pi = p2=V2o и в начале игры Pi и Ра находятся в
P](0)s S(О; R) и РбОщДО;// соответственно, 1РД0),
Рг(0)1 = 2R. Найдите решение игры Г (2, 1; Я) при лю-
бых начальных положениях £(0)еЯ.
6 Л А Петросян, В, Б Рихсиев
ЗАДАЧИ ДЛЯ ИССЛЕДОВАНИЯ
1.	Перенести все результаты книги «Преследование на
плоскости» на случай, когда преследование происходит
в трехмерном пространстве.
2.	Рассмотрим обобщение Г((т, 1; S) игры Г(т, 1; S).
В игре Г/(/п, 1; S) под встречей наряда Р — {Pi, ..., Рт}
с игроком Е мы будем понимать сближение хотя бы од-
ного из участников наряда Р, с игроком Е на расстояние
/(>0. В остальном игра Г/(т, 1; S) совпадает с игрой
Г(т, 1; S) (если все I,, i = 1, .. т, равны 0, то мы по-
лучаем игру Г(т, 1; 5)).Наптп решение игры Г((т, 1; S).
3.	Рассмотрим обобщение Gi(m, 1; 5) пгры G(m, 1; S).
В игре Gi(m, 1; S) под встречей наряда Р с игроком Е
мы будем понимать сближение хотя бы одною из участ-
ников наряда Pt с игроком Е на расстояние h. В осталь-
ном игра Gt{m, 1; S) совпадает с игрой G(m, 1; S'). Най-
ти решение игры Gt(m, 1; 5).
4.	Рассмотрим игру Г(1, 1; а), где 0<a=Sn/2, р >
> а > 0, и местоположение игрока Е в начале шры сов-
падает с вершиной угла a, Р(0)<=а, iP(0)£(0) I >0. Най-
ти решение игры Г(1, 1; а).
5.	Найти решение игры Г(1, 1; а) в общем случае.
6.	Найти решение игры Г(3, 1) в случаях pi > рг >
> рз > о; pi > рг > рз ~ о; pi > рг — рз = о.
7.	Найти решение игры Г (3, 1) прп условии pi — рг =
= рз — о и Е(0) находится внутри треугольника
7>1(0)?2(0)Рз(0). Интересен также частный случай, ког-
да ДР1 (0)Рг(0)Рз(0) равносторонний и точка £(0) сов-
падает с точкой пересечения его биссектрис.
8.	Найти решение игры Г (2, 1; L) в случае, когда pi
> рг > о и L — полуплоскость.
9.	Исследовать задачу 8 при условии pi —рг = п.
10.	Исследовать задачи 5, 8 в случае, когда множест-
во S является квадратом.
И.	Найти решение игры Г(1, 1; 5)', где S — круг и
р > а.
12.	Найти решение игры Г(2, 1, S)' в случаях р] >
> рг > о; pi = рг = о, когда S — круг.
РЕШЕНИЯ, УКАЗАНИЯ, ОТВЕТЫ
1.	а) Из формулы (1) следует, что P(t) = (21, 0) и Е(1) —
— (1 + 1, 0); б) встреча Р с Е происходит в точке .V = (2, 0) в
момент времени t = 1.
2.	а) Если Е перемещается с вектор-скоростыо v = (1, 0), то
игрог: Р не может осуществить встречу с Е до момента времени
0 = 1, так как при 0 С t < 1 для положений Р} (!) = (Р, (г), 0)
и E(t) — (E2(t), 0) — (1 + 1, 0) (см. упражнение 1) имеем Pt(t)
С 2г < 1 + t = Е] (1). С другой стороны, если игрок Р перемеща-
ется с вектор-скоростыо и = (2, 0), то встреча Р с Е происходит
не позже, чем за время 0 = 1, так как в момент времени 0 = I
для положений P(t) = (21, 0) и Е(г) = (Z?s (г), 0) имеем Е) (1) гД
=+2 = P,(1).
б) Если а > Ь, то оптимальное время преследования равно
а — b и — (2, 0) и v = (1, 0) —оптимальные стратегии игроков
Р и Е соответственно.
Если а < Ь, то оптимальное время преследования равно b— а:
и= (—2, 0) и v = (—1, 0)—оптимальные стратегии игроков Р
ц Е соответственно.
3.	а) Для начального положения Е(0) = (а, 0) игрока Е воз-
можно выживание, если не [—2, 1] |J fl, 2], в противном случае
выживание невозможно.
б)	Пусть а > Ь, тогда из начального положения Е(0) — (а, 0)
возможно выживание, если «е [—2, (Ь — 2)/2] IJ [(2 —Ь)/2, 2],
в противном случае выживание невозможно.
4.	К моменту времени г > 0 игрок Р из начального положения
Р(0) может оказаться в любой точке круга //(/ДО); pt) (лемма 1),
по поскольку в процессе движения игрок Р не может покинуть
множество S, то множество всех точек, в которых может оказать-
ся игрок Р в момент времени г, имеет вид S pH(P(0); pt).
5.	Точки Р(0), Р(Р) и М лежат на одном радиусе [Р(0), -VI
и |Р(О)-Р(ti) I = рИ, 'E(li)Jf| = p(l—1,), следовательно, окруж-
ности 5(Д(0); pl) и S(P(Z2); р(г —гД) касаются в точке М
(см. лемму 6).
6.	См. доказательство леммы 3.
7.	Геометрическое место таких точек А образует эллипс с фо-
кусами в точках Р(0) и z.
8.	Геометрическое место точек Аполлония образует отрезок
[4(Z’(0), Е (9)), +]. Доказательство вполне аналогично доказа-
тельству ле 11 ни 4.
9.	При 1 = 0 пип /= |Е(0)-1/|/о псравеис 1во очевидно. Рас-
смотрим случай 0 < 1 < [E(0).V|/(j.
6*
Из подобия треугольников £(0)Р(0)Л7 и E(t)P(t)M (см. рис. 7'
имеем
| Е Ш Р «) | __ | Е (Z) М | _ | Е (0) М | - | Е (0) Е (I) |
| А (0) A (0)J ~ |А(0).1/1	\Е(0)М\
отсюда, учитывая, что Р(0}Е(0) — b, |£(О)Е(Д| = о/, получаем
<jbt
1 t- (0 р (0 I = & — |£ (0) М
Отсюда п пз формулы (12) имеем
\E(t) Л (0 I =
о| РД) Е(1\\
р — а
abt
| Е (0) М |
о
р — а
b —
Следовательно, данное неравенство можно переписать в виде
о /, vbt \ °Ъ
ot + р— а | Е (0) М |J	р —а"
Отсюда, учитывая, что t > 0, получаем эквивалентное неравенство
o‘?)i
al С------------------,
(р - о) | Е (0) М |
т. е.
ab
| А (ОДП | <7^ ==!'£'(0) Л|.
Последнее неравенство всегда справедливо, поскольку А — точка
Аполлония.
10.	Предоставляется читателю.
11.	Предоставляется читателю.
12.	Предположим. что Е(0) = (0, а), Р(0) = (0, 0) и игрок
перемещается с вектор скоростью v= (г|.о2). II-стратегия предпи-
сывает игроку Р движение с вектор-скоростью и --	J/^р‘ — и2)
Пз неравенства |/”р2 — г’х V^P2 — о2 > 0 следует, что N — точ-
ка с положительной ординатой. Отсюда получаем решение задачи.
13.	Предоставляется читателю.
14.	Предоставляется читателю.
15.	Убегающему достаточно перемещаться по полупрямой
	>
ГР(О), Е(0)). Тогда |Р(/)А(/)|	!Р(0)Е'(0)| для всех 1^0.
| Е /0) Е (>) |
16.	а) Для всех I	—р ду 0---- имеет место включение пз
утверждения в) леммы 6.
17.	Укажем способ преследования тпрона Е. Пусть в момент
времени I = i игрок Е решил изменить направление своего дви-
жения и начал перемещаться по полупрямоп_|Е_(0), .17), где М —
некоторая точка на окружности Аполлония S(O\ Л), соответствую-
щая полож’епиям Р(/) и /.’(/). Если .1/ е: S, то предпишем игроку Р.
начиная с момента времени / = I, движение по полупрямой
Д’(0), М), т. е. сотласно II стратегии, если Л/ ф. S, то предпишем
84
игроку, начиная с момента времени t = г, движение по полупря-
мой [Р(0), Л/), где М = S П [£(0), М). Для доказательства утверж-
дения удобно ввести псевдопреследователя Р$, действующего со-
гласно П-сгратогии.
18.	В обоих случаях точка Аполлония, соответствующая на-
чальным положениям Р(0) и £(0), содержится в полуплоскости L.
19.	Предоставляется чтателю.
20.	В данном случае точка встречи М является внутренней
точкой полуплоскости L и множество, ограниченное параболой S’o
и отрезком f—Л/*, Л/*], выпукло.
21.	Предоставляется читателю.
22.	Предположим, что /’(0) = (0, — 6) и Е = (0, — а). Из тео-
ремы 3 следует, что 0 = ((62 — «2)/( р2 — о2). Если величину 0 рас-
сматривать как функцию переменной а, т. е. 0 = 0(я), то оче-
видно, что функция 0 = 0(a) достигает своего наибольшего значе-
ния, когда а = 0, т. е. в случае Е(0) е= I.
23.	Предоставляется читателю.
24.	Предоставляется читателю.
25.	а) Рассмотрим случай р, > р2 > а = 1. Предположим, что
Р|(0) = (0, 0) и Р2(0) = («, 0), а > 0. Решение игры-Г(2. 1) из
начальных положений Pi(0), Р2(0) и Е(0) сводится к решению
игры Г(1, 1) тогда и только тогда, когда
£(0) е= 11(0,; /?,) U S(O2; ll2) (J (S\H(O2; П2)),
где S — вен плоскость, О =

'2 - !>1
_ (р1 ~ Р?а
1 o'l - Р1
0
Р*-Р^
р, (Pl-1)0
f>2 - Pl
Докажите это утверждение. Найдите аналогичные условия и в слу-
чаях а) р, = рз > о; б) pi > р2 — о.
26.	Следует из решения упражнения 25 и теорем 5—6.
27.	Предоставляется читателю.
28.	Предоставляется читателю.
29.	Предоставляется читателю.
30.	Предоставляется читателю.
31.	См. указание к упражнению 23.
32.	Утверждение следует из свойств П-стратетни, которая пред-
писывает игроку Р движение по отрезку	H(/s+i)] в случае,
когда игрок Е двигается по отрезку [£(/*).	].
33.	Согласно теореме 2 множество точек встречи при исполь-
зовании Н-страгегни игроком Р в игре <7(1. 1; S) совпадает с кру-
гом Аполлония !1(О,: Н,)_ Поэтому если 11(0,; Г),) не пересекается
с границей I множества S, игрок Е пе может достичь I до его
встречи с игроком Р. Принадлежность траектории игрока Р множе-
ству S обеспечивается выпуклостью S.
34.	Если не требовать условия принадлежности траектории
игрока Р множеству S, то условие выпуклости 5 пе нужно для до-
казательства оптп.ма.'ияюсти I[-стратет ин в ш ре <7(1, 1; S). Поэто-
му решение совпадает с решением предыдущего упражнения,
35.	Поскольку множество S oi раннчено, то полупрямая
[/’(О), Е(0)) обязательно пересекает границу I этого множества.
85
Стратегия Е, обеспечивающая выживание, заключается в движе-
нии игрока Е по полупрямой [/’(О), Е(0)).
36.	Обозначим буквой .]-! точку окружности Аполлония
S(Oi; Ei) относительно начальных положений Р(0), Е(0), наиболее
близкую к границе I множества S. Оптимальная стратегия игрока Е
заключается в движении по полупрямой [£(0), J7], а оптимальная
стратегия игрока Р — П-стратегия.
37.	Предоставляется читателю.
38.	Предоставляется читателю.
39.	Пусть S — квадрат. Представьте квадрат как пересечение
полуплоскостей L}, L2,	L<. Постройте УЗр(о)(А1; a), i = 1, 2,
3, 4. Множество У3р(о)(5; <в) совпадает с пересечением квадрата S
4
с объединением множеств U УЗр(0) (7^; к>). Аналогично пред-
ставьте УЗр(0)(5; со) для многоугольника, Случай круга может быть
получен предельным переходом. Построение УЗ£(0)(5; со) предо-
ставляется читателю.
40.	Пусть {£(0), Е,(0)}еУЗ(5; со). Если в игре G(l, 1; .9)
относительно начальных положений Р(0), Е(0) возможно выжива-
ние. то это означает, что круг Аполлония S(Ot; /?,) пересекается
в некоторой точке М с границей I множества S. Рассмотрим дви-
жение Е по полупрямой [7?(0), Л/). Пусть P(t) —произвольное дви-
жение Р. Предположен!, что в некоторый момент t >0 пара {Р(1),
Е(1)} не принадлежит У3(5; со). Тогда это означает, что круг Апол-
лония относительно начальных положений Р(7) и E(t) не будет пе-
ресекаться с I, т. е. из начальных состояний P(l), E(t) возможна
встреча с Е при движении Е по полупрямой f£(O)jtf) до достиже-
ния игроком Е точе.п М. Однако это противоречит лемме 5 (так
как Е находится на окружности Аполлония 5((9j; Рч)). Получен-
ное противоречие доказывает утверждение.
41.	Доказательство аналогично упражнению 40.
42.	Доказательство аналогично упражнению 33,
43.	Доказательство аналогично упражнению 34.
44.	Предоставляется читателю.
45.	Предоставляется читателю.
46.	Предоставляется читателю.
47.	Воспользуйтесь леммой 5.
48.	См. доказательство теорем 18—20.
49.	Если Е((У)е S П [tf((l, 1): 1) U Я((1,-1); 1) U Н((-1, -1);
1) U#((—1, О: Ш, 10 в игре Г(1, 1; S) оптимальное время пре-
следования равно 1. В остальном решение игры Г(1, 1; 5) либо
сводится к решению игры Г( 1, 1; Е), где L — полуплоскость, либо
к решению игры Г(1, 1).
50.	См. теоремы 18, 19 и указание к упражнению 49.
51.	Следует из теоремы 26.
52.	Предоставляется читателю.
53.	Предоставляете!! читателю.
54.	Предоставляется читателю.
55.	Используя П-стратегию, получаем, что наряд Р = {Р,,
Р2, Рз} гарантирует встречу за время 6 —- о/о (см. упражнение 56).
56.	В этом случае .множество К (см. теорему 26) является тре-
угольником. Пусть точки /В, Л2. Л~, — его вершины и |А1А2| Дг
Дг |Л2.-1,,| > |/11--'13|. Перез точку С(О) проведем прямую, параллель-
86
пую отрезку [Л1Л2]. и пусть Bi и В}— точки пересечения этой
прямой с отрезками [>Мз] и [Л2Л3] соответственно. Гарантийное
время убегания игрока Е при использовании нарядом Р П страте-
гии равно 0 — (jB|B2| + 1В242|)/о.
57.	Воспользуйтесь указанием к упражнению 55.
58.	Предоставляется читателю.
59.	Следует из теоремы 26.
60.	Предоставляется читателю.
61.	Предоставляется читателю.
62.	а) Укажем стратегию наряда Р = {Рь Р?}. Сначала наряд
Р — {Pi, Р2} за минимальное время переходит в центр квадрата,
а далее использует П-стратегию.
б) Такую же стратегию применяет наряд Р и в этом случае.
63.	Предположим, что Pi(0) = (—В, 0) и Р2(0) = (В, 0), Если
£(0) ев [Н((0, В); В) (J //((0, -В); В)] П Я(0; В), то оптимальное
время преследования относительно положений Pi(0), Р2(0) и В(0)
равно О = В/о; в остальном решение игры Г(2, 1; Н) сводится
либо к решению игры Г(1, 1; а), где а —угол, либо к решению
игр Г(2, 1) и Г(1, 1).
НЕКОТОРЫЕ СИМВОЛЫ Н ОБОЗНАЧЕНИЯ,
ИСПОЛЬЗУЕМЫЕ В КНИГЕ
[А, В) -
Будем считать, что на плоскости введена ортогональная систе-
ма координат XOY. Тогда /1 — (Ai, А?) будет означать точку на
плоскости с абсциссой А, и ординатой А2;
А — вектор с началом в точке О — (0, 0) и с концом в точ-
ке А;
АВ — вектор с началом в точке А и концом в точке В;
[А, В] — отрезок с концами в точках А и В;
(А, В) — прямая, проходящая через точки А и В;
[А, В) — полупрямая (луч) с началом в точке А, проходящая
через точку В;
полупрямая с направлением АВ, по которой возмож-
но движение только в направлении АВ;
|АВ|—расстояние между точками
, 4 = (-И, Bi) и В = (ж2, у2), т, е,
Г/ '' |АВ| = 1 (ад — г2)2 + (г/i — У^',
|АВ| — длина вектора АВ, т. е.
Jr	|ЛВ|;
ДАВС — треугольник с вершинами
в точках А, В, С;
рпс 4з	И(A; R) — круг с центром в точке
А и радиусом R-
5(А; В) — окружность с центром в точке А и радиусом R;
X Г) У, X (J У и Х\У — пересечение, объединение и разность
множеств Хи У; А <= X означает, что точка А принадлежит мно-
жеству’ X, У с: X — множество X содержит множество У; conv X—'
наименьшее выпуклое множество, содержащее множество X; мно-
жество Х\У состоит из точек множества X, не принадлежащих
множеству У, 0 — пустое множество;
II — знак параллельности; _1_ — знак перпендикулярности;
fj— знак сонаправленностп векторов,
Символом E(t), ti < t < /2. обозначим траекторию (закон дви-
жения) игрока Е на отрезке времени [Ц, f2].
Полярные координаты. Пусть М — (г. у) —некоторая точка на
плоскости. Проведем полупрямую [0, М) и пусть | ОМ| = г и ср =
— Л.М0х (рис. 43). Легко заметить, что таким способом любой
точке (х, у) на плоскости сопоставляется единственная пара (г, ср),
которая называется полярными координатами точки М = (х, у).
Наоборот, каждой точке (г, ср) в полярных координатах соответст-
вует единственная точка (х, у) на плоскости, х = г cos ср, у =
= г sin ср.
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Аполлония круг 16
— окружность 16
— точка 16
Время преследования гаранти-
рованное 11
— — оптимальное И
Выживание возможно 13
— не возможно 12
Выпуклое множество 7
Игра	преследования Г(т,	1; S)
И		
— с	линией жизни	:	5)
12		
Зона	встречи 59	
Зона	yoei ания 59	
Линейная скорость точки 7
Множество достижимости 14
Оптимальная стратегия И, 12
Простое движение 6
— — по ломаным 7
П-стратегия 24
Теорема А. С. Безиковича 79
—- В. И. Левина 81
— Б. Н. Пшеничного 77
— Ф. Л. Черноусько 68
Траектория движения 6
ОГЛАВЛЕНИЕ
Введение .................. ........	3
Г л а в а I
ГЕОМЕТРИЯ ПРОСТОГО ДВИЖЕНИЯ
§	1.	Простое движение. Постановка задачи	преследования	6
Упражнения 1—3.....................................................................13
§	2.	Множество достпяшмости, окружность	и	точка	Апол-
лония ...........................................	14
Упражнения 4—9 ......................................................................21
§	3.	Стратегия параллельного сближения..............23
Упражнения 10—14...................................................................27
Глава II
ИГРА ПРЕСЛЕДОВАНИЯ НА ПЛОСКОСТИ
§ 4.	Преследование на плоскости с одним преследователем 29
Упражнения 15—17............................  ,	33
§ 5.	Преследование в полуплоскости с одним преследовате-
лем .................................................34
Упражнения 18—24	.	.	. '........................................................46
§ 6.	Преследование на плоскости с несколькими преследо-
вателями ............................................47
Упражнения 25—30	   52
Глава III
ИГРА С «ЛИНИЕЙ ЖИЗНИ»
§ 7.	Преследование с одним преследователем ....	54
Упражнения 31—36.....................................................................58
§ 8.	Построение зон убегания п зон встречи ....	59
Упражнения 37—41.....................................................................64
§ 9.	Преследование с несколькими преследователями . .	65
Упражнения 42—46	.	    68
90
Глава IV
ИГРЫ ПРЕСЛЕДОВАНИЯ, ПОЛНОЕ РЕШЕНИЕ КОТОРЫХ
НЕИЗВЕСТНО
§ 10.	Преследование в угле............................70
Упражнения 47—51.................................73
§11.	Случай, когда убегающий «окружен» преследователями 73
Упражнения 52—58	  77
§ 12.	Лев и человек...................................79
Упражнения 59—63	   81
Задачи для исследования...............................82
Решения, указания, ответы.............................83
Некоторые символы и обозначения, используемые в книге 88
Предметный указатель..................................89
Научно-популярное издание
ПЕТРОСЯН Леон Аганесович
РПХСИЕВ Бавир БерОибаевич
ПРЕСЛЕДОВАНИЕ НА ПЛОСКОСТИ
Серия «Популярные лекции по математике»,
выпуск 61
Заведующий редакцией А. П. Баева
Редактор В. В. Донченко
Художественный редактор Г. М. Коровина
Технический редактор Е. Б. Морозова
Корректоры Т. Г. Егорова, Л. С. Сомова
ИВ № 32769
Сдано в набор 08 09 90. Подписано к печати
27,05.91. Формат 84X108/32. Бумага тип. X» 2.
Гарнитура обыкновенная новая. Печать высо-
кая. Усл. печ. л. 5,04. Усл. ьр.-отт. 5,25. Уч,-
изд. л. 5,35. Тираж 53 000 эвз. Заказ As 425.
Цена 80 коп.
Издательско-ириизводсгвсниое и книготорговое
объединение «Наука»,
Главная редакция
физико-математической литературы
1 17071 Москва В-71, Ленинский проспект, 15
Четвертая типография издательства «Наука»
630077 г. Новосибирск 77, Станиславского, 25
PURSUIT ON THE PLANE
L. A. P e tr os j an, В. B. Rikhsiev
The theory of differential games is a new developing branch of
modern mathematics. Starting from the problems of pursuit and eva-
sion it covers today various mathematical models of decision making
when different conflicting sides are presented. The book is devoted
to the most elementary classes of differential games-simple motion
pursuit games on the plane with complete information. In spite
of the elementary and attractive formulations many of the problems
discussed in the book could serve as a basis of further scientific
research.
Chapter 1.	Geometry of simple motino.
The motions of the players pursuier (P) and evader (E) are de-
fined as movements with constant speeds along arbitrary broken li-
nes with the finite number of vertexes. The simple motion pursuit
game, the optimal capture time, optimal pursuit and evasion strate-
gies are defined. The reachable sets of the players, the capture cir-
cle and the parallel pursuit strategy (П-strategy) are introduced.
Chapter 2.	Pursuit game on the plane.
The optimal strategies in the pursuit games on the plane and
halfplane with one pursuier and one evader are found In the same
way the case of two pursuiers is considered. It is proved that in all
cases the П-strategy of P is optimal one.
Chapter 3.	«.Lifelines games.
The cases of one and m pursuiers are considered. The aim of the
evader in this class of games is to reach the boundary (lifeline) of
some given set S before being captured. It is proved that when P
uses П-strategy the capture set coincides with the Apollonius circle
in the case of one pursuier and with the intersection of m such
circles in the case of m pursuiers. The optimality of П-strategy is
proved and the complete solution founded.
93
Chapter 4.	Pursuit games with the solutions yet unknown.
To this class of games belong the so called “dead-line” games.
That means the pursuit-evasion games in which the both players
move in tire given set S having no possibility to penetrate its boun-
dary (dead-line), or the evader surrounded by the pursuiers with the
aim to minimize the time of capture. In some special cases the op-
timal strategies are formed.
The book is elementary written and is understandable for the se-
condary school students. The great number of exercises and research
problems are included.
ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ
Вып. 1. А. И, Маркушевич. Возвратные последовательности,
Вып. 2. И. П. Натансон. Простейшие задачи на максимум и ми-
нимум.
Вып. 3. II. С. Соминский. Метод математической индукции.
Вып. 4. А. И. Маркушевич. Замечательные кривые.
Вып. 5. П. П. Коровкин. Неравенства.
Вып. 6. Н. Н. Воробьев. Числа Фибоначчи.
Вып. 7. Л. Г. Курош. Алгебраические уравнения произвольных
степеней.
Вып. 8. А. О. Гельфонд. Решение уравнений в целых числах.
Вып. 9. А. И. Маркушевич. Площади и логарифмы.
Вып. 10. А, С. Смогоржевекий. Метод координат.
Вып. 11. Я. С. Дубнов. Ошибки в геометрических доказательствах.
Вып. 12. II. П. Натансон. Суммирование бесконечно малых ве-
личин.
Вып. 13. А. II. Маркушевич. Комплексные числа и конформные
отображения.
Вып. 14. А. II. Фетисов. О доказательствах в геометрии.
Вып. 15. И. Р. Шафаревич. О решении уравнений высших степеней.
Вып. 16. В. Г. Шерватов. Гиперболические функции.
Вып. 17. В. Г. Болтянский. Что такое дифференцирование?
Вып. 18. Г. М. Миракьяп. Прямой круговой цилиндр.
Вып. 19. Л. А. Люстерник. Кратчайшие линии.
Вып. 20. А. М. Лопшпц. Вычисление площадей ориентированных
фигур.
Вып. 21. Л. II. Головина и И. М. Яглом. Индукция в геометрии.
Вып. 22. В. Г. Болтянский, Равновеликие и равносоставленные
фигуры.
Вып. 23. А. С. Смогоржевекий. О геометрии Лобачевского.
Вып. 24. Б. И. Аргунов и Л. А. Скорняков. Конфигурационные тео-
ремы.
Вып. 25. А. С. Смогоржевекий. Линейка в геометрических построе-
ниях.
Вып. 26. Б. А. Трахтенброт. Алгоритмы и машинное решение за-
дач.
Вып. 27. В. А. Успенский. Некоторые приложения механики к ма-
тематике.
Вып. 28. II. А. Архангельский и Б. И. Зайцев. Автоматические циф-
ровые машины.
Вып. 29. А. II. Костовский. Геометрические построения одним цир-
кулем.
Вып. 30. Г. Е. Шилов. Как строить графики.
95
Вып. 31. Л. Г. Дорфман. Оптика конических сечений.
Вып. 32. Е. С. Вентцель. Элементы теории игр.
Вып. 33. А. С. Барсов. Что такое линейное программирование.
Вып. 34. Б. Е. Маргулис. Системы линейных уравнений.
Вып. 35. Н. Я. Виленкин. Метод последовательных приближений.
Вып. 36. В. Г. Болтянский. Огибающая.
Вып. 37. Г. Е. Шилов. Простая гамма (устройство музыкальной
шкалы).
Вып. 38. 10. А. Шрейдер. Что такое расстояние?
Вып. 39. И. II. Воробьев. Признаки делимости.
Вып. 40. С. В. Фомин. Системы счисления.
Вып. 41. Б. 10. Коган. Приложение механики к геометрии.
Вып. 42. IO. II. Любнч п Л. А. Шор. Кинематический метод в гео-
метрических задачах.
Вып. 43. В. А. Успенский. Треугольник Паскаля.
Вып. 44. II. Я. Бакельман. Инверсия.
Вып. 45. И. М. Иглом. Необыкновенная алгебра.
Вып. 46. II. М. Соболь. Метод Монте-Карло.
Вып. 47. Л. А. Калужниц. Основная теорема арифметики.
Вып. 48. А. С. Солодовников. Системы линейных неравенств.
Вып. 49. Г. Е. Шилов. Математический анализ в области рацио-
нальных функций.
Вып. 50. Б. Г. Болтянский, Н. Ц. Гохберг. Разбиение фигур на
менылпе части.
Вып. 51. II. М. Бескин. Изображения пространственных фигур.
Вып. 52. II. 11. Бескин. Деление отрезка в данном отношении.
Вып. 53. Б. А. Розенфельд и Н. Д. Сергеева. Стереографическая
проекция.
Вып. 54. В. А. Успенский. Машина Поста.
Вып. 55. Л. Беран. Упорядоченные множества.
Вып. 56. С. А. Абрамов. Элементы программирования.
Вып. 57. В. А. Успенский. Теорема Гёделя о неполноте.
Вып. 58. Ю. А. Шашкин. Эйлерова характеристика.
Вып. 59. Л. А. Скорняков. Системы линейных уравнений.
Вып. 60. Ю. А. Шашкин. Неподвижные точки.
Вып. 61. Л. А, Петросян, Б. Б. Рихсиев. Преследование на плос-
кости.