58-я Международная Математическая OлимпиадаБразилия, Рио-де-Жанейро, 2017 год

Охотник и невидимый кролик играют в следующую игру на плоскости. Стартовая точка $A_0$ кролика и стартовая точка $B_0$ охотника совпадают. Пусть после $n-1$ раунда игры кролик находится в точке $A_{n-1}$, а охотник — в точке $B_{n-1}$. Тогда в $n$-ом раунде игры последовательно выполняются следующие три действия:
(i) Кролик, оставаясь невидимым, перемещается в точку $A_n$ такую, что расстояние между $A_{n-1}$ и $A_n$ в точности равно 1.
(ii) Следящее устройство сообщает охотнику некоторую точку $P_n$. При этом следящее устройство гарантирует только то, что расстояние между точками $P_n$ и $A_n$ не больше 1.
(iii) Охотник, оставаясь видимым, перемещается в точку $B_n$ такую, что расстояние между $B_{n-1}$ и $B_n$ в точности равно 1.
Всегда ли возможно охотнику, при любых перемещениях кролика и любых сообщаемых следящим устройством точках, выбирать свои перемещения так, чтобы после $10^9$ раундов он мог гарантировать, что расстояние между ним и кроликом не больше 100?

Комментарий/решение

Слышал что это одна из самых сложных задач за историю IMO. Ответ: да

Давайте дадим фору охотнику. Пусть заяц будет иногда сообщатся ему точное свое местоположения. Пусть расстояние между ними уже что-то в районе 50. Но не именно 50, так как расстояние не обязательно целое. Возьмем его как М. Пусть они сделали х ходов. И мы говорит о том, что заяцу стоит бегать вдоль прямой. Так же как и охотнику, иначе он будет тратить больше времени. Так как их ход ограничен длиной, то по неравенству ломанной, длина начала и конца ломанной не больше длины самое ломаной, что значит охотнику выгоднее ходить по одной прямой, что очевидно, не совпадает с прямой пути зайца, ведь заяц видит охотника. Допустим охотник был в точен Z1, а заяц в точке Z2. Отпустим перепендикуляр на направления пути охотника с точки зайца - допустим Z2T. Пусть они сделали по х ходов,( х>М) значит они прошли по х расстоянию. Рассмотрим треугольник Z2TZ1. Причем очевидно что Z2T=1, так как у волка как мы изначально давало подсказку. Z1Z2=x, тогда Z1T=sqrt(X^2 -1). Допустим изначально они были в точке V1. И пусть охотник перешел затем в V2. Но тогда Z1V2=x-M. Посмотрим на треугольник V2TZ2. V2T=sqrt(x^2-1) -x + M. По теореме пифагора, Z2V2^2=r=(sqrt(x^2-1)-x+M)^2 + 1. Z2V2^2=r - это квадрат расстояние между зайцем и охотником. То есть если мы докажем что через и миллиард ходов r будет 10.000, то мы решили задачу. Раскрыв скобки, собирая подобные, мы получим что r=M^2 +2(x-M)(x-sqrt(x^2-1)). Заметим что x-M>0, и также x - sqrt(x^2-1)>0. Тогда по неравенству треугольник х>=М+1 => х-М>=1. Пусть у=sqrt(x^2 -1). Не сложно заметить x^2-y^2=1. (x-y)(x+y)=1. x-y=1/(x+y). 1/(x+y)>=1/2x, так как x^2>x^2-1, а в свою очередь 1/2x>=1/300, так как х>=101 как минимум.Уже через 300.000.000 он отдалится на 10.000, в свою очередь 10000=100^2. Дальше заяц может ходить по прямой от охотника, что не будет уменьшать расстояние. Раз мы доказали что с подсказкой заяц отдалится от охотника на 100, то без нее и подавно отдалится.

Харош

Это с ютуба решение https://m.youtube.com/watch?v=mgUGHRLN-34&t=1226s

Бро решение 1 в 1 с ютуба скопировал и настолько поленился досмотреть видео, что даже ответ не верен

Пусть $N = 10^9$. Может ли охотник гарантировать, что $A_N B_N < 100$?

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

$\textbf{Утверждение}$-Пусть кролик находится на расстоянии $d \geq 1$ от охотника в некоторый момент времени. Тогда он может увеличить это расстояние как минимум до $\sqrt{d^2 + \frac{1}{2}}$ за $4d$ шагов независимо от того, что охотник уже знает о кролике.

$\textit{Доказательство.}$ Рассмотрим положительное целое число $n > d$, которое будет выбрано позже. Пусть охотник начинает в точке $B$, а кролик в точке $A$, как показано. Обозначим прямую $AB$ через $\ell$.

Теперь мы можем предположить, что кролик раскрывает свою позицию $A$, так что вся предыдущая информация становится несущественной.

Кролик выбирает две точки $X$ и $Y$, симметричные относительно $\ell$, такие что $XY = 2$ и $AX = AY = n$, как показано. Затем кролик может прыгнуть в $X$ или $Y$, передавая сигнал из точки $P_n$ на $\ell$ каждый раз. Это требует $n$ прыжков.

Среди всех точек $H$, куда может переместиться охотник, $\min \max \{HX, HY\}$ очевидно минимизируется при $H \in \ell$ по симметрии. Таким образом, охотник перемещается в точку $H$, такую что $BH = n$. В этом случае новое расстояние равно $HX = HY$.

Мы вычисляем:

$HX^2 = 1 + HM^2 = 1 + \left(\sqrt{AX^2 - 1} - AH\right)^2$

$= 1 + \left(\sqrt{n^2 - 1} - (n - d)\right)^2$

$\geq 1 + \left(\left(n - \frac{1}{n}\right) - (n - d)\right)^2$

$= 1 + (d - \frac{1}{n})^2$

что превосходит $d^2 + \frac{1}{2}$ при $n \geq 4d$.

$\textbf{Замечание.}$ Шаг раскрытия местоположения кролика кажется критическим, поскольку, насколько мне известно, практически невозможно отслеживать местоположения сигналов в данной задаче.

$\textbf{Замечание.}$ Причины полагать, что ответ — «нет»: константа $10^9$, а также то, что «следование за последним сигналом» является проигрышной стратегией для охотника.

$\textbf{Замечание.}$ Я думаю, что есть два способа подойти к этой задаче, когда вы осознаете ответ:

1. Попытаться контролировать местоположение сигналов.

2. Отказаться от идеи контроля возможных местоположений и вместо этого пытаться увеличить расстояние немного, например, от $d$ до $\sqrt{d^2 + \varepsilon}$. Это предполагает раскрытие местоположения кролика перед каждой итерацией нескольких прыжков

Я думаю, что сложность моего подхода заключается в осознании того, что (2) возможно; как только это становится очевидным, метод с двумя точками оказывается практически единственным возможным.

нет вот так будет

$HX^2$=1+HM

Нет…