IMO 2017 - P3

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Violeta

OFO - Mención-OFO 2017 FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019
Mensajes: 405
Registrado: Sab 04 Jun, 2016 11:50 pm
Medallas: 5
Ubicación: Puerto Rico

IMO 2017 - P3

Mensaje sin leer por Violeta »

Un conejo invisible y un cazador juegan como sigue en el plano euclídeo. El punto de partida del conejo $A_0$ y el punto de partida del cazador $B_0$ son el mismo. Después de $n-1$ rondas del juego, el conejo se encuentra en el punto $A_{n-1}$ y el cazador en el punto $B_{n-1}$. En la $n$-ésima ronda del juego, ocurren tres hechos en el siguiente orden:

(i) El conejo se mueve de forma invisible a un punto $A_n$ tal que la distancia entre $A_{n-1}$ y $A_n$ es exactamente $1$.

(ii) Un dispositivo de rastreo reporta un punto $P_n$ al cazador. La única información segura que da el dispositivo al cazador es que la distancia entre $P_n$ y $A_n$ es menor o igual a $1$.

(iii) El cazador se mueve de forma visible a un punto $B_n$ tal que la distancia entre $B_{n-1}$ y $B_n$ es exactamente $1$.

¿Es siempre posible que, cualquiera que sea la manera que se mueva el conejo y cualesquiera que sean los puntos que reporte el dispositivo de rastreo, el cazador puede escoger sus movimientos de modo que despues de $10^9$ rondas el cazador pueda garantizar que la distancia entre él mismo y el conejo sea menor o igual a $100$?
Para todo [math], existen [math] primos en sucesión aritmética.
Avatar de Usuario
Prillo

Colaborador-Varias OFO - Jurado-OFO 2015
Mensajes: 401
Registrado: Sab 18 Dic, 2010 8:52 pm
Medallas: 2

Re: IMO 2017 - P3

Mensaje sin leer por Prillo »

Spoiler: mostrar
Lema: Si al comenzar alguna ronda el conejo esta a distancia [math] del cazador, entonces en [math] rondas mas puede garantizarse estar a distancia al menos [math].
IMO2017P3.png
Demostracion: Sin perdida de generalidad el cazador esta en [math] y el conejo en [math]. Consideremos una circunferencia [math] de radio [math] centrada en [math] y una circunferencia unitaria [math] centrada en [math]. [math] y [math] se intersecan en [math] y [math], con [math] en el semiplano inferior y [math] en el semiplano superior. En [math] rondas el conejo puede llegar de [math] a [math] o a [math] yendo en linea recta mientras el dispositivo de rastreo emite en la ronda [math] el punto [math]. Por lo tanto, luego de [math] rondas, el conejo se garantiza estar en [math] o [math] sin que el cazador lo sepa. Supongamos que despues de estas [math] rondas el cazador esta en el punto [math]. Afirmamos que alguna de las distancias [math] o [math] es al menos [math]. Por simetria supongamos sin perdida de generalidad que [math] esta en el semiplano superior. Notemos que [math] esta dentro de la circunferencia [math] centrada en [math] de radio [math]. Sea [math]. Entonces [math] (detalle: esto es mentira si [math]), luego basta ver que [math]. Sea [math]. Entonces [math]. Acotemos [math]. Sea [math] el simetrico de [math] con respecto a [math]. Entonces [math] es semejante a [math] y asi [math]. Entonces (es trivial que) [math]. Por desigualdad triangular concluimos que [math], como queriamos. [math]

Veamos que el conejo puede ganar. Notemos que si el conejo luego de terminar alguna ronda esta a distancia mayor que [math] del cazador gana trivialmente, entonces supongamos lo contrario. En la primer ronda el conejo se asegura estar a distancia [math] del cazador (se toma [math]). De ahi en mas cada [math] rondas el conejo puede aumentar su distancia de [math] a mas de [math]: En efecto, usando el lema, basta ver que [math], que equivale a [math], es decir [math], que vale pues [math] por suposicion. Entonces haciendo estas [math] rondas [math] veces (para un total de [math] rondas), el conejo se garantiza estar a distancia mayor que [math], contradiccion. Entonces gana el conejo.
Mas: Kalman filter
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
4  
Responder