Geometría combinatoria+Teoría de los juegos IMO 2017 Problema 3

Question

Un cazador y un conejo invisible juegan una partida en el plano euclidiano. El punto de partida del conejo, $A_0,$ y el punto de partida del cazador, $B_0$ son los mismos. $n-1$ rondas del juego, el conejo está en el punto $A_{n-1}$ y el cazador está en el punto $B_{n-1}.$ En el $n^{\text{th}}$ ronda del juego, ocurren tres cosas en orden:

$\text{1) }$ El conejo se mueve invisiblemente hasta un punto $A_n$ tal que la distancia entre $A_{n-1}$ y $A_n$ es exactamente $1.$

$\text{2) }$ Un dispositivo de seguimiento informa de un punto $P_{n}$ al cazador. La única garantía que ofrece el dispositivo de seguimiento al cazador es que la distancia entre $P_n$ y $A_n$ es como máximo $1.$

$\text{3) }$ El cazador se mueve visiblemente hacia un punto $B_n$ tal que la distancia entre $B_{n-1}$ y $B_{n}$ es exactamente $1.$

¿Es siempre posible, sin importar cómo se mueva el conejo, y sin importar los puntos reportados por el dispositivo de rastreo, que el cazador elija sus movimientos para que después de $10^9$ rondas, puede asegurar que la distancia entre ella y el conejo es como máximo $100?$

Answer 1

Mi intento está esbozado de la siguiente manera.

Tenemos que comprobar si la cazadora puede encontrar una estrategia que le permita permanecer dentro de las 100 unidades después de 109 iteraciones, hagan lo que hagan el conejo y el dispositivo de seguimiento.

Tiene entonces sentido considerar la mejor estrategia posible para el cazador, persiguiendo a un conejo que hace lo mismo, mientras que el dispositivo de seguimiento "ayuda" al conejo tanto como sea posible. Denotemos entonces como $d_{i}$ la distancia entre el conejo y el cazador en el $i$ iteración.

El conejo tratará de maximizar la distancia con el cazador, dando un paso a lo largo de la línea que pasa por él y el cazador.

A continuación, el dispositivo hará lo peor que pueda para el cazador: seleccionará el punto dentro de un círculo de radio 1 centrado en el conejo que minimice la ganancia de distancia a medida que el cazador da pasos (en el esquema de abajo, el cazador está marcado por el punto rojo, el conejo por el azul, y la señal del dispositivo de seguimiento "peor" por el punto verde)

Dicho punto se coloca alrededor de la circunferencia, y es tal que el segmento que lo une al cazador es tangente a la circunferencia.

Si la mejor estrategia para el cazador es moverse hacia la señal dada por el dispositivo de rastreo, moviéndose a lo largo de este segmento tiene la menor proyección a lo largo de la línea cazador-conejo. El ángulo $\alpha$ entre la señal del dispositivo de seguimiento del cazador y la línea del cazador-conejo viene dada por $\alpha = sin^{-1} \frac{1}{d_{i} + 1} $ Estas consideraciones dan lugar a la siguiente fórmula recursiva $$ d_{i+1} = d_{i} + 1 - \sqrt{1- (\frac{1}{d_{i}+1})^2}$$ La secuencia es monotónicamente decreciente y cóncava. Fijamos $d_i = 100$ y verificar que $d_{i+1} – d_{i} \approx 10^-5$ .

Por lo tanto, mi afirmación es que el cazador no alcanzará el objetivo requerido después de $10^9 $ (Ni siquiera sé si la afirmación es correcta, y mucho menos el proceso, pero vale la pena intentarlo).

EDITAR Se ha dejado abierto el punto de si seguir la señal del dispositivo de rastreo es la estrategia óptima para el cazador. Como señaló @seoneo, la información previa podría proporcionar información adicional al cazador. El problema se puede sortear mostrando que existe una estrategia, aunque subóptima, para el conejo, en control del dispositivo de rastreo (esto se puede suponer siguiendo la formulación del problema), suficiente para aumentar la distancia lo suficientemente rápido. El conejo puede elegir moverse sobre una de las líneas punteadas en rojo, y además decidir que se le envíe una señal sobre la línea azul central. Esto es posible hasta que la distancia entre el conejo y la línea azul sea $<1$ . Mientras esta condición se mantenga, el cazador no tiene mejor estrategia que continuar por la línea azul. Una vez que la distancia entre el conejo y la línea azul es $<1$ Si el cazador llegara a conocer la posición del conejo, se podría realizar una nueva iteración, siguiendo la misma estrategia: el cazador va hacia el conejo por la línea azul "actualizada", y éste elige una de las líneas rojas "actualizadas". La trigonometría que he presentado no se ve afectada.