Лиса, Утка и озеро.

[EUgeneUS]

wrest в сообщении #1289353 писал(а):

Вы фактически говорите, что есть два критических круга, первый нам известен как "круг безопасности Утки", второй назовем кругом принятия решения Лисы.

Да.

wrest в сообщении #1289353 писал(а):

Чему же равен его радиус?

У меня получилось $r_2 = \sqrt{k}$
То есть этот радиус больше $k$ и меньше 1. А значит такая стратегия лисы имеет смысл.

[Geen]

EUgeneUS в сообщении #1289378 писал(а):

У меня получилось $r_2 = \sqrt{k}$

У меня получается, всё-таки, меньшая окружность... ("круг безопасности")

-- 02.02.2018, 12:34 --

worm2 в сообщении #1289334 писал(а):

Да что ж вы так человека мучаете?

Ох, прошу прощения - не хотелось лишать "радости озарения"

[worm2]

wrest в сообщении #1289340 писал(а):

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

Ну, победит она или нет — всё зависит от соотношения скоростей, критическое значение которого мы и хотим выяснить
Уже понятно, что на втором этапе оптимальный путь Утки — под углом $\arccos (1/a)$ к берегу, так что там не середина будет, а немножко в сторону. Единственная проблема, стоящая перед нами — понять, когда же начинается второй этап. Для круглого озера было показано, что это — ровно тот момент, когда Утка покидает пределы своего "круга безопасности". Для всех остальных фигур это всё ещё не понятно.
Если считать выделенное жирным шрифтом доказанным и для квадратного озера, то получается, что как только Утка покидает свой "квадрат безопасности" (в этот момент центр квадрата находится между Уткой и Лисой), Лиса должна выбрать направление и бежать в эту сторону с максимальной скоростью, сокращая угловое расстояние до Утки. А Утка должна до самого конца плыть по прямой к намеченной точке (меняя направление в нужный момент, если Лисе вздумается поменять своё направление, про это уже достаточно написано). В любом другом случае (например, если Утка захочет вернуться на свой квадрат безопасности) оптимальность нарушается.

wrest писал(а):

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

Если Утка отплыла на какое-то расстояние от своего квадрата безопасности, а потом решит вернуться к его углу, Лиса добежит до своего угла раньше.
Однако тут Вы правы в том смысле, что эту разность можно сделать сколь угодно малой. Получается, если Лиса полагает верным выделенное жирным шрифтом, и двигается в соответствии с этим планом, Утка может загнать её в угол почти в тот же момент, когда сама попадает в противоположный угол своего квадрата безопасности. Т.е. Dmitriy40 прав!

Впрочем, теперь для меня стало совершенно очевидным, что выделенное жирным шрифтом неверно для квадрата. Непонятно, когда начинается второй этап. Теперь мне кажется, что Лиса должна обладать стальными нервами и отдыхать на середине своей стороны, наблюдая за Уткой, покинувшей свой "квадрат безопасности" и плывущей во всю прыть к противоположной стороне! Должна быть какая-то другая граница, снаружи "квадрата безопасности", при пересечении которой Лиса наконец должна начать действовать.

[EUgeneUS]

Geen
Нашел ошибку у себя
Ответ с Вашим опять не совпал
Но получилось, что лиса все таки не улучшает свое положения при этой стратегии.

[wrest]

EUgeneUS в сообщении #1289378 писал(а):

У меня получилось $r_2 = \sqrt{k}$
То есть этот радиус больше $k$ и меньше 1.

Я на всякий случай уточню. $k$ это у вас во сколько раз Утка быстрее Лисы, то есть $k$ меньше единицы?
Ибо в первом посте темы эта буква определена как по-другому и она больше единицы:

wrest в сообщении #1284304 писал(а):

Пусть скорость Лисы в $k$ раз больше скорости Утки.

-- 02.02.2018, 13:10 --

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

Соображение тут простое:

wrest в сообщении #1284331 писал(а):

Смотрите: как только угол между Лисой и Уткой стал меньше развернутого, а Утка находится за пределами "круга безопасности", угловая скорость Лисы становится больше чем угловая скорость Утки, то по этой стратегии Лисы (сокращать расстояние), расстояние между Лисой и Уткой, хоть по прямой хоть угловое, будет сокращаться.

Ну скажем, при "классической" стратегии Лисы бежать сразу как только Утка выплыла из круга безопасности и не ждать когда Утка выплывет из "круга принятия решения", к моменту когда Утка будет на расстоянии "круга принятия решения Лисы" (который вы обозначили как радиусом $\sqrt{\dfrac{1}{k}}$, Лиса уже будет не на диаметре от Утки, а ближе к ней, то есть в лучших условиях.

[grizzly]

worm2 в сообщении #1289396 писал(а):

Теперь мне кажется, что Лиса должна обладать стальными нервами и отдыхать на середине своей стороны, наблюдая за Уткой, покинувшей свой "квадрат безопасности" и плывущей во всю прыть к противоположной стороне! Должна быть какая-то другая граница, снаружи "квадрата безопасности", при пересечении которой Лиса наконец должна начать действовать.

+1. Что если исходить из равенства решений "точка встречи на северном полюсе" и "точка встречи на запад-северо-западе": $4/(1-x)=6-x$. Тогда $x\approx 0.29844$ и отношение скоростей -- ~5.7. Но секретная стратегия Geen обещает ещё больше.

[Dmitriy40]

worm2 в сообщении #1289334 писал(а):

Лиса может тупо выбрать одну из сторон квадрата, встать на её середину и ждать до тех пор, пока Утка не покинет пределы малого квадрата.

Это уже другая стратегия лисы. Почему я и требую детально её описывать, это не так принципиально лишь для круга, для любых других форм берега разные стратегии приводят к разным результатам (например я приводил пример когда стратегия минимизации расстояния по прямой до утки оставляет лису неподвижной в любом многоугольнике и для эллипсов с коэффициентом сжатие не менее $\sqrt 2$).
Пока наиболее логичным мне видится указанная выше стратегия лисы (это ровно то что wrest предложил): лиса бежит в сторону уменьшения угла между радиус-векторами на утку и на лису. При 180° - в любую сторону, при 0° стоит на месте или бежит в сторону уменьшения расстояния по прямой до утки, если не находится в локальном минимуме расстояния (логично, и для исключения замирания лисы в вершинах).

С Вашим же вариантом утка может сделать следующее: покинуть квадрат безопасности в середине противоположной от лисы стороны, лиса срывается и куда-то бежит, утка поворачивает и движется параллельно квадрату безопасности бесконечно близко снаружи. При этом лиса постепенно догоняет утку (в смысле уменьшения угла между радиус-векторами), но в пределе/асимптотически утка попадает в вершину своего квадрата (бесконечно близко снаружи) одновременно с попаданием лисы в вершину берега. Т.е. пришли снова к начальному состоянию, уже на Ваших условиях.
Кроме того, если посмотрите внимательнее на выложенные логи, то увидите что утке достаточно лишь приблизиться к вершине примерно на 1%, а не попадать в неё строго, уже это обеспечивает ей выигрыш.

EUgeneUS в сообщении #1289346 писал(а):

Я засомневался в решении для круглого озера из первого поста

Да, при смене стратегии лисы ответ меняется, ничего в этом удивительного. Но описанная Вами здесь стратегия не оптимальна для лисы (лишь увеличивает предел $k$, подпуская утку ближе к берегу чем круг безопасности), потому результат из первого сообщения можно рассматривать как гарантированный при любой стратегии лисы.

Geen
Так я жду комментарий на выложенный лог перемещений утки, особенно для сетки 180х180 с $k=5{,}5$ (кроме замечания о стратегии лисы, про неё уже всё сказал в начале этого сообщения). Ваш тоже хотелось бы, и grizzly, и rockclimber, Вы вроде интересовались дискретным случаем. Если надо, могу выложить и программу, но она вообще ни разу не оптимальна и занимает строк 40 на PARI/GP. Могу даже полный лог для сетки 4х4 миллиона выложить, это 42М текста.

grizzly в сообщении #1289400 писал(а):

+1.

worm2 в сообщении #1289396 писал(а):

Должна быть какая-то другая граница, снаружи "квадрата безопасности", при пересечении которой Лиса наконец должна начать действовать.

Это несложно проанализировать аналитически при некоторых простых предположениях: утка плывёт строго на север, по достижению некоторой точки с координатой $y=1/k \ldots 1$ лиса срывается и бежит по левой дуге, утка поворачивает вправо и плывёт горизонтально до правой стороны, куда через лево-верх добегает и лиса. И найти максимум неявно заданного $k(y)$ (если не получится выразить явно), как я уже и делал для $k_3, k_4, k_5, k_6$ для движения утки не по высоте к стороне.
Задача на полчаса: явное выражение для $k=\frac{6-y}{y+1}$ для $y=0 \ldots 1$ монотонно уменьшается и максимума не имеет, т.е. на озвученных условиях утке выгоднее вообще прямо из центра плыть вправо если лиса такая тупая и сразу бежит влево, $k$ становится равным ровно $6$, без всяких квадратов безопасности. Но это уж совсем тупая лиса получается. Если же добавить квадрат безопасности, то данная стратегия утки даёт худший результат чем уже мною вычислено и ей лучше начать движение по прямой из вершины своего квадрата безопасности (что как я тоже выше показал вполне возможно).

[wrest]

worm2 в сообщении #1289396 писал(а):

Должна быть какая-то другая граница, снаружи "квадрата безопасности", при пересечении которой Лиса наконец должна начать действовать.

Ну, тут нужны какие-то соображения почему вам так кажется. Интуиция?
Вообще вот те картинки, что выкладывал ув. Geen вроде бы говорят о том, что в случае эллипса "фигура безопасности" остается центрально-симметричной, но наклоняется на какой-то угол к эллипсу (т.е. в случае озера-эллипса фигура безопасности напоминает овал, но вытянутый не параллельно эллипсу, а повернутый, в зависимости от того куда сейчас бежит Лиса - по часовой или против).

[grizzly]

Dmitriy40
Хорошо, объясните мне, пожалуйста, стратегию Утки в точке (0; 0,29844). Лиса находится в точке (0;-1). Сторона квадрата 2 (центр в начале координат). Если Утка плывёт на север со скоростью 1, Лиса со скоростью 5,7 оказывается там же. Если Утка плывёт на запад со скоростью 1, Лиса успевает по большему "периметру" с той же скоростью 5,7. У Вас скорость 5,9 -- значит в этой точке у Утки есть третья стратегия. Какая?

-- 02.02.2018, 13:20 --

wrest в сообщении #1289403 писал(а):

Интуиция?

Что насчёт моих уравнений?

[EUgeneUS]

wrest

(обсуждение гипотезы, оказавшейся неверной)

wrest в сообщении #1289398 писал(а):

Я на всякий случай уточню. $k$ это у вас во сколько раз Утка быстрее Лисы, то есть $k$ меньше единицы?
Ибо в первом посте темы эта буква определена как по-другому и она больше единицы:

Брал $k$ как отношение скорости утки к скорости лисы. Тогда $k<1$ - это радиус круга безопасности, так удобнее.

wrest в сообщении #1289398 писал(а):

"круга принятия решения Лисы" (который вы обозначили как радиусом $\sqrt{\dfrac{1}{k}}$,

Не обозначил, а посчитал. Неверно . Спасибо Geen, который также проверил эту гипотезу.

[Dmitriy40]

grizzly в сообщении #1289404 писал(а):

Хорошо, объясните мне, пожалуйста, стратегию Утки в точке (0; 29844). Лиса находится в точке (0;-1). Сторона квадрата 2 (центр в начале координат).

Прошу Вас поправить координаты утки, у Вас координата в тысячи раз больше размера квадрата. Пока ничего внятного ответить не могу.
Но я показал (на словах, все выкладки не стал приводить, хотя у меня есть на бумажке, но там же тривиально) что для утки нет преимущества от такой стратегии лисы за пределами квадрата безопасности и ей лучше пользоваться моим давним решением - движением из угла квадрата безопасности под небольшим углом к стороне, это дает $k>5{,}9$. Так что вероятно утка просто не попадёт в подразумеваемую Вами точку - ей это невыгодно и у неё есть выбор.

[worm2]

grizzly в сообщении #1289400 писал(а):

Что если исходить из равенства решений "точка встречи на северном полюсе" и "точка встречи на запад-северо-западе": $4/(1-x)=6-x$. Тогда $x\approx 0.1716$ и отношение скоростей -- ~5.7.

У меня примерно так же получилось. Но уравнение сложнее из-за учёта того, что утка на своём конечном отрезке пути плывёт не строго на север (запад), а под углом $\arccos(1/a)$ к берегу. Соответственно, значения немного другие: критическое соотношение скоростей ~5.786; Лиса начинает бежать, когда Утка проплывает 0.2984 на север (удаляясь от "квадрата безопасности" на 0.1256).

[Dmitriy40]

wrest в сообщении #1289403 писал(а):

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

Без уточнения стратегии лисы - я не согласен, уже дважды обосновывал что никакого наклона нет и не должно быть, есть отражение относительно центра и уменьшение в $k$ раз. И легко получается требованием одинаковых угловых скоростей утки и лисы на границе области безопасности утки и максимизации расстояния утки от центра.

[worm2]

wrest в сообщении #1289403 писал(а):

Ну, тут нужны какие-то соображения почему вам так кажется. Интуиция?

По моим расчётам, Лиса должна стартовать, когда Утка отплывает на вот такое расстояние от центра квадрата:

$$x=\frac{2a\sqrt{a^2-1}}{a^3+(a-1)\sqrt{a^2-1}} > \frac 1 a$$

(позднее добавление: неравенство верно не для всех $a$! Нас интересуют только достаточно большие $a$, скажем, большие $\sqrt{2}$; для меньших $a$ оптимальные стратегии животных, вероятно, будут существенно другими)
Тогда расстояние между животными в конечный момент времени будет одинаковым вне зависимости от того, к какому берегу вздумается поплыть Утке. Критические значения $a$ и $x$ при такой стратегии я привёл в предыдущем сообщении.

[grizzly]

Dmitriy40,
У меня там были ещё опечатки, но уже не важно. worm2 привёл аккуратные выкладки. Теперь нужны более аргументированные возражения, чем "вероятно" и "кажется".