Torneo de las ciudades Octubre 2021 Nivel Mayor P2

Problemas que aparecen en el Archivo de Enunciados.
Juaco

OFO - Medalla de Bronce-OFO 2020 OFO - Mención-OFO 2021 OFO - Medalla de Bronce-OFO 2022
Mensajes: 219
Registrado: Jue 10 Oct, 2019 8:24 pm
Medallas: 3
Ubicación: Uruguay

Torneo de las ciudades Octubre 2021 Nivel Mayor P2

Mensaje sin leer por Juaco »

Una torre se ubica en alguna casilla de un tablero de ajedrez de $10×10$. En cada turno se mueve a una casilla adyacente a la que se encuentra y pasó por cada una exactamente una vez.
Demuestre que para cada diagonal principal (la diagonal entre las esquinas del tablero) es cierta la siguiente afirmación: en el camino de la torre hubo dos pasos consecutivos en los que la torre se apartó de la diagonal y luego regresó a la diagonal.

7 PUNTOS
$\text{“The further removed from usefulness or practical application, the more important."}$
Avatar de Usuario
...

OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Mención-FOFO Pascua 2022
Mensajes: 7
Registrado: Vie 01 Oct, 2021 3:35 pm
Medallas: 2

Re: Torneo de las ciudades Octubre 2021 Nivel Mayor P2

Mensaje sin leer por ... »

Capaz falta afinar un poco.
Spoiler: mostrar
Si tenemos dos casillas $A$ y $B$, y la torre pasa de $A$ a $B$, podemos expresar ese turno como $A \to B$. Diremos que tanto $A$ como $B$ están involucradas en ese turno.
Supongamos que la afirmación es incorrecta, e intentemos llegar a un ejemplo. Veamos que es imposible para la diagonal principal negra, que va desde la esquina inferior izquierda a la superior derecha del tablero. Llamemos a las casillas de esta diagonal $C_{1},\ldots, C_{10}$, acorde al orden en que la torre fue pasando por ellas. Además, llamamos a las $18$ casillas de las dos diagonales blancas vecinas a esta diagonal principal $c_1, \ldots, c_{18}$ (también según el orden en que la torre las atravesó). Notemos que cualquier turno que involucre a $C_{k}$, con $1 \leq k \leq 10$ será de la forma $C_{k} \to c_{j}$ o $c_{j} \to C_{k}$, para $1 \leq j \leq 18$. Además, $c_{j}$ solo puede aparecer en un turno que involucre algún $C_{k}$, ya que si aparece en dos significa que salió de la diagonal principal y volvió a entrar en turnos consecutivos (o que pasó por esa casilla dos veces). Como hay $18$ casillas en las diagonales vecinas a la principal, hay un máximo de $18$ turnos que involucran sus casillas. Las casillas $C_2, \ldots, C_9$ forzosamente están involucradas en dos turnos, mientras que $C_{1}$ y $C_{10}$ están involucradas como mínimo en uno. Por lo tanto, la torre debe iniciar su recorrido en $C_{1}$ y finalizarlo en $C_{10}$, ya que sino nos pasamos de los $18$ turnos. Supongamos que este es el caso, y notemos que cuando la torre pasa por las casillas $c_{1},\ldots, c_{18}$ o bien en su anterior turno estaba en la diagonal o bien en su próximo turno lo estará, ya que $c_{1},\ldots, c_{18}$ necesariamente están involucradas en un turno con algún $C_{k}$. Entonces, podemos categorizar estas casillas como casillas salida y casillas entrada. Digamos que la torre comienza en $C_1$ y sale hacia abajo respecto a la diagonal principal. Entonces, ese lado ya tiene una casilla salida. Las casillas salida y entrada se alternan una y una, por lo que la última casilla vecina a la diagonal por la que pase de ese lado también será salida (ya que hay un número impar de casillas vecinas a la diagonal principal en ese lado). Pero si la torre debe terminar sobre la diagonal principal, la casilla vecina a la diagonal principal que atraviese última tiene que ser entrada. Entonces llegamos a un absurdo, y la afirmación se cumple para la diagonal principal negra.
Análogamente, se cumple para la blanca.
Avatar de Usuario
...

OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Mención-FOFO Pascua 2022
Mensajes: 7
Registrado: Vie 01 Oct, 2021 3:35 pm
Medallas: 2

Re: Torneo de las ciudades Octubre 2021 Nivel Mayor P2

Mensaje sin leer por ... »

... escribió: Dom 20 Nov, 2022 8:34 pm Capaz falta afinar un poco.
Spoiler: mostrar
Si tenemos dos casillas $A$ y $B$, y la torre pasa de $A$ a $B$, podemos expresar ese turno como $A \to B$. Diremos que tanto $A$ como $B$ están involucradas en ese turno.
Supongamos que la afirmación es incorrecta, e intentemos llegar a un ejemplo. Veamos que es imposible para la diagonal principal negra, que va desde la esquina inferior izquierda a la superior derecha del tablero. Llamemos a las casillas de esta diagonal $C_{1},\ldots, C_{10}$, acorde al orden en que la torre fue pasando por ellas. Además, llamamos a las $18$ casillas de las dos diagonales blancas vecinas a esta diagonal principal $c_1, \ldots, c_{18}$ (también según el orden en que la torre las atravesó). Notemos que cualquier turno que involucre a $C_{k}$, con $1 \leq k \leq 10$ será de la forma $C_{k} \to c_{j}$ o $c_{j} \to C_{k}$, para $1 \leq j \leq 18$. Además, $c_{j}$ solo puede aparecer en un turno que involucre algún $C_{k}$, ya que si aparece en dos significa que salió de la diagonal principal y volvió a entrar en turnos consecutivos (o que pasó por esa casilla dos veces). Como hay $18$ casillas en las diagonales vecinas a la principal, hay un máximo de $18$ turnos que involucran sus casillas. Las casillas $C_2, \ldots, C_9$ forzosamente están involucradas en dos turnos, mientras que $C_{1}$ y $C_{10}$ están involucradas como mínimo en uno. Por lo tanto, la torre debe iniciar su recorrido en $C_{1}$ y finalizarlo en $C_{10}$, ya que sino nos pasamos de los $18$ turnos. Supongamos que este es el caso, y notemos que cuando la torre pasa por las casillas $c_{1},\ldots, c_{18}$ o bien en su anterior turno estaba en la diagonal o bien en su próximo turno lo estará, ya que $c_{1},\ldots, c_{18}$ necesariamente están involucradas en un turno con algún $C_{k}$. Entonces, podemos categorizar estas casillas como casillas salida y casillas entrada. Digamos que la torre comienza en $C_1$ y sale hacia abajo respecto a la diagonal principal. Entonces, ese lado ya tiene una casilla salida. Las casillas salida y entrada se alternan una y una, por lo que la última casilla vecina a la diagonal por la que pase de ese lado también será salida (ya que hay un número impar de casillas vecinas a la diagonal principal en ese lado). Pero si la torre debe terminar sobre la diagonal principal, la casilla vecina a la diagonal principal que atraviese última tiene que ser entrada. Entonces llegamos a un absurdo, y la afirmación se cumple para la diagonal principal negra.
Análogamente, se cumple para la blanca.
Spoiler: mostrar
Acabo de darme cuenta que la última parte no hace falta, alcanza con ver que la torre siempra va a terminar en una casilla de color distinto a la que empieza, por lo que no puede arrancar y terminar sobre la misma diagonal.
Responder