Provincial 2018 - Nivel 3 - Problema 1

Avatar de Usuario
Matigelp97

OFO - Medalla de Plata
Mensajes: 34
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 1
Nivel: 1

Provincial 2018 - Nivel 3 - Problema 1

Mensaje sin leer por Matigelp97 » Sab 25 Ago, 2018 4:16 pm

En un tablero de $5$ $X$ $9$ se juega el siguiente juego. Inicialmente se colocan fichas en algunas casillas (ninguna casilla puede tener más de una ficha). Una $movida$ consiste en mover simultáneamente todas las fichas según las siguientes reglas.
$\bullet$ Cada ficha se mueve a una casilla vecina siempre que la casilla de llegada esté vacía al recibir la ficha y que al finalizar la movida en cada casilla haya a los sumo una ficha.
$\bullet$ Si una ficha se movió hacia $\uparrow$ ó $\downarrow$, luego se debe mover hacia $\rightarrow$ ó $\leftarrow$ en la siguiente movida y viceversa.
El juego termina cuando es imposible hacer una movida.
i) Demostrar que si inicialmente hay $33$ fichas el juego terminará.
ii) Demostrar que es posible ubicar $32$ fichas de modo que el juego no termine nunca.
$Nota.$ Dos casillas son vecinas si comparten un lado.

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 753
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Provincial 2018 - Nivel 3 - Problema 1

Mensaje sin leer por Gianni De Rico » Sab 25 Ago, 2018 11:12 pm

i)
Spoiler: mostrar
Pintamos así:
Provincial 2018 N3 P1.png
Notemos que cada $4$ turnos toda ficha debe pasar al menos una vez por una casilla verde, como hay $33$ fichas y $4$ turnos, por Palomar en algún turno hay $9$ fichas en casillas verdes. Nuevamente por Palomar, como hay $9$ fichas y $8$ casillas, entonces hay alguna casilla con $2$ fichas. Luego, el juego termina.
ii)
Spoiler: mostrar
Nos olvidamos de la última fila y la última columna. Nos queda un tablero de $4\times 8$, lo separamos en $8$ subtableros disjuntos de $2\times 2$. En cada subtablero hacemos rotar las fichas en sentido antihorario. Estos movimientos son válidos y cada subtablero de $2\times 2$ puede repetir su movimiento infinitamente. Como los subtableros son disjuntos, el juego no termina nunca.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
[math]

Responder