El conejo invisible y el cazador

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 A_0 del conejo y el punto de partida B_0 del cazador 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:

  1. 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.
  2. 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 que 1.
  3. 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 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 10^9 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.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

17 Comentarios

  1. 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?

    Publica una respuesta
    • 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:

      1. A_1 está a distancia exactamente 1 de A_0.
      2. P_1 está a distancia menor o igual que 1 de A_1.
      3. B_1 está a distancia exactamente 1 de B_0.

      Y así sucesivamente. Pero bueno, igual lo he entendido mal…

      Publica una respuesta
      • 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?

        Publica una respuesta
      • Yo he entendido lo mismo . En la ronda 1 ya dispone del dispositivo de rastreo.

        Publica una respuesta
  2. 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

    Publica una respuesta
  3. 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.

    Publica una respuesta
  4. 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.

    Publica una respuesta
  5. 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 el conejo está más cerca (es decir todo el rato antes de alcanzar los 100), la distancia que se puede alejar el cazador es aún mayor, por lo que suponer de entrada que el conejo ya está a 100, no invalida mi razonamiento.

    Fácil ¿verdad? Pues en realidad lo he hecho más fácil aún, porque para obtener el valor no he supuesto el caso peor para el cazador, sino el que a mi convenía para hacer más sencillos los cálculos (todo lo que sea ponérselo mejor al cazador es válido, porque el resultado real será aún peor para él).

    Edito: Ah!! Se me olvidaba, por supuesto, el cazador no tiene la estrategia que se plantea en el enunciado.

    Publica una respuesta
    • 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.

      Publica una respuesta
    • 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 arcotangente de x para un x pequeño se aproxima por x …
      el seno de x para un x pequeño se aproxima por x…
      el coseno de x para un x se aproxima por 1 o bien 1-x^2/2

      Entonces:
      sqrt((100-cos(arctan(1/100)))^2+sin(arctan(1/100))^2) =~
      =~ sqrt( (100 – cos(1/100))^2 + sin(1/100)^2 )
      =~ sqrt( (100 – 1)^2 + (1/100)^2 )

      sqrt ( 99^2 + 0.0001 ) =~ (99^2 + 0.0001 + 99^2) / (2*99) = 99 + 0.00005/99 > 99 + 0.0000005
      Así que la distancia que aumenta es mayor que 5*10^(-7)

      El único punto que me deja con duda es si la mejor estrategia del cazador es ir en dirección a Pn.
      Por ejemplo, él sabe todos P_i anteriores ¿estamos seguros de que no habría una forma de usar esos P_i anteriores para mejorar la estimación óptima de la dirección donde debe ir?
      La intuición me dice que no… pero a veces la intuición falla y sin una demostración pues me queda la duda.

      Publica una respuesta
      • 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 enseñar la patita cada dos movimientos, de modo que el cazador sepa exactamente donde está, y así podemos suponer la otra mitad como movimientos aislados.

        En este caso, “enseñar la patita” significa que el señuelo indique la posición real del conejo.

        Publica una respuesta
  6. 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 cierta distancia y se produce el movimiento A2. Podemos conceder para más claridad y sin pérdida de generalidad, que incluso conocemos la posición A1. Es perfectamente posible que el sensor nos indique P2 o P2′, pues están a distancia menor que 1 de A2.

    Ahora bien, sea cual sea la estrategia que se haya seguido en el movimiento anterior, usar P2 en nuestra estrategia nos acerca a A2, y usar P2′ en nuestra estrategia nos aleja de A2, eso incluso a pesar de conocer la posición de A1. Por lo tanto hemos de conceder que es posible aumentar la distancia en esta iteración.

    Siguiendo el razonamiento, se puede repetir el esquema en las siguientes iteraciones hasta pasar la distancia 100 unidades.

    QED.

    Corolario:

    Se puede demostrar que tampoco existe estrategia de huida para el conejo. Si el sensor siempre indica sobre él, el cazador puede estar siempre a distancia constante.

    Publica una respuesta
    • 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.

      Publica una respuesta
      • 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 significa que pasadas ciertas iteraciones el cazador va a esta a más de cien.

        – Todo esto previendo el peor de los casos, ya que obviamente el punto P es aleatorio y puede que caiga 10& veces encima exacto del conejo y que pasadas 10& iteraciones el cazador este a 1-2 de distancia –

        Publica una respuesta
        • 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 no estuviese acotado, es posible que no supere 100 en esos pasos… aunque quizá después de muchos pasos más sí que superase 100 ó 1000 o cualquier número.
          Por ejemplo, el logaritmo: El logaritmo decimal de un número siempre crece. Log(10) = 1, Log(100) = 2, Log(10^9) = 9 … Ese logaritmo, llegado a 10^9 es menor que 10 pero si n aumenta mucho puede llegar a ser cualquier número: 100, 1000, etc… Para llegar a 100 necesitaría 10^100 pasos.

          En resumen: que cada vez estés más cerca no implica que llegues… y, al revés, que cada vez estés más lejos no implica que te separes todo lo que quieras.

          Por tanto, tu demostración no es válida.

          Publica una respuesta
          • EDITADO POR EL ADMINISTRADOR

            Por favor, responde con más educación.

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *