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

[wrest]

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

Если с этим не согласны - приведите пример преимущества утки в такой позиции чем на том же расстоянии от центра на противоположной от лисы стороне диаметра?

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

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

Для красного треугольника и стартующей из центра и пытающейся удалиться от лисы утки (а не произвольных положений лисы и утки, в которые последняя никогда не попадёт!) это возможно.

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

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

В-третьих не только внутри вписанной окружности,

Ну естественно, поэтому я писал, что

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

фигура безопасности распадается на две зоны - там где всегда и там где иногда.

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

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

если уж геометрия это так сложно.

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

[EUgeneUS]

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

В начале погони расположение Лисы и Утки случайное.

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

Предлагаю такие варианты начала игры:
1. Либо утка у берега (точку выбирает утка), лиса на берегу напротив утки.
2. Либо утка в центре, лиса выбирает точку берега.

[wrest]

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

Предлагаю такие варианты начала игры:
1. Либо утка у берега (точку выбирает утка), лиса на берегу напротив утки.
2. Либо утка в центре, лиса выбирает точку берега.

М-м-м... думаю что оба подходят, мне больше нравится вариант 2.

[EUgeneUS]

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

[Dmitriy40]

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

Зона между берегом и описанной вокруг красного треугольника окружности -- это где Лиса всегда быстрее Утки.

Не всегда! Достаньте калькулятор и посчитайте например для смещений лисы $0{,}01$ хоть влево, хоть вправо:

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

Контрпример по рисунку выше: лиса стоит в $(0{,}5;-1)$, утка в $(-0{,}19;0{,}38)$ или в $(0{,}19;-0{,}38)$, в обоих случаях утка на диаметре, но за пределами вписанной окружности, при любом малом смещении лисы (вплоть до углов берега! ) утка имеет возможность полностью его скомпенсировать и остаться на диаметре. Считайте!

До опровержения этого утверждения цифрами все ваши утверждения про окружности считаю ошибкой/бредом.

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

В начале погони расположение Лисы и Утки случайное.

Вовсе нет: утка в центре озера. Лиса произвольно, но для утки наихудший случай - лиса в центре стороны, все остальные положения лисы дают утке преимущество.

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

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

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

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

1. Либо утка у берега (точку выбирает утка), лиса на берегу напротив утки.

Простите бред, задача формулируется для утки в центре.

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

2. Либо утка в центре, лиса выбирает точку берега.

Любое смещение лисы от центра стороны даёт утке преимущество.

-- 07.02.2018, 14:23 --

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

Во втором варианте для несимметричного озера не ясно, что брать за центр.

Вполне ясно: центр вписанной в берег окружности. Только при таком условии расстояние утке до любой из сторон берега равны.

[EUgeneUS]

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

Простите бред, задача формулируется для утки в центре.

Простите, но не для всех форм озера ясно, что брать за центр.

[wrest]

EUgeneUS
Ну сплошные непонятки, что ты будешь делать...

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

Во втором варианте для несимметричного озера не ясно, что брать за центр.

Не знаю. Если невогнутое - центр тяжести?
Лучше наверное пока ограничиться правильными многоугольниками, несмотря на протесты ув. Geen

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

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

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

[EUgeneUS]

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

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

И зачем бы это надо Утке?

[wrest]

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

И зачем бы это надо Утке?

Затем что так, на мой взгляд, будет справедливо, потому что иначе

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

может случиться так, что утка почти у берега, а лиса на противоположном крае озера.

-- 07.02.2018, 15:37 --

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

Вполне ясно: центр вписанной в берег окружности.

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

[EUgeneUS]

Для перехода к рассмотрению более разных форм озера хотелось отвязаться от "центра".

Вот такие соображения.
1. Уточним условия и определения.
1.1. Лиса двигается "по рельсам" вокруг озера. То есть не может срезать на вогнутых участках берега.
1.2. Диаметром назовем хорду, которая делит периметр озера пополам.
1.3. Хорошим озером, назовем озеро, у которого никакой диаметр не проходит по суше никаким своим отрезком. Далее будем рассматривать только хорошие озера.
1.4. У Утки лимитировано время игры. Если утка за конечное (но может быть большое) время не выходит на берег - Утка дисквалифицируется и не едет на олимпиаду это хуже, чем Утку поймает Лиса. Для избежания дедлоков.
1.5. И Утка, и Лиса всегда бегают с максимальной скоростью. Лиса может стоять. Утка - нет (по сути - для избежания дедлоков).
1.6. Реакция на изменение поведения другого животного моментальная.

2. Гипотеза об оптимальной стратегии утки при таких уточненных условиях:
В любой точке озера для утки будет оптимальной такая стратегия:
а) Если Лиса куда-то бежит (с максимальной скоростью), то плыть в точку берега, которая максимизирует разницу по времени прибытия туда Утки и Лисы.
Время прибытия Утки: расстояние по прямой делить на максимальную скорость Утки.
Время прибытия Лисы: длина куска периметра делить на максимальную скорость Лисы.
б) Если Лиса стоит, то плыть к точке берега, которая есть противоположная сторона диаметра Лисы.

[Geen]

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

То есть не может срезать на вогнутых участках берега.

Это нечестно!

[EUgeneUS]

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

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

[wrest]

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

1.1. Лиса двигается "по рельсам" вокруг озера. То есть не может срезать на вогнутых участках берега.

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

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

1.5. И Утка, и Лиса всегда бегают с максимальной скоростью.

Странное требование. Дедлоки мы исключили пунктом 1.4, так что этот - лишний. А в свете отсутствия инерции по пункту 1.6, снижение скорости и стояние на месте эмулируются малыми колебаниями.

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

а) Если Лиса куда-то бежит (с максимальной скоростью),

Бежит Лиса или стоит нет никакой разницы в связи с наличием пункта 1.6

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

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

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

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

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

Да, это вроде бы разумно.

[EUgeneUS]

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

А в свете отсутствия инерции по пункту 1.6, снижение скорости и стояние на месте эмулируются малыми колебаниями.

Да. Но Лиса может так снизить свою скорость до нуля. А утка - нет.

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

Странное требование. Дедлоки мы исключили пунктом 1.4, так что этот - лишний.

1.4 - "интегральное требование". Хотелось бы получить требование в точке. Так как Лиса и Утка двигаются с максимальной скоростью, но инерции нет, то Лиса двигается с любой скоростью (в среднем) от нуля до максимальной, а Утка всегда с ненулевой. 1.4 - доп. требование, на случай если получится, что Утка плавает "кругами".

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

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

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

[wrest]

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

На берегу пляж, а дальше от берега непроходимые для лисы джунгли.

При сильно изрезанном береге его периметр может быть очень большим, тогда наши рассмотрения теряют смысл: при таком береге Утка просто обгоняет Лису безо всякой особой стратегии: Утке надо подплыть к участку где начинается изрезанный берег, и потом просто плыть вдоль не заплывая во фьорды, и таким образом обогнав Лису, вынужденную бежать повторяя форму берега. Достаточно одной таблэтки, то есть одного длинного "луча" озера выпирающего на сушу, у которого сумма длин длинных сторон больше длины короткой больше чем в $k$ раз.