58-я Международная Математическая Oлимпиада
Бразилия, Рио-де-Жанейро, 2017 год
(i) Қоян, көзге көрінбей, An−1 мен An нүктелер арасында қашықтығы дәл 1 болатындай An деген нүктеге өтеді.
(ii) Бақылау аппараты аңшыға Pn деген нүктені көрсетеді. Мұнда бақылау аппараты Pn мен An нүктелер арасында қашықтығы 1-ден аспайтынын ғана кепіл береді.
(iii) Аңшы, Bn−1 мен Bn нүктелер арасында қашықтығы дәл 1 болатындай, көрінетін бір Bn деген нүктеге өтеді. Қоян қалай жүрсе де және бақылау аппараты қандай нүктелер көрсетсе де, 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) возможно; как только это становится очевидным, метод с двумя точками оказывается практически единственным возможным.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.