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

[wrest]

На другом форуме возник следующий вопрос.

Есть известная задача: Утка плавает в озере круглой формы. Лиса хочет Утку съесть, а Утка хочет добраться до берега чтобы пощипать траву. Может ли Утка добраться до берега озера и пощипать травы если скорость Лисы в 4 раза больше скорости Утки?

Ответ на эту задачу известен: может. Обычно приводятся такие рассуждения. Если Утка плывет по окружности, а Лиса бежит по берегу озера, то угловая скорость Утки может быть больше угловой скорости Лисы пока радиус окружности по которой плывет Утка меньше радиуса озера в 4 раза. Таким образом, Утка может встать в такую позицию относительно Лисы, что Лисе надо будет пробежать половину длины окружности озера, а Утке проплыть 3/4 радиуса озера, так что Утка успеет.

При вышеописанной стратегии Утки и Лисы получается так, что предельное соотношение их скоростей, при котором Утка и Лисы прибывают к берегу одновременно, равно $\pi+1 \approx 4,14159...$, при бОльше скорости Лиса Утку ловит.

Однако, при другой стратегии Утки, получается что и при бОльшем чем $\pi+1$ соотношении скоростей, Утка добирается до берега раньше чем Лиса.

Пусть у нас есть декартовы координаты с центром в середине озера.

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

Тогда предельный радиус окружности, где угловая скорость Утки больше угловой скорости Лисы, равен $1/k$.

Тогда Утка всегда может встать в позицию так что её координаты равны $(0;1/k)$ при том что координаты Лисы будут $(0;-1)$. Пусть это будет начальная позиция.

Из начальной позиции Утка начинает движение параллельно и однонаправленно с $Ox$ и как только Лиса побежала против часовой стрелки, Утка сразу поворачивает на $\pi$. Считаем, что этот маневр занимает пренебрежимо малое время. Он нужен для того, чтобы Лиса побежала против часовой, и далее в каждый момент времени угол между Лисой и Уткой будет только сокращаться так что Лисе нет резона поворачивать обратно. Соответственно, будем считать что Утка с самого начала плывет к берегу по прямой $y=1/k$, а Лиса бежит против часовой стрелки.

На картинке ниже большая окружность - озеро, радиус 1. Малая окружность - "безопасная окружность", радиус $1/k$.
$B$ - начальное положение Лисы,
$C$ - начальное положение Утки,
$CD$ - расстояние которое надо проплыть Утке.
Дуга $BD$ против часовой стрелки - расстояние которое надо пробежать Лисе.

То есть путь Лисы показан красным, путь Утки - синим.

Если я всё верно посчитал, то уравнение равенства времени в пути Лисы и Утки такое:
$\sqrt{1-\dfrac{1}{k^2}}=\dfrac{\dfrac{3\pi}{2}-\arcsin \dfrac{1}{k}}{k}$
где $k$ - во сколько раз скорость Лисы больше скорости Утки.
Его решение (численное, спасибо Вольфраму) $k=4,60334$ и это больше чем $\pi+1$.

Вопрос, собственно: какова все-таки оптимальная стратегия Утки и Лисы и каков предел по отношению скорости Лисы и Утки при котором Лиса еще не ловит Утку.

Ответ мне неизвестен, но выше вроде бы показано что при отношении скоростей $4,6$ Утка убегает.

[Sender]

Ну нет, лиса на это не купится, особенно голодная.

[rockclimber]

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

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

Есть резон, на вашей диаграмме длина дуги $BD$ по часовой в 2 с лишим раза короче, чем против. Если Лиса видит направление движения утки, она "вычислит" точку, в которую плывет утка, и побежит туда по кратчайшему пути.

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

[wrest]

rockclimber в сообщении #1284324 писал(а):

Есть резон, на вашей диаграмме длина дуги $BD$ по часовой в 2 с лишим раза короче, чем против. Если Лиса видит направление движения утки, она "вычислит" точку, в которую плывет утка, и побежит туда по кратчайшему пути.

Тогда, если Лиса так сделает, Утка опять повернет ровно в тот момент когда между ними будет угол 180 градусов. Но теперь Утка будет уже дальше от "безопасного круга".
При такой стратегии имхо Лиса не поймает Утку никогда, т.к. будет метаться из стороны в сторону...

rockclimber в сообщении #1284324 писал(а):

Ваше решение такой возможности не дает и требует более глупой версии лисы.

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

[rockclimber]

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

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

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

[wrest]

rockclimber в сообщении #1284329 писал(а):

Да просто двигаться в ту сторону, где расстояние по прямой между ней и уткой будет сокращаться.

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

-- 15.01.2018, 18:01 --

rockclimber в сообщении #1284329 писал(а):

В одной из версий этой задачи, виденных/слышанных мной ранее, эта стратегия вроде бы была дана прямо в условии.

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

Но если Лиса не знает траектории Утки наперед, вот тут и начинается большая игра

[grizzly]

wrest
Предлагаю такую стратегию для лисы. Если утка сокращает расстояние между своим положением и внутренним кругом, лиса останавливается и ждёт. Как только утка начинает удаляться от внутреннего круга, лиса бежит по ближайшей дуге в сторону предполагаемой точки пересечения. Эта стратегия для лисы должна быть лучше, кажется.

[wrest]

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

Если утка сокращает расстояние между своим положением и внутренним кругом, лиса останавливается и ждёт.

Тогда Утка плывет по кругу не сокращая и не увеличивая расстояние до внутреннего круга (ну или сокращая инфинитезимально) пока не окажется напротив Лисы. И Лиса в пролёте.

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

лиса бежит по ближайшей дуге в сторону предполагаемой точки пересечения.

Это, опять же, позволяет Утке вилять и управлять Лисой. Кстати, раз уж на то пошло. Утке (и Лисе) необязательно двигаться с фиксированной скоростью, они могут двигаться и медленнее. Тогда, просто стоя на месте и направившись туда или сюда, Утка будет управлять Лисой.

[grizzly]

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

Тогда Утка плывет по кругу не сокращая и не увеличивая расстояние до внутреннего круга

Согласен, что нужен чуть более сложный алгоритм. Но не верю, что Ваш нельзя улучшить за лису.

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

Тогда, просто стоя на месте и направившись туда или сюда, Утка будет управлять Лисой.

В этом случае Лиса выигрывает (Утка никогда не поест).

[rockclimber]

wrest
Давайте на выходных я потрачу пару часов времени и напишу программку, где вы будете управлять уткой, а лиса будет действовать по описанной мной стратегии. Вы ее скачайте и играйтесь на здоровье, как победите - приходите за призом

[wrest]

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

В этом случае Лиса выигрывает (Утка никогда не поест).

Смотрите: Утка, подплыв почти к берегу, разворачивается плывет к центру со своей половинной скоростью, Лиса бежит вокруг, к точке куда направляется Утка, и когда Лиса оказывается напротив, через центр, Утка разворачивается и плывет с полной скоростью к берегу.
Не-е-е, вот тут уж Лиса не дура, так бегать не будет.
Как только угловое расстояние сравнялось, а Утка находится снаружи "круга безопасности", у Лисы ясная стратегия: держать угол между ней и Уткой нулевым, и она это может т.к. её углвая скорость а прделами круга безопасности больше чем у Утки.

-- 15.01.2018, 18:45 --

rockclimber в сообщении #1284342 писал(а):

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

Давайте. Хотя, в общем-то, все украдено до нас: http://log-in.ru/articles/lisicsa-i-utka/
Но там все слишком быстро...

[rockclimber]

Давайте сделаем первый ход. Вот картинка, утка начала движение из пункта $C$ в пункт $D$ (красный кружок). Лиса, двигаясь со скоростью примерно в $4,5$ раз больше, может оказаться либо в левом зеленом кружке, либо в правом. В каком случае она будет дурой и почему?

[Sender]

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

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

А если лиса будет бежать ровно с такой скоростью, чтобы прибыть к месту встречи одновременно с уткой?

[rockclimber]

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

Давайте. Хотя, в общем-то, все украдено до нас: http://log-in.ru/articles/lisicsa-i-utka/
Но там все слишком быстро...

Плохой пример, скорость реакции компьютера намного больше человеческой, проверить граничные случаи невозможно. Я планировал сделать пошаговую программу.

[wrest]

rockclimber в сообщении #1284345 писал(а):

Давайте сделаем первый ход. Вот картинка, утка начала движение из пункта $C$ в пункт $D$ (красный кружок).

Утка начинает движение вправо! И двигается вправо в течение времени $t=0,01$ c (ну то есть - просто очень малое время). Лиса, естественно, начинает бежать вправо. Через 0,01с между Лисой и Уткой образуется угол меньший 180 градусов (если считать углы против часовой стрелки). И вот, в момент 0,01с Утка вероломно поворачивает на 180 градусов и плывет влево. Но поскольку Утка уже за пределами внутреннего круга, её угловая скорость меньше чем угловая скорость Лисы, так что продолжая бежать против часовой стрелки, Лиса непрерывно сокращает угловое расстояние между собой и Уткой.

-- 15.01.2018, 18:56 --

Sender в сообщении #1284348 писал(а):

А если лиса будет бежать ровно с такой скоростью, чтобы прибыть к месту встречи одновременно с уткой?

Есть ограничения на скорость Лисы: её скорость не больше чем в k раз больше максимальной скорости Утки, максимальная скорость Утки равна единице, радиус озера равен единице.