viernes, 3 de junio de 2011

Rellenar con piezas un tablero

Enunciado

Tablero coloreado

Tablero coloreado

Este tipo de problemas de rellenos se pueden solucionar con un método general que se suele denominar como coloraciones. Lo difícil del método es encontrar la coloración adecuada para razonar el problema de una manera sencilla.

Tras tratar problemas más pequeños, podemos encontrar algunos paralelismos en las posiciones de las piezas que usamos, de forma que, si nos fijamos en una trama como la que está expuesta en el dibujo, en la que los cuadros coloreados son los que, partiendo de una esquina, tienen ambas coordenadas pares cumplen la siguiente condición: cualquiera de las piezas que situemos en el tablero tapa siempre uno de los cuadrados coloreados y sólo uno de ellos. Demostrar este hecho es muy sencillo, ya que basta estudiar la paridad de una casilla en general y la de los cuadrados que tapará una de las piezas que situemos allí.

Ahora, trasladando ese coloreado a nuestro tablero 9x9, de forma que la esquina superior izquierda, por ejemplo, tenga ambas coordenadas impares (1, 1) dentro del tablero habrá exactamente 16 cuadrados coloreados (ver imagen adjunta).

Ejemplo de relleno

Ejemplo de relleno

Eso quiere decir que, si situamos las piezas en el interior de ese cuadrado sin solaparse, podremos poner un máximo de 16 piezas, es decir, que a lo sumo taparán 64 cuadrados, puesto que 16*4 = 64, es decir, que quedarán nada menos que 17 cuadrados sin cubrir, y además, si nos fijamos en el coloreado anterior, serán de los blancos.

Faltaría asegurarse de que es posible situar de esa forma las piezas, pero hay muchas formas de colocar esas 16 piezas, en realidad. Adjunto una de ellas. Observa que la intuición nos engaña, ya que aparentemente sobra mucho espacio, y da la impresión de que reubicando las piezas podremos colocar otra, cuando ya sabemos que no es posible.

1 comentario:

viterick@gmail.com dijo...

Excelente! Gracias por el aporte