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

[Dmitriy40]

Согласен, погорячился, этот hint применим лишь для определения вершины области принятия решения, в той самой точке $(0;1-4/k)$. А что плыть по наклонной выгоднее сам же в начале доказал ...

Вытащил траекторию утки из большого лога (точнее перезапустил счёт), картинка немного странная, сетка ±90000 х ±90000, k=5,8, квадрат безопасности ±15517:

Прямые участки (это лиса забежала за угол и бежит по другой стороне уже) связаны с недоработкой алгоритма перемещения утки по сетке, не может она по диагонали плыть, а влево (слева вверху) запрещено (переступит через диаметр). Эти прямые участки по идее должны быть сглажены. Но хоть видно что квадрата достигает именно при повороте на 180°, ну и что не по окружности тоже видно. Я бы предположил что это увеличивающийся и поворачивающийся квадрат, но продемонстрировать не могу.

[wrest]

Dmitriy40 в сообщении #1290064 писал(а):

Написал программулину для симуляции утки, Вы управляете лисой. Алгоритм движения утки не полный (она никогда не двигается вниз, только влево-вправо-вверх),

То есть под углом она не ходит? А как же арккосинус?

[Dmitriy40]

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

То есть под углом она не ходит? А как же арккосинус?

Не ходит (за исключением малой добавки к $y$ на каждом шаге для исключения точных циклов, но добавка порядка 0,006° - точнее ровно единица младшей цифры координат и зависит от точности координат). Связано прежде всего с целью создания программы: доказательства недостаточности $k=5{,}66$ (точно) для победы лисы. Впрочем таких горизонтальных шагов хватает и для $k=5{,}7$ (точно). Алгоритм утки очень и очень упрощён, она даже из центра не может правильно выбраться (выбирается дёрганиями туда-обратно с тем самым мелким шагом за миллионы итераций), потому и убрал кнопочку инициализации утки в центр, ну и кругами ходить не может. Лень мне стало полно и подробно формулировать алгоритм утки.

А арккосинус ... Как уже говорил, вычисление $k$ для условия равенства путей лисы при движении утки из точки $(0;1-4/k)$ как строго на север или строго на запад/восток, так и для движения из той же точки под углом - дают одно и то же значение $k$. Т.е. лисе без разницы побежит ли утка по перпендикуляру или под углом - срываться лисе надо при достижении уткой одной и той же точки и иметь скорость не менее одной и той же величины. Возьмите калькулятор и сравните 4 пути лисы $4; 6-y; 4+(1-y)/\cos(1/k); 6-y+(1-y)/\cos(1/k)$ для $y=1-4/k$ с путями утки $1-y; 1; (1-y)/\cos(1/k); 1/\cos(1/k)$ в те же точки - увидите что $\cos(1/k)$ везде сократится.

[Dmitriy40]

Dmitriy40 в сообщении #1290125 писал(а):

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

Нарисовал график траектории утки из центра с сохранением угловой скорости лисы, получилась не совсем та кривая что думал. Жёлтый - квадрат безопасности, зелёная - траектория утки, сиреневая - трансформированная по формуле $R'=R/\cos\varphi$ окружность, думал утка по ней будет идти хотя бы до диагонали. Шаги и лисы и утки проверял от $10^{-3}$ до $10^{-7}$ (погрешность вычисления координат при этом всегда была меньше $10^{-15}$), от величины шага и значения $k$ вид траектории совершенно не меняется. Пересечение с диагональю в $(0{,}658885/k;0{,}658885/k)$, с границей квадрата в $(0{,}65150/k;1/k)$ при 56,92°, лиса добежала из $(-1;0)$ до $(-0{,}65150;-1)$. Прямой отрезок зелёной кривой - мой глюк, там утка уже не успевает за лисой, начиная с $(0{,}557115/k;1{,}117400/k)$, пройдено 63,50°. Вторая картинка - посчитано другой программой, более правильно, а результат точно тот же самый. Кстати неплохая иллюстрация что фигурой безопасности является таки квадрат - если за него сбежали, то скоро наступит момент неуспевания за лисой, пример на третьей картинке, утка стартует из $(0;1/k)$ и вынуждена бежать строго по стороне квадрата и максимально может убежать до $(-1{,}24190/k;0{,}91456/k)$ с углом 53,63°. Везде требование максимально быстрого удаления утки от центра при сохранении угла 180° на лису. Картинки кликабельны.

[ET]

А это на 19 страниц тут о чем?
Около года назад здесь на форуме обсуждалась задача-близнец этой. С убедительными аргументами, что стратегия "по касательной к кругу безопасности" - оптимальна я и лучше не существует. И всего страниц на 6
Вот, только долго искал: topic117466.html

[Geen]

ET в сообщении #1290515 писал(а):

обсуждалась задача-близнец этой.

То совсем другая задача.

[ET]

Geen в сообщении #1290517 писал(а):

ET в сообщении #1290515 писал(а):

обсуждалась задача-близнец этой.

То совсем другая задача.

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

[wrest]

Dmitriy40
Спасибо, что раскапываете дальше.
Но давайте придем к каким-то конвенциям.
Например.

В случае озера в виде правильного многоугольника с четным количеством сторон или окружности, Лиса всегда бежит с нижней (южной) стороны, середина которой $x=0;y=-1$ Не обязательно с середины, но обязательно с $y=-1$.
Если есть выбор, то Лиса предпочитает бежать против часовой стрелки, Утка тоже.
Центром озера будем называть его барицентр (центр масс). Координаты центра озера - начало координат.
Кратчайшее расстояние от центра озера до берега равно единице. В случае квадратного озера тогда длина его стороны равна 2.
Максимальная скорость Утки равна единице.
Буквой $k$ будем обозначать максимальную скорость Лисы.

-- 06.02.2018, 12:06 --

ET в сообщении #1290515 писал(а):

С убедительными аргументами, что стратегия "по касательной к кругу безопасности" - оптимальна я и лучше не существует. И всего страниц на 6

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

[grizzly]

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

В случае озера в виде правильного многоугольника с четным количеством сторон или окружности, Лиса всегда бежит с нижней (южной) стороны, середина которой $x=0;y=-1$ Не обязательно с середины, но обязательно с $y=-1$.

И решение здесь всегда находится по одному принципу: находим на оси $OY$ координату уткиной точки, которая является для Лисы точкой принятия решения (при этом точка встречи в северо-северо-западном направлении равноценна с точкой встречи в направлении запад-юго-запад).

Нужно решить для правильного треугольника -- тогда, может, станет понятен общий принцип для правильных нечётноугольников.

[wrest]

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

Нужно решить для правильного треугольника -- тогда, может, станет понятен общий принцип для правильных нечётноугольников.

Не думаю. Треугольник, как мне кажется, существенно отличается от остальных многоугольников тем, что у него при вершине острый угол. Тогда случаи у нас распадаются на такие
-- треугольник (острый угол при вершине)
-- квадрат (прямой угол при вершине)
-- многоугольники с тупым углом и нечетным количеством сторон большим 3
-- многоугольники с тупым углом и четным количеством сторон большим 4
Но - не настаиваю, возможно я и не прав.

[EUgeneUS]

ET в сообщении #1290521 писал(а):

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

Основное отличие:
1. В задаче с кораблем и прожектором один игрок - корабль, он и выбирает стратегию. Стратегия прожектора фиксирована, от действий корабля не зависит.
2.В задаче с лисой и уткой два игрока.

[worm2]

EUgeneUS уже ответил, но я бы добавил.

ET в сообщении #1290521 писал(а):

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

Действительно, для круглого озера это так. Но в этой теме с круглым озером тоже вопрос давно закрыт. Мы рассматриваем обобщения на другие конкретные формы озера (эллипс, правильный многоугольник), облизываясь при этом на обобщение для озера произвольной формы. Тут уже аналогия ломается: точка пересечения луча прожектора с границей озера движется с переменной скоростью, а мы хотим постоянную. Можно попробовать заставить прожектор крутиться с переменной угловой скоростью, чтобы обеспечить постоянную линейную. Действительно, над этим можно подумать. Но есть некоторые соображения, которые заставляют думать, что это аналогию не спасёт. Хотя бы потому, что для прожектора нужен центр, а задача может быть поставлена для озера произвольной, несимметричной, формы: где у неё центр искать?

[grizzly]

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

-- многоугольники с тупым углом и четным количеством сторон большим 4

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

[wrest]

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

1. В задаче с кораблем и прожектором один игрок - корабль, он и выбирает стратегию. Стратегия прожектора фиксирована, от действий корабля не зависит.

И кстати, для той формулировки с прожектором 4,603 не является пределом, а будет немного больше. Там картинок и численных ответов нет, так что к чему там пришли непонятно.
В нашем случае с круглым озером это все равно, что Лиса точно на юге озера, Утка точно на юге (а не на севере как у нас) круга безопасности и в начальный момент Лиса начинает бежать против часовой стрелки (вправо), а Утка начинает плыть по прямой точно на ... не знаю, наверное на восток (тоже вправо). Тогда Лиса до встречи делает почти полный круг с четвертью, а не почти три четверти как у нас, то есть бежит на полкруга больше.

[Geen]

За выходные много умного написать не удалось (скорее наоборот - два раза ловил себя на потерях двойки), страничку обновил.
Основной новый результат - появился из-за углов ещё один угол $\tg\beta=\frac{U-1}{U+1}$ где $U=\sqrt{V^2-1}$, а $V$ - отношение скоростей.