Processing math: 68%

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


Аңшы және көзге көрінбейтін қоян жазықтықта келесі ойын ойнайды. Қоянның бастапқы нүктесі A0, және аңшының бастапқы нүктесі B0, екеуі бірдей екен. Ойынның n1 раундтан кейін, қоян An1 деген нүктеде түр, ал аңшы Bn1 деген нүктеде түр. Ойынның n-інші раунд кезінде, келесі үш нәрсе ретінде орындалады.
(i) Қоян, көзге көрінбей, An1 мен An нүктелер арасында қашықтығы дәл 1 болатындай An деген нүктеге өтеді.
(ii) Бақылау аппараты аңшыға Pn деген нүктені көрсетеді. Мұнда бақылау аппараты Pn мен An нүктелер арасында қашықтығы 1-ден аспайтынын ғана кепіл береді.
(iii) Аңшы, Bn1 мен Bn нүктелер арасында қашықтығы дәл 1 болатындай, көрінетін бір Bn деген нүктеге өтеді. Қоян қалай жүрсе де және бақылау аппараты қандай нүктелер көрсетсе де, 109 раундтан кейін аңшы мен қоян арасында қашықтығы 100-ден аспайтынына кепіл ету үшін, аңшы қалай жүру керек өзіне әрқашан таңдай ала ма?
посмотреть в олимпиаде

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

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

Слышал что это одна из самых сложных задач за историю 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 месяца 20 дней назад #

Харош

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

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

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

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

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

Пусть 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
5 дней 1 часов назад #

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

HX^2=1+HM

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

Нет…