Еще одна задача о преследовании

Сообщение №33836 от Бел 03 июня 2004 г. 12:34
Тема: Еще одна задача о преследовании


Упомянув задачу о собаке и лисе, Snowman заставил меня вспомнить о классической задаче "Лев и человек" (есть в книжке Литлвуда "Математическая смесь")
На круглой арене лев и человек (конечно, матточки). Их максимальные скорости одинаковы. Направление движения могут менять как угодно быстро.
Пообедает ли лев?


Отклики на это сообщение:

>
> Упомянув задачу о собаке и лисе, Snowman заставил меня вспомнить о классической задаче "Лев и человек" (есть в книжке Литлвуда "Математическая смесь")
> На круглой арене лев и человек (конечно, матточки). Их максимальные скорости одинаковы. Направление движения могут менять как угодно быстро.
> Пообедает ли лев?

Кажется лев должен все время находится на отрезке между центром арены и человеком. При этом начинать льву надо с перемещения в центра арены.
Далее лев будет двигаться по кругу быстрее человека и сможет остаток скорости тратить на сближение с человеком.
Используя такую тактику лев после того как он занял центр арены должен пообедать за конечное время которое можно вычислить табличным интегралом от 2* dx / sqrt(1-x^2) на отрезке от 0 до корня из двух, единица времени - длина арены деленная на скорость льва (человека).


В корне из двух интеграл не сушествует (если комплексные значения не считаются).


интеграл от 0 до 1 деленной на корень из 2


> В корне из двух интеграл не сушествует (если комплексные значения не считаются).

спасибо - поправили


деленная на скорость льва


> >


> Кажется лев должен все время находится на отрезке между центром арены и человеком. При этом начинать льву надо с перемещения в центра арены.
> Далее лев будет двигаться по кругу быстрее человека и сможет остаток скорости тратить на сближение с человеком.
> Используя такую тактику лев после того как он занял центр арены должен пообедать за конечное время которое можно вычислить табличным интегралом от 2* dx / sqrt(1-x^2) на отрезке от 0 до корня из двух, единица времени - длина арены деленная на скорость льва (человека).

Кой-какие комментарии из книжки Литлвуда:
"Задача о льве, хотя и имеет уже 25-летнюю давность, недавно (книжка написана более 50 лет назад - Бел) вновь пронеслась по стране; но большинство из нас удовлетворилось ответом "L (лев) все время должен находиться на радиусе ОМ (М-человек)""
Этот "..."ответ" неверен; М может избежать поимки (как бы L себя не вел). Это было совсем недавно обнаружено профессором А.С.Безиковичем."


даже представить себе не могу


> даже представить себе не могу

Ваше решение, как и "стандартное", предполагает, что человек все время движется вдоль края арены.
Ответ Литлвуда.
M0 - начальная точка, в которой при t=0 находится человек (достаточно далеко от края арены).
Проведем ломаную M0M1M2M3... со следующими свойствами:
(1) MnMn+1 перпендикулярен к OMn. O - центр арены.
(2) Длина Mn-1Mn = Ln = C*nM-3/4.

Тогда
(3) Квадрат расстояния от центра до человека на энном этапе
(OM0)2 + (L1)2 + (L2)2 + ...
Этот ряд сходится и можно подобрать постоянную С так, чтобы выбранная ломаная вся была внутри арены.
(4) Сама длина ломаной бесконечна (и бесконечно время движения по ней).

Так как M0M1 перпендикулярна LM0 (лев на радиусе!), то лев не может поймать человека, пока человек находится на отрезке
M0M1. Аналогичное рассуждение справедливо для любого этапа.


Должно быть:

> (2) Длина Mn-1Mn = Ln = C*n-3/4.


> Так как M0M1 перпендикулярна L0M0 (лев на радиусе!), то лев не может поймать человека, пока человек находится на отрезке
> M0M1. Аналогичное рассуждение справедливо для любого этапа.


> > даже представить себе не могу

> Ваше решение, как и "стандартное", предполагает, что человек все время движется вдоль края арены.
> Ответ Литлвуда.
> M0 - начальная точка, в которой при t=0 находится человек (достаточно далеко от края арены).
> Проведем ломаную M0M1M2M3... со следующими свойствами:
> (1) MnMn+1 перпендикулярен к OMn. O - центр арены.
> (2) Длина Mn-1Mn = Ln = C*nM-3/4.

> Тогда
> (3) Квадрат расстояния от центра до человека на энном этапе
> (OM0)2 + (L1)2 + (L2)2 + ...
> Этот ряд сходится и можно подобрать постоянную С так, чтобы выбранная ломаная вся была внутри арены.
> (4) Сама длина ломаной бесконечна (и бесконечно время движения по ней).

> Так как M0M1 перпендикулярна LM0 (лев на радиусе!), то лев не может поймать человека, пока человек находится на отрезке
> M0M1. Аналогичное рассуждение справедливо для любого этапа.

Хорошая задача.
Небольшое замечание по форме. Расстояния L1, L2 и т.д. откладываются вдоль радиуса, тогда как в формуле (2) n может быть любым (n = 1,2,3,...). Это значит, что Mn-1Mn = Ln определяет и длины отрезков поперек радиуса.



> Ваше решение, как и "стандартное", предполагает, что человек все время движется вдоль края арены.

А если решать не ломаными?
Пусть
V^2=Vr^2+Vf^2 радиальная и тангенциальная скорости льва
V^2=Ur^2+Uf^2 то же, но у человека.
Лев начинает из центра и бежит так, что всегда находится на одном радиусе
с человеком, то есть
Vf*r=Uf*R и R больше, чем r
Тогда
Vr^2=V^2-Vf^2=V^2-(Uf*r/R)^2=V^2-(V^2-Ur^2)*(r/R)^2=
V^2(1-(r/R)^2)+Ur^2*(r/R)^2
Или
dr/dt=Vr=V*sqrt(1-(r/R)^2+(Ur/V)^2*(r/R)^2)
Время, потребное льву, чтобы оставаясь на одном радиусе с человеком, достичь
радиуса R ( максимальное время до обеда )
t=(R/V)*int(d(r/R)/sqrt(1-(r/R)^2+(Ur/V)^2*(r/R)^2) в пределах по r/R от 0 до 1
Это время меньше, чем
t'=(R/V)*int(d(r/R)/sqrt(1-(r/R)^2)= ( знаменатель немного уменьшили )
(R/V)*(arcsin(1)-arcsin(0))=(R/V)*pi/2.
Совсем не много, чуть дольше, чем до края арены из центра добежать.


> Так как M0M1 перпендикулярна LM0 (лев на радиусе!), то лев не может поймать человека, пока человек находится на отрезке M0M1. Аналогичное рассуждение справедливо для любого этапа.

Если б профессора пустить на арену вместо М, то он бы обнаружил, что Лев бежит не перпендикулярно отрезку.
И отлично догоняет профессора.


У Литтлвуда далее доказывается, что профессор может изьегнуть поимки при любой стратегии льва.


наверное в общем случае человек должен бежать в направлении перпендикулярном к направлению на льва
при этом надо следить чтобы длина пути была бесконечной
если лев находится на радиусе то алгоритм указан
если лев находится не на радиусе надо бежать в ту сторону где длина перпендикуляра больше
если лев на радиусе но снаружи от человека человек должен бежать прямо ото льва


> У Литтлвуда далее доказывается, что профессор может избегнуть поимки при любой стратегии льва.
Было бы очень интересно посмотреть на убегающего профессора.

Если стратегия льва максимально примитивна = бежать точно к профессору, то (если профессор всё-таки бросит умничать) конечной картинкой будет профессор мчащийся по большому кругу и лев догоняющий его по раскручивающийся спирали. Время бесконечное.

Если стратегией льва будет оставаться на одном радиусе с профессором, а проф будет мчаться по окружности, то если вначале проф на краю а лев в центре, то лев догонит за время = пи/4 * R / V.
Подозреваю также, что траектория льва будет полуокружность радиуса R/2 (а траектория профа четвертьокружность радиуса R).


> > У Литтлвуда далее доказывается, что профессор может избегнуть поимки при любой стратегии льва.
> Было бы очень интересно посмотреть на убегающего профессора.

> Если стратегия льва максимально примитивна = бежать точно к профессору, то (если профессор всё-таки бросит умничать) конечной картинкой будет профессор мчащийся по большому кругу и лев догоняющий его по раскручивающийся спирали. Время бесконечное.

> Если стратегией льва будет оставаться на одном радиусе с профессором, а проф будет мчаться по окружности, то если вначале проф на краю а лев в центре, то лев догонит за время = пи/4 * R / V.
> Подозреваю также, что траектория льва будет полуокружность радиуса R/2 (а траектория профа четвертьокружность радиуса R).

Это не так. Что касается "бежать прямо на профессора", то процитированный
отрывок как раз показывает, что не догонит - прочитайте внимательнее.
Профессор действительно приближается к граничной окружности и расстояние до
льва монотонно и неограниченно уменьшается, однако...
Кстати, вспоминаю, что в "В мире науки" было обобщение на увеличение размерности
задачи и числа львов - кажется, в пространстве размерности n профессор может
убежать от n-1 львов, но не более.



> > Проведем ломаную M0M1M2M3... со следующими свойствами:
> > (1) MnMn+1 перпендикулярен к OMn. O - центр арены.
> > (2) Длина Mn-1Mn = Ln = C*nM-3/4.

> > Тогда
> > (3) Квадрат расстояния от центра до человека на энном этапе
> > (OM0)2 + (L1)2 + (L2)2 + ...
> > Этот ряд сходится и можно подобрать постоянную С так, чтобы выбранная ломаная вся была внутри арены.
> > (4) Сама длина ломаной бесконечна (и бесконечно время движения по ней).

> > Так как M0M1 перпендикулярна LM0 (лев на радиусе!), то лев не может поймать человека, пока человек находится на отрезке
> > M0M1. Аналогичное рассуждение справедливо для любого этапа.

> Хорошая задача.
> Небольшое замечание по форме. Расстояния L1, L2 и т.д. откладываются вдоль радиуса,
> > (1) MnMn+1 перпендикулярен к OMn. O - центр арены.
> > (2) Длина Mn-1Mn = Ln = C*n-3/4.
То есть L1, L2 и т.д. перпендикулярны радиусам.

А расстояние от центра определяется по Пифагору.
Или я что-то не понял в Вашем замечании?



> Совсем не много, чуть дольше, чем до края арены из центра добежать.

Насколько я понял, Вы рассмотрели вариант движения человека, при котором лев действительно его поймает. Но если человек движется так, как предлагают Безикович и Литлвуд, то время бесконечно.



> Если стратегией льва будет оставаться на одном радиусе с профессором, а проф будет мчаться по окружности, то если вначале проф на краю а лев в центре, то лев догонит за время = пи/4 * R / V.

Это как? Лев пробежит меньше радиуса?
А время = пи/2 *R/V - максимум, как бы профессор не метался.

> Подозреваю также, что траектория льва будет полуокружность радиуса R/2 (а траектория профа четвертьокружность радиуса R).

А здесь льву бежать пи*R


>
> > Совсем не много, чуть дольше, чем до края арены из центра добежать.

> Насколько я понял, Вы рассмотрели вариант движения человека, при котором лев действительно его поймает. Но если человек движется так, как предлагают Безикович и Литлвуд, то время бесконечно.

Не, вариант движения человека - произвольной. От него ( варианта ) требуется
только величина тангенциальной скорости человека для льва ( стратегия у льва
такая, менять свою тангенциальную синхронно с человеком )
и радиальной для
более точного расчета времени. Но если оценка сверху пи/2*V/R устраивает,
то величина радиальной скорости человека не важна. Но если человек хочет
пожить подольше, то желательно чтобы она ( вернее ее квадрат ) была как
можно меньше.
В случае если человек движется так, как предлагают Безикович и Литлвуд, а лев
не так, как они предлагают, а оставаясь всегда на одном радиусе с человеком,
человек ловится и на удивление быстро.


> В случае если человек движется так, как предлагают Безикович и Литлвуд, а лев
> не так, как они предлагают, а оставаясь всегда на одном радиусе с человеком,
> человек ловится и на удивление быстро.

Решение Безиковича как раз показывает, что нет.


> > В случае если человек движется так, как предлагают Безикович и Литлвуд, а лев
> > не так, как они предлагают, а оставаясь всегда на одном радиусе с человеком,
> > человек ловится и на удивление быстро.

> Решение Безиковича как раз показывает, что нет.

У него лев как движется? Оставаясь все время на одном радиусе с человеком?
Именно все время, а не в отдельные моменты времени.
Если по другому, то стратегия льва плохая. А при плохой стратегии может и
не поймать.


> > Решение Безиковича как раз показывает, что нет.

> У него лев как движется? Оставаясь все время на одном радиусе с человеком?
> Именно все время, а не в отдельные моменты времени.
> Если по другому, то стратегия льва плохая. А при плохой стратегии может и
> не поймать.
Именно все время. Читайте внимательнее.Но, повторяю, есть доказательство
и для любой другой стратегии льва. Оно тоже базируется на том тривиальном
факте, что если Вы побежите по прямой, перпендикулярной линии Вы - лев, то
он Вас не догонит.Вся проблема в том, что для нахождения в круге необходимо
время от времени менять направление движения.


> > > Проведем ломаную M0M1M2M3... со следующими свойствами:
> > > (1) MnMn+1 перпендикулярен к OMn. O - центр арены.
> > > (2) Длина Mn-1Mn = Ln = C*nM-3/4.

> > > Тогда
> > > (3) Квадрат расстояния от центра до человека на энном этапе
> > > (OM0)2 + (L1)2 + (L2)2 + ...

> > Небольшое замечание по форме. Расстояния L1, L2 и т.д. откладываются вдоль радиуса,
> > > (1) MnMn+1 перпендикулярен к OMn. O - центр арены.
> > > (2) Длина Mn-1Mn = Ln = C*n-3/4.
> То есть L1, L2 и т.д. перпендикулярны радиусам.

> А расстояние от центра определяется по Пифагору.
> Или я что-то не понял в Вашем замечании?

Или, наоборот, я что-то не понял:)...
Как ломанная может состоять из одних перпендикуляров к радиусам? Ведь L1, L2 и т.д. перпендикулярны радиусам, и Ln = Mn-1Mn.



> Как ломанная может состоять из одних перпендикуляров к радиусам? Ведь L1, L2 и т.д. перпендикулярны радиусам, и Ln = Mn-1Mn.

Проще всего было бы ответить рисунком, но ... не умею.
Точка О - центр. Начальное положение человека M0. Строим M0M1 перпендикулярно ОM0. Проводим через точку
M1 радиус ОM1. Перпендикулярно этому радиусу строим отрезок M1M2 и т.д.
Длины отрезков - в соответствии с написанным в исходном варианте.


> В случае если человек движется так, как предлагают Безикович и Литлвуд, а лев
> не так, как они предлагают, а оставаясь всегда на одном радиусе с человеком,
> человек ловится и на удивление быстро.

Я совершенно согласен с тем, что ответил КС.


> > > Решение Безиковича как раз показывает, что нет.

> > У него лев как движется? Оставаясь все время на одном радиусе с человеком?
> > Именно все время, а не в отдельные моменты времени.
> > Если по другому, то стратегия льва плохая. А при плохой стратегии может и
> > не поймать.
> Именно все время. Читайте внимательнее.Но, повторяю, есть доказательство
> и для любой другой стратегии льва. Оно тоже базируется на том тривиальном
> факте, что если Вы побежите по прямой, перпендикулярной линии Вы - лев, то
> он Вас не догонит.Вся проблема в том, что для нахождения в круге необходимо
> время от времени менять направление движения.

Если все время, то посмотрите http://physics.nad.ru/rusboard/messages/33913.html
Там выписана точная формула ( интеграл ) для времени, которое затратит лев
на поимку при любой стратегии человека, а затем дана и посчитана оценка
сверху этого времени. И без всяких бесконечных последовательностей ломаных и
"очевидно, что".


> > Как ломанная может состоять из одних перпендикуляров к радиусам? Ведь L1, L2 и т.д. перпендикулярны радиусам, и Ln = Mn-1Mn.

> Проще всего было бы ответить рисунком, но ... не умею.
> Точка О - центр. Начальное положение человека M0. Строим M0M1 перпендикулярно ОM0. Проводим через точку
> M1 радиус ОM1. Перпендикулярно этому радиусу строим отрезок M1M2 и т.д.
> Длины отрезков - в соответствии с написанным в исходном варианте.

Дошло. Я просто думал о другом движении (не только поперек, но и вдоль радиуса).



> Я совершенно согласен с тем, что ответил КС.

А в решении Безиковича есть расчет для времени, когда лев всегда на одном
радиусе с человеком?
Пока Вы привели:
"Так как M0M1 перпендикулярна LM0 (лев на радиусе!), то лев не может поймать человека, пока человек находится на отрезке
M0M1. Аналогичное рассуждение справедливо для любого этапа. "

То есть лев бежит в точку, где человек находился в начале движения по ломаной.
При такой стратегии конечно не поймает.

Вы смотрели
http://physics.nad.ru/rusboard/messages/33880.html
Ошибки нашли?
Или - неправильно, потому что вывод с написанным в книжке не совпадает?


Разобрался.
Нашел ошибку в своих рассуждениях.
Возражения снимаются, лев профессора не скушает.



> А в решении Безиковича есть расчет для времени, когда лев всегда на одном
> радиусе с человеком?

По-моему, на этот вопрос я Вам уже отвечал.
Да, лев в каждый момент времени находится на прямой, проходящей через центр окружности и через человека-точку.
Если человек будет бегать по краю арены, то лев действительно его поймает за конечное время. В этом Вы правы.
Но идея Безиковича заключается в том, что для человека это вовсе не наилучшая тактика. Примем такие начальные условия: лев в центре арены, человек, скажем, на расстоянии половины радиуса от центра.
Если далее человек движется по той ломаной, которую предложил Безикович, то время поимки человека становится бесконечно большим (бесконечно велика сумма длин отрезков ломаной). При этом предполагается, что в каждый момент времени лев находится на прямой центр арены - человек.
Человек в варианте Безиковича движется по раскручивающейся спирали (спираль состоит из участков той самой ломаной). При этом строго показано, что хотя спираль и раскручивается, ее "радиус" (расстояние от человека до центра арены) и при t, стремящемся к бесконечности, остается внутри арены (подбор постоянной "с" в формулах позволяет это сделать).
Я привел наглядное изложение строго доказанного утверждения:
"Если лев все время находится между человеком и центром арены, то человек может избежать поимки".


> Пока Вы привели:
> "Так как M0M1 перпендикулярна LM0 (лев на радиусе!), то лев не может поймать человека, пока человек находится на отрезке
> M0M1. Аналогичное рассуждение справедливо для любого этапа. "

> То есть лев бежит в точку, где человек находился в начале движения по ломаной.
Нет! Лев все время на прямой человек - центр арены (см. выше)
> При такой стратегии конечно не поймает.

> Вы смотрели
> http://physics.nad.ru/rusboard/messages/33880.html
> Ошибки нашли?

Смотре. Не искал.
> Или - неправильно, потому что вывод с написанным в книжке не совпадает?

Я понимаю вывод Безиковича и не вижу в нем ошибок. Хорошо бы Вам для опровержения этого вывода сначала указать, где ошибка в доказательстве Безиковича. Укажете - появится предмет обсуждения.


> Разобрался.
> Нашел ошибку в своих рассуждениях.
> Возражения снимаются, лев профессора не скушает.

Прошу извинить, сначала ответил на Ваше предыдущее письмо, потом добрался до этого. Консенсус :-))


> > Разобрался.
> > Нашел ошибку в своих рассуждениях.
> > Возражения снимаются, лев профессора не скушает.

> Прошу извинить, сначала ответил на Ваше предыдущее письмо, потом добрался до этого. Консенсус :-))

Это работа модератора. Я запостил то же самое под своим ответом Вам,
но он его стер. Наверно надо было слова переставить...


> У него лев как движется? Оставаясь все время на одном радиусе с человеком?
> Именно все время, а не в отдельные моменты времени.
> Если по другому, то стратегия льва плохая. А при плохой стратегии может и
> не поймать.

33921
Наглядное представление о непоимки человека львом можно описать таким образом. Пусть арена это кольцо заряженное положительно а лев и человек шарики любого размера(но вместе не больше чем диаметр арены) заряженны так же положительно. Начнём двигать «шарик-льва» - «шарик-человек» начнёт удаляться не зависимо с какой скоростью движется лев. Массы шариков советуется брать одинаковыми, если арена абсолютно гладкая, то её заряжать не обязательно.



> > То есть лев бежит в точку, где человек находился в начале движения по ломаной.
> Нет! Лев все время на прямой человек - центр арены (см. выше)
> > При такой стратегии конечно не поймает.

А если лев бежит не на человека а на точку в которой этот человек будет через некоторое время не изменяя своего направления? Т.е. лев не реагирует на движения человека а анализирует ситуацию и экономит свои силы не растрачивая их по напрасну -вот такой лев стратег.
> Я понимаю вывод Безиковича и не вижу в нем ошибок. Хорошо бы Вам для опровержения этого вывода сначала указать, где ошибка в доказательстве Безиковича. Укажете - появится предмет обсуждения.
Т.е. Вы в роли льва уже обречили себя на голодную смерть(-:?
С уважением Д.


> А если лев бежит не на человека а на точку в которой этот человек будет через некоторое время не изменяя своего направления?
Тогда он соскочит с радиуса и обгонит человека по углу.
А раз так, чел может изменить угловую компоненту движения на противоположную и лев окажется отставшим.

Так что льву с радиуса соскакивать невыгодно. Оставаться на радиусе - лучшая стрателия льва.


Если человек бежит по прямой, перпендикулярной отрезку, соединяющему
его положение со львом, то лев никогда не сможет его догнать. Проблема в том,
что можно упереться в границу территории. Поэтому общая стратегия такова:
смотрим, где лев (в момент t_i), бежим по перпендикуляру на некое расстояние,
смотрим, где лев сейчас (в момент t_{i+1}), поворачиваем, бежим снова etc.
Моменты и направление поворота выбирается из следующего правила: из центра
круга проводим перпендикуляр к нашей траектории (следующему звену ломаной) и
бежим в сторону основания этого перпендикуляра, перебегая его на l_i, выбирая
его так, чтобы сумма этих длин была бесконечной, а сумма их квадратов конечной
и достаточно малой, для чего можно выбрать степенную зависимость от i с
показателем степени между 1/2 и 1.
На шаровой арене размерности n от каждого льва можно бежать по перпендикулярной
гиперплоскости. Их пересечение (от разных львов) задает в пределе n-1 львов
единственную прямую успешного убегания. Добавление еще одного льва меняет
ситуацию.


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100