Simulacro Nacional 2022 Politecnico - Nivel 2 Problema 3

Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Jurado-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 269
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 11
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Simulacro Nacional 2022 Politecnico - Nivel 2 Problema 3

Mensaje sin leer por 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.
This homie really did 1 at P6 and dipped.
Avatar de Usuario
Kechi

OFO - Medalla de Bronce-OFO 2023 OFO - Medalla de Plata-OFO 2024
Mensajes: 74
Registrado: Mié 21 Sep, 2022 1:41 pm
Medallas: 2
Nivel: 2

Re: Simulacro Nacional 2022 Politecnico - Nivel 2 Problema 3

Mensaje sin leer por 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.
"La suma de las raíces cuadradas de dos lados de un triángulo isósceles es igual a la raíz cuadrada del lado restante."
Avatar de Usuario
Lean

OFO - Medalla de Bronce-OFO 2023 FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Plata-OFO 2024
Mensajes: 175
Registrado: Vie 20 Ene, 2023 10:38 am
Medallas: 3
Nivel: 3
Ubicación: Quilmes

Re: Simulacro Nacional 2022 Politecnico - Nivel 2 Problema 3

Mensaje sin leer por 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.
"El mejor número es el 73".
Responder