Processing math: 68%

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


Охотник и невидимый кролик играют в следующую игру на плоскости. Стартовая точка A0 кролика и стартовая точка B0 охотника совпадают. Пусть после n1 раунда игры кролик находится в точке An1, а охотник — в точке Bn1. Тогда в n-ом раунде игры последовательно выполняются следующие три действия:
(i) Кролик, оставаясь невидимым, перемещается в точку An такую, что расстояние между An1 и An в точности равно 1.
(ii) Следящее устройство сообщает охотнику некоторую точку Pn. При этом следящее устройство гарантирует только то, что расстояние между точками Pn и An не больше 1.
(iii) Охотник, оставаясь видимым, перемещается в точку Bn такую, что расстояние между Bn1 и Bn в точности равно 1.
Всегда ли возможно охотнику, при любых перемещениях кролика и любых сообщаемых следящим устройством точках, выбирать свои перемещения так, чтобы после 109 раундов он мог гарантировать, что расстояние между ним и кроликом не больше 100?
посмотреть в олимпиаде

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

  1
2 месяца 17 дней назад #

Слышал что это одна из самых сложных задач за историю 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, то без нее и подавно отдалится.

  1
2 месяца 17 дней назад #

Харош

пред. Правка 2   1
2 месяца 11 дней назад #

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

  0
1 месяца 24 дней назад #

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

  1
1 дней 20 часов назад #

Пусть N=109. Может ли охотник гарантировать, что ANBN<100?

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

Утверждение-Пусть кролик находится на расстоянии d1 от охотника в некоторый момент времени. Тогда он может увеличить это расстояние как минимум до 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) возможно; как только это становится очевидным, метод с двумя точками оказывается практически единственным возможным.

  0
1 дней 20 часов назад #

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

HX^2=1+HM

  0
1 дней 19 часов назад #

Нет…