La pasada semana se celebró en Río de Janeiro la edición 58 de la Olimpiada Internacional de Matemáticas. En ella, el equipo español ha obtenido tres Medallas de Bronce y dos Menciones Honoríficas (se dan a quienes hacen algún problema bien entero pero no entran en medallas).
Hoy os traigo el problema número 3. Y quiero plantearos este problema porque parece que ha sido especialmente complicado para los chicos y chicas que han competido en esta edición. Tan difícil les ha resultado que solamente dos personas lo han resuelto completamente. De hecho, la mayoría de los participantes han sacado una puntuación de 0 en este problema, algo que no es para nada habitual.
A ver si por aquí somos capaces de resolverlo. Como siempre, espero que nadie haga trampas y busque la solución por internet (seguro que ya está por ahí). Lo interesante es que lo intentemos resolver aquí sin mirar ninguna solución. Bueno, ahí va:
Un conejo invisible y un cazador juegan como sigue en el plano euclídeo. El punto de partida
del conejo y el punto de partida
del cazador son el mismo. Después de
rondas del juego, el conejo se encuentra en el punto
y el cazador en el punto
. En la
-ésima ronda del juego, ocurren tres hechos en el siguiente orden:
- El conejo se mueve de forma invisible a un punto
tal que la distancia entre
- Un dispositivo de rastreo reporta un punto
al cazador. La única información segura que da el dispositivo al cazador es que la distancia entre
- El cazador se mueve de forma visible a un punto
tal que la distancia entre
¿Es siempre posible que, cualquiera que sea la manera en que se mueva el conejo y cualesquiera que sean los puntos que reporte el dispositivo de rastreo, el cazador pueda escoger sus movimientos de modo que después de
rondas el cazador pueda garantizar que la distancia entre él mismo y el conejo sea menor o igual que 100?
Hala, ahí lo dejo. A por él.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Entiendo que en los primeros n-1 movimientos el cazador NO usa el dispositivo de rastreo pero ¿cuánto puede moverse el conejo? ¿Cualquier cantidad?
Lo que yo he entendido es que en cada ronda del juego se cumplen las tres condiciones, o sea que el cazador dispone del dispositivo de rastreo en todas las rondas. Por poner un ejemplo:
Y así sucesivamente. Pero bueno, igual lo he entendido mal…
El enunciado es realmente penoso. Lo que yo he entendido es:
– Cada jugador TIENE QUE moverse en cada turno exactamente una distancia = 1 desde su posición actual.
– El cazador puede usar el dispositivo de rastreo antes de moverse, pero éste tiene un error menor o igual que 1.
Que a simple vista parece lo mismo que ha entendido Miguel Ángel, pero con otras palabras ¿no?
Yo he entendido lo mismo . En la ronda 1 ya dispone del dispositivo de rastreo.
Me encantan las matemáticas y por tanto este blog. Me encantan que se suban problemas de Olimpiadas para mí son un auténtico reto¡¡¡ Enhorabuena por su trabajo
Es un problem dificil, y atractivo.
Sin quitar mérito ni aplausos a los que logran resolverlo (y más con la presión del tiempo), yo me saco el sombrero ante los que idean los problemas de las olimpíadas. Me parece admirable lo que hacen.
https://oeis.org/A004253/a004253.pdf
Une recurrencia infinita de triángulos pitagóricos sencillamente geométricos; para cada triángulo pitagórico.
A mi me sale que en el peor de los casos en el el paso 656617 ya está a 100 unidades de distancia y alejándose, estando este paso muuuy lejos de 10^9.
Yo lo he resuelto, pero me llevo unas 3 horas (a ojo) y usé calculadora, no sé si está permitido usarla en la olimpiada. Mi consuelo es que mi solución es realmente simple (las tres horas se me fueron dando palos de ciego por el camino imposible que seguramente hemos seguido todos). Lo que he hecho es calcular cuanto se puede alejar el cazador del conejo, suponiendo que el conejo está exactamente a 100 de distancia (coincidiréis en que esto es simple). Ahora se dan dos circunstancias: – El valor obtenido es pequeño, pero muchísimo mayor que 100/10^9 – Si… Lee más »
Perdón, no me expliqué bien. Cuando escribí «Lo que he hecho es calcular cuanto se puede alejar el cazador del conejo» quería decir en un sólo movimiento de ambos, cazador y conejo, suponiendo que antes de este movimiento estaban a 100 de distancia.
Si en vez de molestarnos en calcular esa distancia, nos conformamos con una menor, más favorable para el cazador, se puede hacer por semejanza de triángulos y Pitágoras muy fácilmente.
Supongo que lo que haces es: * An está a una distancia de 100 de B_[n-1] * Pn sale a una distancia 1 de An en dirección ortogonal al segmento / vector An B_[n.1] Entonces tienes un triángulo rectángulo, con un ángulo cuya tangente es 1/100 Supones que Bn se dirige a Pn avanzando 1 y calculas la distancia d(Bn, An) = sqrt((100-cos(arctan(1/100)))^2+sin(arctan(1/100))^2) Eso con calculadora sale: 99.0000505013 Entonces, A_[n+1] estaría a una distancia 100.0000505013 y el incremento de distancia en este paso es de más de 5*10^(-5) Que es más que 100/(10^9) = 10^(-7) Sin calculadora: la tangente y… Lee más »
Bien por esa duda. El problema pide que se pruebe si el cazador tiene o no una estrategia que le GARANTICE que estará a menos de 100 unidades de distancia. En un movimiento aislado y sin información previa, no puede hacer otra cosa que no sea seguir el señuelo, porque si no lo hace, no tiene ninguna garantía de que el conejo no se movió, por ejemplo, en un ángulo igual pero al otro lado. Pero como bien dices, esto no son movimientos aislados. Ahora, como el resultado nos da muchísimo margen, el conejo se puede permitir el lujo de… Lee más »
No se puede garantizar una estrategia del cazador para que la distancia no pase de 100 unidades en el número dado de rondas. La demostración es la siguiente: Sea un punto An y Bn separado una distancia cualquiera. Para que la distancia no pase de una cota en un número dado de iteraciones, hace falta ver que no puede aumentar «demasiado» en una iteración cualquiera, pues en dicho caso, se puede repetir el razonamiento m veces y superar la cota M. Pongo un ejemplo para simplificar: https://drive.google.com/file/d/0B5WKRHL3UJJOajJza0RCTGFMb2hFR0lieUxjaHR4dUZHSFA4/view En el dibujo podemos ver una situación posible: A1 y B1 están separados… Lee más »
Pero cuando la distancia que separa la cazador del conejo es bastante grande, digamos 10 o 20, los valores posibles de P estarán cerca del conejo y el cazador al moverse hacia P puede minimizar el aumento.
tanto si esta a 0,1, a 1 ó a un millón la estrategia optima es siempre ir hacia el punto P. Si el punto P cae sobre el punto tangencial de la recta tangente a la circunferencia del margen sobre B (el conejo) que pasa por el punto A (el cazador) siempre va a haber una desviación ya que el conejo suponemos que tiene una huida optima (en dirección opuesta a donde se encuentra el cazador). Así que queda Claro que el cazador jamás va a poder acercarse al conejo y que siempre va a perder algo de distancia. Esto… Lee más »
Si lo único que estás diciendo es que en el caso «peor» el conejo («mejor» para el conejo, «peor» para el cazador) el conejo se aleja un poco en cada paso… Eso no asegura que tras 10^9 iteraciones tenga que estar alejado más de 100 unidades. ¿Por qué? Pues porque hay sucesiones crecientes pero acotadas. Ejemplo: 1, 1+1/2, 1+1/2 + 1/4, 1+1/2+1/8… en cada paso la distancia al 0 crece, está más lejos del 0 pero tras 10^9 pasos o tras 10^1000 pasos o tras todos los pasos que quieras la distancia siempre es menor que 2… Es más, aunque… Lee más »
EDITADO POR EL ADMINISTRADOR
Por favor, responde con más educación.