Segundo Pretorneo 2012 - P1 Juvenil

[Ivan]

Hay un tesoro enterrado en una casilla de un tablero de [math]8\times 8. En cada una de las otras casillas hay enterrado un mensaje que indica el mínimo número de pasos que se necesitan para llegar a la casilla del tesoro. (Se necesita un paso para moverse desde una casilla a una casilla vecina, que es una que tiene un lado ocmún con la casilla de partida.). Determinar el mínimo número de casillas que se deben excavar para llegar con certeza al tesoro.

[benedito2012]

La respuesta es 3. Es facil ver qui com 2 es impossible.

[Prillo]

Te equivocas, con 2 se puede.

[benedito2012]

Incluso con una excavación que se puede llegar a la tesoro, pero no tiene ninguna garantía de que efectivamente llegará. Con tres usted seguro llega

[Prillo]

Identificamos a las casillas del tablero en la forma usual con el par [math](f,c), donde [math]f indica la fila a la que pertenece y [math]c indica la columna a la que pertenece.

Consideremos dos excavaciones, en las casillas [math](1,1) y [math](8,1). Sean [math]a y [math]b las distancias que hallamos al excavar estas casillas. El lugar geométrico de las casillas a distancia mínima [math]a de la casilla [math](1,1) es una escalera formada por las casillas [math](1,a+1),(2,a),(3,a-1),\dots,(a+1,1). De la misma manera, el lugar geométrico de las casillas a distancia mínima [math]b de la casilla [math](1,1) es una escalera formada por las casillas [math](8,b+1),(7,b),(6,b-1),\dots,(8-b,1). El tesoro se encuentra en la única casilla que pertenece simultáneamente a estas dos escaleras (de hecho, es fácil ver que tal casilla es precisamente [math](\frac{a-b+9}{2},\frac{a+b-9}{2}+2)). De esta manera, dos excavaciones son suficientes para encontrara el tesoro, independientemente de la ubicación del tesoro.

Por otra parte, veamos que una excavación no siempre alcanza. Para ello, notemos que toda casilla del tablero tiene al menos dos casillas vecinas. Por lo tanto, si al excavar obtuvíeramos el valor [math]1, sabríamos que el tesoro pertenece a una de las casillas vecinas, pero obviamente no sabríamos con certeza a cuál de ellas. Esto concluye la demostración.

[benedito2012]

Interesante su idea. Pero, para comprender mejor, me imaginaba un tablero donde está el tesoro en la casa (4.6). Pronto, cuando excavó la casa (1.1), encontramos a = 8. ¿En este caso, lo que sería la escalera que va desde (1 + 1) = (1, 8 + 1) hasta (el + 1, 1) = (9, 1), en un 8 por 8 tablero?

[benedito2012]

Corigindo al mensaje anterior:
Interesante su idea. Pero, para comprender mejor, me imaginaba una tabla donde está el tesoro en la casa (4.6). Pronto, cuando excavó la casa (1,1), encontramos a = 8. ¿En este caso, lo que sería la escalera que va desde (1, a + 1) = (1, 8 + 1) hasta (a + 1, 1) = (9, 1), en un 8 por 8 Junta?

[Prillo]

Lo importante es que la escalera que se forma es un subconjunto de dichas casillas. Desde luego que se ignoran aquellas casillas que no interesan. Se sobreentiende que es esto a lo que se refiere la frase "el lugar geométrico (...) es una escalera formada por las casillas (...)".

[benedito2012]

Para aclarar una duda, estoy pensando en el 8 por 8 tablero, donde las filas se numeran de arriba a abajo y las columnas de izquierda a derecha.
Supongamos que el tesoro está en la casa (4, 6).
Por lo que la escalera es de longitud 8 que va desde casa (8, 1) el tesoro se compone de casa: (1, 2), (2, 2), (2, 3), (3, 3), (3, 4), 4 (4), (4, 5), (4, 6).
Ahora, tenga en cuenta que la escalera que va (8, 1) hasta la casa del tesoro (4, 6) es de 9 de longitud y está formado por
(8, 2) , (7, 2), (7, 3), (6, 3), (6, 4), (5, 4), (5, 5), (4, 5) y (4, 6).
Tenga en cuenta que las dos escaleras tiene dos casas en común: (4, 5) y el tesoro, que es (4.6).
¿Cómo decidir dónde está el tesoro?

[Martín Vacas Vignolo]

Otra forma de explicar lo que dice Seba Prillo sería:

Nuestras dos excavaciones son en (1,1) y en (1,8). En cada excavación nos dijeron un número, que es el camino mínimo que hay desde la casilla excavada hasta el tesoro. Dentro de todos los caminos mínimos consideramos, sin pérdida de la generalidad, el camino que realiza primero todos los movimientos horizontales necesarios y luego todos los movimientos verticales necesarios.

Notemos que si el tesoro está en la casilla (i,j), nuestros caminos mínimos considerados serían:

-Desde (1,1) ir hasta (1,j) y desde (1,j) hasta (i,j).

-Desde (1,8) ir hasta (1,j) y desde (1,j) hasta (i,j).

Es claro entonces que los movimientos verticales en ambos caminos son los mismos. Entonces la diferencia entre los dos números que nos digan en las dos excavaciones tiene que estar en los movimientos horizontales. Además, notemos que la suma de los dos movimientos horizontales siempre suman 7.

Entonces tenemos un sistema de 2x2, pues sabemos la suma de los dos números y la resta de esos dos números, que tiene solución única.

Ejemplo: si consideramos que el tesoro está en (4,6)

Cuando excavamos en (1,1) nos dicen que el camino mínimo al tesoro es [math]8.
Cuando excavamos en (1,8) nos dicen que el camino mínimo al tesoro es [math]5.

Entonces lo que me tengo que mover hacia la derecha desde (1,1) más lo que me tengo que mover para la izquierda desde (1,8) es [math]7 por lo que dijimos arriba y además, su diferencia es [math]8-5=3. Entonces tenemos que buscar dos números que sumados den [math]7 y restados den [math]3, y los únicos que cumplen son [math]5 y [math]2. Es decir que desde la casilla (1,1) me tengo que mover [math]5 para la derecha (o sea que termino en (1,6)) y como me quedan [math]3 (porque me habían dicho que ese camino mínimo era de [math]8, me tengo que correr [math]3 para abajo, o sea que termino en (4,6) que es donde efectivamente está el tesoro.