CÓMO RELLENAR CON PIEZAS UN TABLERO
(tetramino corrido)
Tenemos un tablero cuadrado de 9 x 9 = 81 casillas iguales y 20 piezas idénticas de la forma que se muestra en la parte superior de la Fig. 1.
Se trata de ir poniendo piezas en el tablero en cualquier posición, como en un puzzle, con el objetivo final de cubrir el MAYOR número de cuadros posible, o lo que es lo mismo, dejando vacíos el MENOR número de cuadrados posible. Cada cuadrado de la pieza ocupa exactamente un cuadrado del tablero y las piezas no se pueden solapar.
Dividimos el problema en dos cuestiones:
1. Demostrar que NO ES POSIBLE cubrirlo dejando un solo cuadrado libre.
2. ¿Cual es el MENOR número de cuadrados que pueden dejarse VACÍOS en el tablero al recubrirlo con este tipo de piezas?
Nota: Las piezas son reversibles.
COMENTARIOS
Este ejercicio es parte de los conocidos como poliminos que es palabra compuesta de poli (muchos) y mino (terminación de la palabra dominó; se supone que las dos primeras letras do hacen referencia a dos ya que una ficha de dominó está compuesta de dos cuadrados).
El juego consiste, como en el dominó, en adosar unas fichas a otras pero en nuestro caso, para producir teselados (cubrimiento de superficies mediante teselas -mosaicos o cosas similares-).
El término polimino fue acuñado en 1954 por Solomon W. Colomb, recién graduado como matemático en Harvard, y que habría de terminar su carrera como matemático investigador en el laboratorio de propulsión de reactores del Instituto Tecnológico de California. Él definía el polimino como un conjunto de cuadrados pegados unos a otros por uno de sus lados. Después, ese conjunto habría de moverse para rellenar una superficie, por pura traslación, es decir mediante movimientos como los permitidos a la torre del ajedrez.
Los poliminos pueden tener, pues, estas formas:
El monomino consiste en sólo un cuadrado.
El dominó, con sus dos cuadrados es, también, único.
El trimino, con tres cuadrados tiene dos variantes: los tres cuadrados en línea o formando un ángulo recto.
El tetramino puede adoptar 5 configuraciones: los 4 cuadrados en línea; un cuadrado de a cuatro; los cuatro formando una T; formando una L; o dos y dos corridos como el mostrado arriba de la Fig.1.
Sucesivamente se dan los pentaminos, con 12 configuraciones, etc. No se ha encontrado la fórmula que relacione la n de un enemino con la cantidad de configuraciones en que pueda presentarse.
Otra cuestión es la exigencia de las teselaciones: rellenar superficies cuadradas o rectangulares; con relleno completo o a base de configuraciones aisladas de carácter cíclico; empleando todas las configuraciones o solamente alguna o algunas de ellas, etc.
En nuestro caso, y de acuerdo con el enunciado, vamos a manejar un solo tipo de pieza: el tetramino corrido, intentando teselar con él completamente un cuadrado de 9 x 9. Que por otra parte ya se ve por el propio enunciado que es tarea imposible.
En la Fig. 1 se ven las cuatro formas en que podemos colocar la pieza en el tablero. De arriba abajo y de izquierda a derecha:
1-La forma básica.
2-Simétrica de 1 (ésta, dada la vuelta).
3-La 1 girada 90º (en cualquiera de los dos sentidos).
4-La 2 girada 90º (ídem).
SOLUCIÓN
La mejor solución que he encontrado después de diversos tanteos es la de Fig.2.
He utilizado solamente la configuración 1 en cantidad de 16 piezas dejando 17 cuadrados del tablero vacíos (y 81-17=64 llenos). Creo que es la solución óptima aunque deja, como es natural, toda una fila vacía y dos cuadrados por cada una de las 4 ristras de piezas (9+4×2=17).
En un principio pensé que utilizando las cuatro formas de la Fig. 1 obtendría un mejor rendimiento dada la mayor versatilidad, pero llegué a comprobar que no era tal. Con esa versatilidad no logré superar los 17 cuadrados vacíos (Fig.3), pero alcancé el peor resultado con 21 en un par de ocasiones (Fig.4).
Luego vino mi amigo Mariano Nieto con su solución socrática que dice así:
PRIMERA CUESTIÓN
Convirtamos el tablero según la Fig. 5 que muestra la existencia de 45 cuadros rayados y 36 oscuros.
Cualquier pieza de la Fig. 1, colocada adecuadamente sobre cualquier lugar de la Fig. 5 ocupará siempre 2 cuadros rayados y dos oscuros.
Como 36<45, habrá de considerarse la cantidad 36 para ver que 36/2=18 es la cantidad máxima de piezas que podremos colocar sobre el tablero.
O dicho de otro modo: 18 x 4=72 es la mayor cantidad de cuadrados que podemos ocupar (a lo mejor tendremos que ocupar menos). Es decir 81-72=9 es la cantidad mínima (mayor que 1) de cuadros del tablero que tendremos que dejar vacíos.
Notar que 9 es el mcd de 36 y 45.
Fig. 5
SEGUNDA CUESTIÓN
Convirtamos el tablero según la Fig. 6 que muestra la existencia de sólo 16 cuadros oscuros.
Se puede observar que cualquiera que sea la posición en que coloquemos un tetramino sobre el tablero, dicho tetramino ocupa siempre uno y sólo uno de los 16 cuadros oscuros.
Lo que quiere decir que sólo se podrán colocar 16 piezas, es decir, que sólo podremos rellenar 16 x 4=64 cuadros del tablero.
Lo que implica dejar vacíos 81-64=17 cuadros.
Fig.6