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

[Dmitriy40]

Да, походу я постоянно путаю синус и тангенс.
Ограничение $k>5{,}7015$ верно лишь при горизонтальном/вертикальном пути утки, при произвольном довороте утки ограничение возрастает до $k>5{,}79$ (примерно, точно пока не подсчитал). А координата принятия решения $0{,}2984$ при этом не меняется.

[wrest]

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

Еле-еле разобрал случай, когда озеро — (бесконечный) угол, меньший развёрнутого. Для конечных озёр, являющихся выпуклыми многоугольниками, это даёт локально оптимальную стратегию, когда Утка находится относительно близко от одной стороны или от одной вершины угла (относительно далеко от других вершин).

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

Если интересно, я могу выложить решение для угла.

Да, интересно - а какие там подводные камни?
Вернее, какова постановка задачи, в случае бесконечного угла?
Я так понимаю, единственно разумная тут постановка задачи это когда начальная позиция Утки где-то на биссектрисе, а Лисы - в вершине.
Решение вроде тоже как очевидно: Утка плывет "по арккосинусу":

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

Если утка уже "близко" к берегу, а лиса "неподалёку", то без потери общности берег можно "спрямить" и решать следующую задачу. Пусть озеро занимает верхнюю полуплоскость, утка находится в точке с координатами $(0,h)$, а лиса - $(-a,0)$. Скорость утки $1$, а лисы $V$. В какой точке $(d,0)$ утке надо вылезать на берег, чтобы максимизировать расстояние до лисы в этот момент?
Задача решается довольно просто. Пусть $r$ - расстояние между уткой и лисой в момент вылезания утки. Тогда $r=(a+d)-V\sqrt{h^2+d^2}$. Максимум достигается при $\frac{dr}{dd}=1-\frac{Vd}{\sqrt{h^2+d^2}}=0$. То есть, при $d=\frac{h}{\sqrt{V^2-1}}$.
Таким образом, выход утки на берег составляет с касательной к берегу угол $\cos\alpha=1/V$.

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

Остается только вопрос что если Утка и Лиса по одну сторону от биссектрисы, но кажется и тут все просто. Или под "Еле-еле разобрал случай" вы имели в виду именно его?

[Geen]

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

Решение вроде тоже как очевидно

Не совсем: http://www.k-labs.ru/dms/fdl.html#1toc4

[wrest]

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

Не совсем: http://www.k-labs.ru/dms/fdl.html#1toc4

Ссылка не открывается (connection time out).

[worm2]

Решение для Угла:


Я пишу "Угол" с большой буквы, чтобы не путать его с другими вспомогательными углами на рисунке.
Величина Угла — $2\alpha$. Вершину я поместил в начало координат, а биссектриса направлена вниз по ординате.
Вы правы, для бесконечного Угла нужна немного другая постановка, чем для конечного озера. А именно: вместо позиции Лисы рассматривается его отражение. Для конечного озера отражение — это точка границы озера, максимально удалённая от позиции Лисы, расстояние до которой по границе в любую сторону равно половине периметра. Для центрально-симметричных озёр это действительно будет отражением относительно центра симметрии.
Так вот, в данной постановке мы работаем только с отражением Лисы, обозначив его через $s$. Расстояние до $s$ Утка пытается минимизировать, а Лиса — максимизировать. Числовое выражение $s$ — это расстояние до вершины Угла, взятое со знаком "минус", если отражение слева от вершины и со знаком "плюс", если справа (таким образом, в декартовой системе координаты отражения — $(s\sin\alpha, -|s|\cos\alpha)$).
$M(x, y)$ — позиция Утки. Как и на предыдущем рисунке, $\varphi=\arcsin(1/k)$ — "угол скорости", а зелёные лучи — это углы $\varphi$, отложенные вниз от ординаты (как уже давно выяснили, Утка должна подплывать к берегу под углом $\arccos(1/k)=\pi/2-\varphi$).
Я здесь рассматриваю только случай $\alpha>\varphi$. Случай $\alpha<\varphi$ вычислительно гораздо проще, но результаты, наоборот, гораздо любопытнее: при определённом начальном соотношении $M$ и $s$ Утка всегда "ловит" отражение Лисы, т.е. добивается конечного расстояния 0 (см. описание первого этапа в решении для квадрата).
Стандартным образом из точки $M$ опускаются перпендикуляры на стороны Угла, от которых откладываются во все стороны углы $\varphi$. Это всевозможные направления движения Утки. Их всего 4 штуки, но на рисунке я обозначил только два: $N_1$ и $N_2$. Остальные два получаются из них отражением относительно соответствующих перпендикуляров.
Стратегии Утки внутри зелёного угла и вне его отличаются.
Вне зелёного угла Утка ведёт себя так, как будто существует только одна сторона Угла: ближайшая к ней. Утка строит перпендикуляр на эту сторону и от этого перпендикуляра доворачивает на угол $\varphi$ в ту же сторону, по которую находится $s$ (относительно этого же перпендикуляра). Например, если Утка находится в точке $M_1$ на рисунке, то она смотрит, с какой стороны находится $s$ относительно $M_2$ и доворачивает в ту же сторону (я напоминаю, что Утка пытается приблизиться к отражению, а не убежать от него).
Внутри зелёного угла для Утки разрешёнными являются только направления $N_1$ и $N_2$. Какое именно — определяется положением $s$ относительно точки $M_2$, которая является проекцией точки на зелёном угле с абсциссой Утки $x$ ($M_1$) на ближайшую сторону Угла. Если $s$ находится слева от $M_2$, Утка плывёт в направлении $N_1$, иначе — в направлении $N_2$.
В каждой точке пути Утка пересматривает направление движения исходя из своего положения внутри или вне зелёного угла и из взаимного расположения своего отражения $M_2$ и отражения Лисы $s$. Однако, если отражение Лисы бежит оптимально (с максимальной скоростью удаляясь от отражения Утки $M_2$), то и Утка будет до конца плыть в одном направлении.
Оптимальное значение конечного расстояния от Утки до отражения Лисы в момент приплытия к стороне Угла даётся формулой:

$$F(x, y, s)= - y\sin\alpha\ctg\varphi - \max\{|x|\ctg\varphi, -y\}\cos\alpha + |s-x\sin\alpha-\min\{|x|\ctg\varphi, -y\}\mathrm{sgn\,} x\cos\alpha|.$$

(формула верна для любой позиций Утки внутри Угла: как внутри зелёного угла, так и вне его, но только для $\alpha>\varphi$ — см. выше).
Первое слагаемое этой суммы характеризует расстояние от Утки до границы Угла, второе равно расстоянию (по границе) между отражениями $s$ и $M_2$. Минимум этой величины по всем $s$ (т.е. то, чего может добиться Утка, если изначально $s$ совпадает с отражением Утки $M_2$) даётся первым слагаемым:

$$G(x,y)=\min\limits_{s}F(x, y, s)= - y\sin\alpha\ctg\varphi - \max\{|x|\ctg\varphi, -y\}\cos\alpha.$$

Функции $F$ и $G$ имеют смысл для любой границы озера (но, разумеется, для каждого озера разные). Красным цветом на рисунке обозначена линия уровня функции $G$ для Угла. В случае конечного озера линия уровня $G(x,y)=P/2$ (где $P$ — периметр озера) является границей фигуры принятия решения.

[wrest]

worm2
А где Лиса то? Я не понял как строится ее "отражение" в случае бесконечного Угла

[worm2]

В случае бесконечного Угла нельзя ставить вопрос о позиции Лисы. Я в начале написал. Мы вынуждены переформулировать задачу так, чтобы работать только с её "отражением". Но как только мы начинаем рассматривать конечное озеро, в котором Утка приблизилась достаточно близко к стороне или вершине Угла (точнее: попала в область, где зелёные лучи от соседних Углов не пересекаются; для квадрата это будет квадрат минус внутренний красный квадрат — фигура принятия решения), решение для Угла вступает в законные права и позиция Лисы сразу определяется: она является противоположной для отражения точкой озера, т.е. точкой, расстояние от которой до отражения (по границе озера) равно половине периметра озера (в квадрате — точка $M_3$, противоположная отражению $M_2$).

[wrest]

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

В случае бесконечного Угла нельзя ставить вопрос о позиции Лисы. Я в начале написал.

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

[worm2]

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

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

По координатам Утки $M(x, y)$ в начальный момент времени рассчитываем позицию её отражения $M_2$, а также функцию $G(x, y)$. Если в начальный момент времени координата Лисы $s$ находится в пределах интервала $[M_2-G(x,y), M_2+G(x,y)]$, то она ловит Утку на бесконечном угле. Если вне этого отрезка — Утка успевает к берегу на расстоянии $|s-M_2|-G(x,y)$ от Лисы.
Понятие же "критической скорости" применимо только к конечным озёрам. Можно ещё определить другую "критическую скорость-2" как максимальную скорость, при которой Утка убегает от Лисы "как от стоячей", т.е. может при любых действиях Лисы достигнуть берега в тот момент, когда Лиса находится в ровно противоположной точке озера. Такая "критическая скорость-2" может быть определена и для бесконечного угла $2\alpha$: она равна $1/\sin\alpha$. Для озёр с гладкой границей такая "критическая скорость-2", кажется, равна 1, для квадрата — $\sqrt{2}$, а для равностороннего треугольника — 2.

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

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

Это похоже на построение решения "с конца", на которое Geen уже давно намекает
Да, это правильный подход, но у меня он пока не получается.

[wrest]

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

Понятие же "критической скорости" применимо только к конечным озёрам.

Ну как же так-то... Вот имеем натурально Утку и Лису, и бесконечное озеро в виде Угла. Утка в начальный момент где-то на биссектрисе Угла, Лиса в вершине. Чему равна критическая скорость Лисы? Тут же применимо? Как я понимаю, вы даже полагаете её равной $\sqrt{2}$ для прямого Угла

[worm2]

Да, тут применимо. Это то, что я назвал "критическая скорость-2". Но это не та "критическая скорость" для квадрата, о которой речь шла изначально, как только мы начали рассматривать квадратное озеро.

Наверное, я зря написал, что "в случае бесконечного Угла нельзя ставить вопрос о позиции Лисы". Можно, конечно. Просто, на мой взгляд, удобнее работать с отражением. Даже для конечного озера удобнее. Я к такому выводу пришёл.

[worm2]

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

Общее решение для правильного $n$-угольника по вышеописанной схеме даёт следующее уравнение на $\varphi=\arcsin(1/k)$:

$$\sin\left(\varphi+\frac\pi n\right)\left(\cos\frac\pi n\cos\varphi-n\sin\frac\pi n\sin\varphi\right)=\sin\varphi\cos\varphi$$

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

$$\ctg\varphi\ctg\left(\varphi+\frac\pi n\right)=n.$$

Цитата:

при дополнительном условии $\varphi>\dfrac{\pi(n-4)}{2n}$ (при невыполнении этого условия Утка не может выйти на границу ФПР ровно в противоположной от Лисы точке).
К сожалению, дополнительное условие нарушается уже при $n=5$...

Во-вторых, кажется, удалось разобраться с этой проблемой. Для правильного многоугольника однократное применение схемы нарушает указанное условие, но получившаяся конфигурация представляет собой внутренний $n$-угольник, подобный исходному, и скорость Лисы на этом $n$-угольнике также постоянна, но меньше исходной: вместо $1/\sin\varphi$ она уменьшается до $1/\sin(\varphi+\pi/n)$. Т.е. мы пришли к той же задаче, но с уменьшенной скоростью Лисы (удобнее представлять её углом скорости $\varphi$, который вырос на $\pi/n$). Решая её по той же схеме, мы можем уже получить решение, удовлетворяющее дополнительному условию (давайте, что ли, его называть условием принятия решения).
Для пятиугольника получается такое уравнение:

$$\ctg\varphi\ctg\left(\varphi+\frac\pi 5\right)+\ctg\left(\varphi+\frac\pi 5\right)\ctg\left(\varphi+\frac{2\pi} 5\right)=5,$$

решение которого ($\varphi\approx 0.19$) уже удовлетворяет модифицированному условию принятия решения $\varphi+\dfrac\pi 5>\dfrac{\pi(5-4)}{2\cdot 5}$.
WolframAlpha нашёл следующее решение этого уравнения в радикалах (для скорости $k=1/\sin\varphi$):

$$k_5=\sqrt{\frac{217}{2}-42\sqrt{5} + \frac{7}{2}\sqrt{1625 - 720\sqrt{5}}}\approx 5.306092.$$

При этом ФПР для пятиугольника представляет собой тот же пятиугольник, подобный исходному уже без поворота , вне ФПР пятиугольник разбивается уже не на 10, а на 20 треугольников, внутри каждого из которых "отражение Утки" на исходный пятиугольник определяется по-своему, и пара направлений (куда Утке следует плыть в зависимости от расположения её отражения относительно отражения Лисы) — также своя.
Рисунок пока не осилил.
Если же и на второй итерации не выполняется условие принятия решения, то никто не запрещает нам сделать третью, четвёртую, и т.д. сколько нужно итераций, на каждой из которой угол скорости $\varphi$ увеличивается на $\pi/n$. Точное количество итераций $M$ определяется условием принятия решения: $\varphi>\dfrac\pi 2-(M+1)\dfrac\pi n$, или

$$M=M(\varphi,n)=\left\lceil n\left(\frac 1 2-\frac\varphi\pi\right)\right\rceil-1.$$

И уравнение на $\varphi$ для правильного $n$-угольника принимает окончательный вид:

$$\sum\limits_{m=1}^{M(\varphi,n)}\ctg\left(\varphi+(m-1)\frac\pi n\right)\ctg\left(\varphi+m\frac\pi n\right)=n.$$

Неплохо было бы проверить, что при стремлении $n$ к бесконечности решение стремится к решению для круга, из первого сообщения темы

UPD: Численно проверил, если подставить в качестве $\varphi$ решение уравнения $\ctg\varphi=3\pi/2-\varphi$ (у этого уравнения много корней; нас интересует тот, которой около 0.21898, дающий для круга $k=1/\sin\varphi\approx 4.6033$), то при стремлении $n$ к бесконечности видно, что разность левой и правой частей стремится к нулю.

UPD2: Не оказалось никаких особых сложностей и с аналитическим доказательством. Берём $\Delta x=1/n$ и устремляем к нулю. Получается уравнение $\displaystyle{\int\limits_\varphi^{\pi/2} \ctg^2 x\,dx=\pi}$, которое сводится к тому же самому.

[wrest]

worm2
Я не очень понимаю что вы делаете, но из ваших формул как-то должны следовать значения критической скорости Лисы для правильных $n$-угольников. Моя "нумерологическая" формула ( post1290953.html#p1290953) даёт следующее (внес также ваши значения $k$ для $n=3,4,5$):

(Оффтоп)

n   wrest   worm2
03  7,614   7,405
04  5,861   5,702
05  5,323   5,306
06  5,076
07  4,939
08  4,855
09  4,800
10  4,761
11  4,733
12  4,711
13  4,695
14  4,682
15  4,671

Интересно было бы сравнить.

[worm2]

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

...из ваших формул как-то должны следовать значения критической скорости Лисы...

Нужно решить последнее (со знаком $\Sigma$) уравнение (относительно $\varphi$), например, численно.
Получается вот что:

n   wrest   worm2
03  7,614   7,405
04  5,861   5,789
05  5,323   5,306
06  5,076   5,055
07  4,9395  4,9386
08  4,855   4,848
09  4,800   4,797
10  4,761   4,758
11  4,733   4,730
12  4,711   4,710
13  4,695   4,693
14  4,6822  4,6821
15  4,6719  4,6707
16  4,6634  4,6630
17  4,6565  4,6558
18  4,6507  4,6501
19  4,6458  4,6455
20  4,6416  4,6411
21  4,6380  4,6379
22  4,6349  4,6345
23  4,6322  4,6320
24  4,6298  4,6296
25  4,6277  4,6275
26  4,6259  4,6258
27  4,6242  4,6240
28  4,6228  4,6227
29  4,6214  4,6213
30  4,62024 4,62018

Уже с 30 сторон приходится брать 5 знаков после запятой, чтобы заметить разницу.

Кстати, $k_6=2+\frac 2 3 \sqrt{21}$.

[wrest]

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

Уже с 30 сторон приходится брать 5 знаков после запятой, чтобы заметить разницу.

Ага, вижу. Кстати для круга только 4 знака-то и известно. Да и то: то ли там $4,6033$ то ли $4,6034$
Ну вот моя формула с периметром выглядит, получается, так:
$k(n)=k_0\dfrac{n}{\pi}\tg{\dfrac{\pi}{n}}$, где $k_0\approx 4,6033$ - решение для круга. Ваша как я понимаю к элементарным функциям и $k_0$ не сводится?