Волк и заяц

[Gortaur]

Когда я еще был на первом курсе, один преподаватель вспомнил про одну задачу, которую ему задали решать когда он в МФТИ учился. Помню не дословно, но она недавно вспомнилась и я (уже понаторевший в математики) хотел бы ее поизучать. В общем, дело такое:
есть пруд скажем радиуса $R$, в нем в центре находится заяц. Плавает он со скоростью $z_p<w$ где $w$ - скорость волка, который бегает по берегу. Если заяц выберется на берег, его скорость будет скажем $z_b = 5w$ то есть он с легкостью от волка улизнет. Какой стратегией кто из них должен пользоваться (волк хочет догнать и съесть, заяц - убежать) чтобы победить, и для кого победа возможна.
Я тогда ему ответил, что мол на любую стратегию одного игрока придется беспроигрышная (и похоже, не выигрышная) стратегия другого, на что он сказал, что все не так-то просто и он ее решил. Там дело было даже не столько в решении, сколько в том, как запрограммировать эту задачу.
Мое мнение до сих пор, что если нет стратегии типа "заяц успеет с самого начала дать деру по воде так, чтобы выскочить на берег до того, как в том месте будет волк" - то на любую стратегию зайца найдется беспроигрышная стратегия волка, и наоборот.
Может кто слышал о такой задаче и ее решении, или я ее неправильно сфорумулировал?

[ewert]

Это далеко не первое вхождение этой задачи в форум. Вот последний вариант:

сообщение #373564

(т.е. теперь уже предпоследниий)

[TOTAL]

ewert в сообщении #376340 писал(а):

Это далеко не первое вхождение этой задачи в форум. Вот последний вариант:
сообщение #373564

Там не указана стратегия, не обоснован приведённый ответ.

[Gortaur]

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

[TOTAL]

Gortaur в сообщении #376362 писал(а):

К тому же где есть утверждение, что именно эта стратегия оптимальна

Вы про какую стратегию говорите?

[Gortaur]

Которая для зайца делает возможным побег при условиях на скорости. Выполнено ли этой для любой стратегии волка и любых начальных условиях?

[Padawan]

Для отношения скоростей $\pi+1$ понятно как решать. Заяц должен плыть от центра озера, постоянно находясь на одном диаметре с волком до тех пор, пока его скорость это позволяет ( до радиуса $r=R\frac{z}{w}$). При отношении скоростей $\pi+1$ в итоге заяц попадает в безопасную зону $r=R-\frac{z}{w}R\pi$, откуда просто плавёт по радиусу к берегу, не обращая внимания на действия волка.

А как получено условие с интегралом, непонятно.

[TOTAL]

Gortaur в сообщении #376382 писал(а):

Которая для зайца делает возможным побег при условиях на скорости. Выполнено ли этой для любой стратегии волка и любых начальных условиях?

Т.е. ни о какой стратегии Вы не говорите.

-- Ср ноя 17, 2010 14:01:04 --

Padawan в сообщении #376392 писал(а):

Для отношения скоростей $\pi+1$ понятно как решать. Заяц должен плыть от центра озера, постоянно находясь на одном диаметре с волком до тех пор, пока его скорость это позволяет ( до радиуса $r=R\frac{z}{w}$). При отношении скоростей $\pi+1$ в итоге заяц попадает в безопасную зону $r=R-\frac{z}{w}R\pi$, откуда просто плавёт по радиусу к берегу, не обращая внимания на действия волка.

А как получено условие с интегралом, непонятно.

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

[Gortaur]

То есть используется стратегия безопасного положения: как только находимся в положении, где любые действия волка нам ни по чем, удираем. Из других положений выбраться невозможно?

[Padawan]

TOTAL в сообщении #376393 писал(а):

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

По радиусу ближе, да и волку бежать дальше. Или я чего-то не понимаю?

-- Ср ноя 17, 2010 15:49:38 --

Gortaur в сообщении #376419 писал(а):

То есть используется стратегия безопасного положения: как только находимся в положении, где любые действия волка нам ни по чем, удираем. Из других положений выбраться невозможно?

Вы конкретные ограничения на скорости волка и зайца приведите. Вам же говорят, что если скорость волка не более, чем в $\pi+1$ раз больше скорости зайца, то заяц всегда может убежать, независимо от действий волка и их начального положения.

[TOTAL]

Padawan в сообщении #376420 писал(а):

TOTAL в сообщении #376393 писал(а):

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

По радиусу ближе, да и волку бежать дальше. Или я чего-то не понимаю?

Если заяц маленько отклонится от радиуса, то его путь удлинится намного меньше, чем путь волка.

[Padawan]

А откуда Вы знаете в какую сторону побежит волк?

[TOTAL]

Padawan в сообщении #376424 писал(а):

А откуда Вы знаете в какую сторону побежит волк?

Слежу за волком. Делаю вид, что двигаюсь по радиусу. Волк вынужден гнаться за мной и сойти с диаметра, скажем, по часовой стрелке. Заметив это, заяц тоже отклоняется от радиуса по часовой стрелке примерно под углом 60 градусов. (Думаю, при оптимальной стратегии надо поплыть под прямым углом к радиусу.) Волк не может изменить направление своего бега, т.к. в этом случае он опять окажется на одном диаметре с зайцем, только заяц будет уже ближе к берегу.

[Руст]

Пусть скорость волка в $a$ раз больше чем у зайца, когда он плавает. Радиус пруда нормируем так, что $R=a$, скороц плавания зайца $1$. Тогда заяц легко может оказаться на расстоянии 1 от центра пруда, так, чтобы волк был на диаметрально противоположной стороне. Далее уже волк бежит только в одну сторону, так как угловая скорость зайца уже меньше чем у волка и волк постоянно догоняет по углу разворота. У зайца лучшая стратегия плавать к берегу и слегка отклоняться. Простая вариационная задача. Которая привело к условию, когда заяц может увильнуть от волка.
Правда я не подсчитал, численное значение максимально возможного значения $a$.

[TOTAL]

Руст в сообщении #376437 писал(а):

У зайца лучшая стратегия плавать к берегу и слегка отклоняться. Простая вариационная задача. Которая привело к условию, когда заяц может увильнуть от волка.$a$.

В этой стратегии заяц бежит по прямой линии? Если нет, то почему?