58-я Международная Математическая Oлимпиада
Бразилия, Рио-де-Жанейро, 2017 год
(i) Кролик, оставаясь невидимым, перемещается в точку An такую, что расстояние между An−1 и An в точности равно 1.
(ii) Следящее устройство сообщает охотнику некоторую точку Pn. При этом следящее устройство гарантирует только то, что расстояние между точками Pn и An не больше 1.
(iii) Охотник, оставаясь видимым, перемещается в точку Bn такую, что расстояние между Bn−1 и Bn в точности равно 1.
Всегда ли возможно охотнику, при любых перемещениях кролика и любых сообщаемых следящим устройством точках, выбирать свои перемещения так, чтобы после 109 раундов он мог гарантировать, что расстояние между ним и кроликом не больше 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, то без нее и подавно отдалится.
Пусть N=109. Может ли охотник гарантировать, что ANBN<100?
Нет, охотник не может. Мы покажем, как увеличить расстояние следующим образом:
Утверждение-Пусть кролик находится на расстоянии d≥1 от охотника в некоторый момент времени. Тогда он может увеличить это расстояние как минимум до √d2+12 за 4d шагов независимо от того, что охотник уже знает о кролике.
Доказательство. Рассмотрим положительное целое число n>d, которое будет выбрано позже. Пусть охотник начинает в точке B, а кролик в точке A, как показано. Обозначим прямую AB через ℓ.
Теперь мы можем предположить, что кролик раскрывает свою позицию A, так что вся предыдущая информация становится несущественной.
Кролик выбирает две точки X и Y, симметричные относительно ℓ, такие что XY=2 и AX=AY=n, как показано. Затем кролик может прыгнуть в X или Y, передавая сигнал из точки Pn на ℓ каждый раз. Это требует n прыжков.
Среди всех точек H, куда может переместиться охотник, min очевидно минимизируется при 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) возможно; как только это становится очевидным, метод с двумя точками оказывается практически единственным возможным.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.