Simulacro Nacional 2022 Politecnico - Nivel 2 Problema 3

[Fedex]

Un tablero de $n\times n$ está bordeado en todo su perímetro a excepción de la casilla superior derecha, donde tiene la salida en uno de sus lados, y en cada una de las casillas hay una flecha apuntando en cualquiera de las $4$ direcciones (horizontales y verticales). Se coloca una ficha en alguna casilla que se empieza a mover de la siguiente manera: Primero se mueve a la casilla vecina en el sentido que indique la flecha sobre la que está parada, luego la flecha en la nueva casilla pisada rota $90$ grados en sentido horario y la ficha continúa su camino (si la ficha choca contra el borde, queda parada en la misma casilla y la flecha rota nuevamente).
Probar que sin importar la configuración inicial de las flechas ni la posición inicial de la ficha, esta acaba saliendo del tablero.

[Kechi]

Spoiler: mostrar

Supongamos que la ficha nunca sale del tablero. Esto implica que pasa una cantidad limitada de veces por la casilla superior derecha, sino en algún momento su flecha apuntaría en dirección a la salida.

Notemos ahora que si tomamos el último momento por el que pasa la ficha por la casilla superior derecha (podría no pasar nunca) entonces las flechas de sus casillas vecinas (que comparten un lado) no volverán a apuntarla, y como las flechas siempre van rotando se sigue que la ficha también pasa una cantidad limitada de veces por estas casillas. Se puede razonar de la misma manera con las vecinas de las vecinas y así sucesivamente hasta llegar a que la ficha pasa limitadas veces por todas las casillas del tablero, es decir que en algún momento se debe quedar quieta, lo que no es posible.

Concluimos que la ficha siempre termina saliendo del tablero.

[Lean]

Spoiler: mostrar

Si la ficha no sale, tiene infinitos movimientos.

Veamos que esto es imposible:

Para que la ficha no salga esta no puede pasar por la casilla superior derecha (CSD) por más de 4 veces (contando el movimiento que choca contra alguna pared), ya que la flecha rotará hacia la salida en algun punto. Podemos decir ahora que las casillas vecinas son las salidas. Es decir, análogamente, la ficha no debe pasar por las casillas vecinas a ésta por más de 4*4 veces. Lo mismo ocurre para las vecina de las vecinas, las cuales tendrán a lo sumo 4*4*4. Podemos pintar los casilleros del tablero con colores diferentes basandonos en las casillas vecinas a la CSD y a las vecinas de las vecinas a CSD. La cantidad de colores diferentes utilizados en un tablero (n x n) es igual a 2n-1. Por lo tanto, a lo sumo se haran $4^{2n-1}$ - 1 movimientos para que la ficha no salga.

Por lo tanto, la ficha nunca puede hacer infinitos movimientos.