Como cubrir tableros

Avatar de Usuario
¿hola?

OFO - Mención-OFO 2016 OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Plata-OFO 2019 OFO - Medalla de Oro-OFO 2020
COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 152
Registrado: Vie 01 Ene, 2016 1:12 am
Medallas: 6
Nivel: 3
Contactar:

Como cubrir tableros

Mensaje sin leer por ¿hola? »

¿Que tableros $M\times N$ se pueden cubrir con piezas $X\times Y$ sin huecos, superposiciones, ni salirse del tablero?

Spoiler: mostrar
Sean $m$ y $n$ los restos en la división por $X$ de $M$ y $N$, vamos a demostrar que, si el tablero se puede cubrir como pide el problema, entonces, $m=0$ o $n=0$. Pintemos el tablero por diagonales con $X$ colores y supongamos que es posible cubrir el tablero como pide el problema.
Como cada pieza de $X\times Y$ al ponerla en tablero ocupa $Y$ casillas de cada color, entonces, el tablero tiene las mismas cantidades de casillas de cada color.

Marquemos un tablerito $m\times n$ en la esquina del tablero $M\times N$, veamos que en las casillas restantes hay las mismas cantidades de casillas de cada color, esto es ya que los rectángulos de $(M-m)\times (N-n), m\times (N-n)$ y $(M-m)\times n$ se pueden cubrir fácilmente con piezas $1\times X$ ya que cada uno tiene por lo menos una dimensión múltiplo de $X$,que son $(M-m), (N-n)$ y $(M-m)$ respectivamente, y como en las piezas de $1\times X$ hay exactamente una casilla de cada color, en todo el tablero menos el tablerito $m\times n$ hay las mismas cantidades de casillas de cada color, y como en el tablero completo también, entonces en el tablerito $m\times n$ hay las mismas cantidades de casillas de cada color.
mn.jpg
Ahora, veremos que en el tablerito $m\times n$ hay las mismas cantidades de casillas de cada color, si y solo si,$m=0$ o $n=0$. Tenemos que $0\leq m,n<X$, por tanto el tablerito $m\times n$ es un subtablero de uno $X\times X$, y al primero lo ubicaremos en una esquina del ultimo (ver dibujo). Fijémonos que hay un color que solo se encuentra en la diagonal principal del tablero $X\times X$, y como en el tablerito $m\times n$ hay las mismas cantidades de casillas de cada color, esta cantidad es igual a la parte que contenga de la diagonal principal, pero es fácil ver que si $m\neq 0$ y $n\neq 0$ hay una casilla de más del color por arriba de la diagonal principal, lo cual es absurdo, por lo que $m=0$ o $n=0$.
color.jpg
Ahora, como $m=0$ o $n=0$ tenemos que una de las dimensiones del tablero es múltiplo de $X$. Análogamente, una de las dimensiones del tablero es múltiplo de $Y$.

Si esas dimensiones son la misma, tendríamos una dimensión múltiplo de $mcm(X,Y)$, para esto, fijémonos que si tomamos una fila de la dimensión restante está solo recorre piezas $X\times Y$ "acostadas" o "paradas", por lo que está dimensión se puede escribir como $aX+bY$ con $a$ y $b$ enteros no negativos, encontrar un ejemplo para este tipo de tableros es sencillo. Luego si esas dimensiones son distintas es mas sencillo aun encontrar un ejemplo.

Finalmente los posibles tableros son los que, o bien, tienen una dimensión múltiplo de $X$ y la otra de $Y$, o bien, tienen una dimensión múltiplo de $mcm(X,Y)$ y la otra dimensión es de la forma $aX+bY$ con $a$ y $b$ enteros no negativos.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
7  
Yes, he who

Responder