Selectivo Cono Sur 2019 - P4

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 915
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Selectivo Cono Sur 2019 - P4

Mensaje sin leer por Gianni De Rico » Vie 29 Mar, 2019 3:16 pm

Un tablero está formado por tres cuadrados de $n\times n$ divididos en casillas de $1\times 1$ que se pegan a lo largo de un segmento de la misma longitud que el lado de cada casilla (ver figura).
Hallar todos los $n\geqslant 1$ para los que el tablero se puede cubrir sin huecos ni superposiciones y sin sobresalir del tablero utilizando piezas de $3\times 1$ o $1\times 3$ con sus casillas de igual tamaño que las del tablero.

Selectivo Cono 2019 P4 Figura.jpg
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
1  
[math]

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 915
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo Cono Sur 2019 - P4

Mensaje sin leer por Gianni De Rico » Vie 29 Mar, 2019 8:36 pm

Spoiler: mostrar
Primero que nada, vemos que si tenemos un tablero de $3\times n$ o $n\times 3$ lo podemos cubrir usando $n$ fichas de $3\times 1$ o de $1\times 3$, entonces podemos pegar $k$ tableros de $3\times n$ o $n\times 3$ y obtener un tablero de $(3k)\times n$ o $n\times (3k)$. De ahora en adelante, si un tablero tiene un lado de longitud múltiplo de $3$, lo cubrimos de esta forma.
Vamos a separar en casos según el resto de $n$ en la división por $3$

Caso $1$: $n\equiv 0\pmod 3$
Spoiler: mostrar
El primer tablero tiene un lado de longitud $n$, que es múltiplo de $3$, entonces lo podemos cubrir (por lo que dijimos antes). De la misma forma, el segundo tablero tiene un lado de longitud $n$, por lo que lo podemos cubrir. Por último, el tercer tablero tiene un lado de longitud $n$, así que también lo podemos cubrir.
Entonces podemos cubrir el tablero para cualquier $n\equiv 0\pmod 3$.

Ejemplo ($n=6$):
Selectivo Cono 2019 P4 n=6.png
Caso $2$: $n\equiv 1\pmod 3$
Spoiler: mostrar
Si $n=1$ entonces todo el tablero es una ficha de $1\times 3$, así que lo cubrimos con esta ficha y listo.
Veamos que pasa para $n>1$.
Miremos el primer tablero. De momento nos olvidamos de la columna de la derecha, entonces nos queda un subtablero de $n\times (n-1)$, y como $n\equiv 1\pmod 3$ tenemos $n-1\equiv 0\pmod 3$, por lo que podemos cubrir este subtablero. Ahora en la columna de la derecha nos olvidamos de la casilla de abajo, nos queda un subtablero de $(n-1)\times 1$, que nuevamente tiene un lado de longitud múltiplo de $3$, así que lo podemos cubrir. En la casilla de abajo a la derecha ponemos una ficha que ocupa las dos casillas de la izquierda de la fila de arriba del tablero del medio.
De forma simétrica, llenamos el tercer tablero. Nos quedan ocupadas las dos casillas de la derecha de la fila de abajo del tablero del medio.
Miremos el tablero del medio. De momento nos quedamos con la columna de la izquierda, y nos olvidamos de la casilla de arriba que ya está ocupada, entonces tenemos un subtablero de $(n-1)\times 1$, que lo podemos cubrir. Hacemos lo mismo con la segunda columna contando desde la izquierda. Para la columna de la derecha, nos olvidamos de la casilla de abajo y nos queda un subtablero de $(n-1)\times 1$, que lo podemos cubrir. Hacemos lo mismo para la penúltima columna contando desde la izquierda. Entonces ya cubrimos las dos columnas de la izquierda y las dos de la derecha, por lo que tenemos que cubrir las $n-4$ columnas del medio, que nos forman un subtablero de $n\times (n-4)$, pero $n\equiv 1\pmod 3\Rightarrow n-4\equiv 0\pmod 3$, luego, podemos cubrir este subtablero, entonces cubrimos todo el tablero.
Entonces podemos cubrir el tablero para cualquier $n\equiv 1\pmod 3$.

Ejemplo ($n=7$):
Selectivo Cono 2019 P4 n=7.png
Caso $3$: $n\equiv 2\pmod 3$
Spoiler: mostrar
Pintamos cada tablero así (en el dibujo $n=5$):
Selectivo Cono 2019 P4 n=5.png
Como $n\equiv 2\pmod 3$ y la casilla de arriba a la izquierda del primer tablero tiene un $1$, las casillas de arriba a la derecha y de abajo a la izquierda del primer tablero tienen un $2$, por lo que la casilla de abajo a la derecha del primer tablero tiene un $3$. Vemos entonces que la cantidad de casillas con un $1$ es la misma en cada tablero ($C_1$), la cantidad de casillas con un $2$ es la misma en cada tablero ($C_2$), y la cantidad de casillas con un $3$ es la misma en cada tablero ($C_3$). Por lo que la cantidad total de casillas de color $1$ en todo el tablero es $3C_1$, la cantidad total de casillas de color $2$ en todo el tablero es $3C_2$, y la cantidad total de casillas de color $3$ en todo el tablero es $3C_3$. Notemos además que cada ficha ocupa exactamente una casilla de cada color (*).
Supongamos que es posible cubrir el tablero, por (*) tenemos que la cantidad total de casillas de cada color es la misma, es decir $3C_1=3C_2=3C_3$, por lo tanto $C_1=C_2=C_3$. Como todas las casillas del primer tablero están pintadas, tenemos que en total tiene $C_1+C_2+C_3=C_1+C_1+C_1=3C_1$ casillas; por otro lado, tiene $n^2$ casillas, por lo tanto $n^2=3C_1$. Ahora, $n\equiv 2\pmod 3\Rightarrow n^2\equiv 1\pmod 3$, además, $3C_1\equiv 0\pmod 3$, luego $1\equiv n^2\equiv 3C_1\equiv 0\pmod 3$. Pero esto es absurdo pues $1\not \equiv 0\pmod 3$. El absurdo proviene de suponer que podemos cubrir el tablero, luego, esto no es posible.
Entonces no podemos cubrir el tablero para ningún $n\equiv 2\pmod 3$.
Por lo tanto, podemos cubrir el tablero si y sólo si $n$ tiene resto $0$ o $1$ en la división por $3$.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
[math]

Responder