Algunas preguntas abiertas acerca de los poliominós

Piste bleue Le 21 juin 2013  - Ecrit par  Julien Bernat
Le 25 mars 2019  - Traduit par  Jimena Royo-Letelier, Julio E. De Villegas
Article original : Quelques questions ouvertes sur les polyominos Voir les commentaires
Lire l'article en  
Los problemas de teselación existen desde hace mucho tiempo, y siguen hasta ahora siendo objeto de intensas investigaciones. Querer dar una vuelta por el conjunto de esos problemas es un proyecto muy ambicioso, por lo que -en lo que viene a continuación- el interés será esencialmente presentar ciertas problemáticas y preguntas abiertas que necesitan un mínimo de conocimientos y conducen a los poliominós. Si ese nombre no evoca gran cosa a algunos lectores, despertará sin duda recuerdos a quienes hayan vivido el frenesí que se apoderó del mundo de los videojuegos a fines de los años 80 con Tetris, que sigue hasta el día de hoy como uno de los grandes éxitos planetarios en ese ámbito (según Wikipedia, más de 35 millones de ventas registradas en junio de 2009).

Un poliominó... ¿qué es ?

El constituyente elemental (atómico, dirían los físicos) de nuestro tema es el cuadrado pequeño. También se supone que hay un enorme montón de cuadrados pequeños, todos rigurosamente idénticos.

Un poliominó es una combinación finita de cuadrados pequeños unidos entre ellos, de forma que los lados pegados unos a otros están totalmente en contacto (se puede llamar a esto una regla de combinación). Esta denominación fue propuesta por Solomon Golomb a principio de los años 50 y rápidamente popularizada por Martin Gardner a través de numerosos libros de juegos y rompecabezas matemáticos. A veces se hace la precisión de que un poliominó debe ser simplemente conexo, lo que significa que no debe tener huecos. La mayoría de las veces la distinción no es muy importante, ya que los poliominós agujereados ¡no verifican ninguna de las propiedades correctas que pueden interesarnos !

Se puede escoger las convención de representar un poliominó utilizando un trazo lleno por su borde y un trazo punteado para representar los lados que están unidos. Se utiliza nombres más específicos para los poliominós constituidos por un número dado de cuadrados pequeños : dominó (2 cuadrados pequeños), triminó (3), tetraminó (4), pentaminó (5), etc. Los poliominós están constituidos por un número finito de cuadrados pequeños, pero pueden ser interesantes también combinaciones que contienen una infinidad de cuadrados, que se llamarán superficies (la superficie más grande posible en un plano presentado en forma de cuadrícula).

Un pentaminó

¡Un horror !

Los poliominós tienen la ventaja de poder ser fácilmente manipulados, lo que permite una apropiación rápida para una amplia variedad de problemas destinados al público joven, por ejemplo mediante bloques plásticos de colores ¡que han asegurado el renombre de una famosa firma danesa !

Sin embargo, muchas preguntas que llevan a los poliominós son problemas de existencia (¿se puede encontrar una combinación que satisfaga ciertas condiciones ?) y de numeración (¿cuántas posibilidades de esas hay ?). El estudio de estas preguntas concierne a un campo llamado combinatoria. Entre las preguntas más usuales se puede citar :

— Con un número fijo de cuadrados, ¿cuántos poliominós diferentes se puede constituir ?

— Si se dan dos poliominós P1 y P2 ¿cuántos poliominós P1 hay que utilizar para cubrir completamente al poliominó P2 ? ¿Cuántos poliominós P1 se puede colocar dentro del poliominó P2 sin formar superposición ?

Se puede fundir algunas de estas preguntas en una nueva problemática que corresponde a un caso de optimización : con ejemplares de un poliominó dado ¿se puede teselar (es decir recubrir sin superposición) un poliominó o una superficie dado/a ?

Volveremos parcialmente a esta útima pregunta ¡que es verdaderamente difícil !

Poliominós idénticos, poliominós diferentes

Las preguntas anteriores hacen aparecer nociones de las cuales cada uno puede formarse una idea intuitiva, que sin embargo exige siempre ser precisada : ¿cuándo se puede decir que dos poliominós son idénticos o diferentes ? De hecho, responder a esta pregunta supone que uno conoce las transformaciones que tiene derecho a aplicar a un poliominó dado.

Cada poliominó puede ser visto como un pedazo de una grilla en la cual uno eventualmente habrá determinado un punto especial (su origen). En el marco más general, se autoriza todo movimiento de modo que cada cuadrado pequeño que constituye el poliominó sea trasladado a un cuadrado de esta grilla (¡o que no se mueva !). Ilustremos las posibilidades con el ejemplo siguiente : se ha representado sobre una grilla un primer poliominó en azul. Para que ocupe el lugar rojo, basta con levantar el poliominó azul y desplazarlo sin cambiar su orientación (se le aplica una traslación) ; para el lugar verde eso no será suficiente y habrá que hacerlo girar (se le aplica una rotación) ; para que ocupe el lugar amarillo, obligatoriamente hay que darlo vuelta (se le aplica una simetría axial).

Los movimientos que están autorizados pueden también ser descritos como una combinación de muchos movimientos elementales. Formalmente, se dice que se hace actuar al grupo de las isometrías de la red ℤ² sobre el conjunto de los poliominós.

Dado un poliominó, se llama configuración a todo poliominó obtenido aplicándole un conjunto de movimientos autorizados. Por abuso, generalmente se dice que dos poliominós son idénticos cuando tienen las mismas configuraciones.

Se puede elegir una regla más restrictiva prohibiendo dar vuelta un poliominó. Se habla entonces de desplazamientos (o isometrías positivas). Esta alternativa es menos usual y no será utilizada a continuación.

Poliominós idénticos, ¡pero con una simetría axial incluida !

Jerarquía de Golomb (versión simplificada)

Se dice que un poliominó es :
— rectificable cuando un conjunto de sus configuraciones tesela un rectángulo,
— autoteselante cuando un conjunto de sus configuraciones tesela un agrandamiento de sí mismo,
— teselante cuando un conjunto de sus configuraciones tesela el plano (la grilla) por completo.

Estas propiedades representan solo una pequeña parte del trabajo de clasificación que Golomb realizó sobre los poliominós, según los tipos de superficies que pueden ser teseladas : tiras, tiras acodadas, semi-planos, etc. Nuevas preguntas aparecieron inmediatamente con esas definiciones : ¿cómo probar que un poliominó dado verifica (o no) una de esas propiedades ? ¿Cuál(es) vínculo(s) pueden establecerse entre los diferentes tipos de poliominós ?

La pregunta de saber si un poliominó dado verifica o no una de las propiedades anteriormente introducidas puede resultar de una dificultad temible. Por ejemplo, dejemos al lector la tarea de constituir un rectángulo únicamente con ejemplares del poliominó de la izquierda, o del de la derecha (a pesar de que eso sea posible, no es razonable creer que se pueda lograr contentándose con unir al azar algunas piezas, ¡por lo menos para la mayoría de las personas !).

Llamemos vecinos de tipo 1 a los poliominós que tienen al menos un lado en contacto, y vecinos de tipo 0 a los poliominós que sólo están en contacto por un número finito no nulo de vértices. Beauquier y Nivat mostraron en 1991 que se podía saber si un poliominó dado tesela el plano por traslación. Eso corresponde a verificar si una codificación de su frontera es de una cierta forma. Las dos posibilidades en que ello ocurre son las siguientes : un poliominó así es un seudohexágono (admite 6 vecinos de tipo 1 y ninguno de tipo 0) o un seudocuadrado (con 4 vecinos de tipo 1 y 4 vecinos de tipo 0).

Teselación de tipo seudohexágono : cada poliominó tiene seis vecinos de tipo 1

Nos contentaremos con detallar las dos implicaciones siguientes.

Proposición 1. Todo poliominó rectificable es auto-teselante.

Introduzcamos un mínimo de definiciones antes de proseguir. Cuando $m$ y $n$ son dos enteros naturales, denotamos $R(m,n)$ el rectángulo constituido por $n$ cuadrados según una de las longitudes y $m$ cuadrados según la otra ; se establece del mismo modo la definición del cuadrado $C(n)$ conteniendo $n$ cuadrados por lado.

Ahora pasemos a la prueba. Si un poliominó P tesela el rectángulo $R(m,n)$, entonces uniendo $m$ rectángulos de este tipo, se puede obtener un rectángulo $R(m,m \times n)$. Después se une $n$ copias de este rectángulo para obtener un cuadrado $C(m \times n)$. Finalmente, se reproduce la combinación de pequeños cuadrados que definen el poliominó $P$ pero esta vez usando los cuadrados $C(m \times n)$. De esta forma se obtiene una amplificación del poliominó inicial según un ’’factor’’ $n \times m$.

Ejemplo con el trominó en forma de L

Proposición 2. Todo poliominó autoteselante es teselante.

Comencemos por comentar que cuando un poliominó es autoteselante, el conjunto de factores de agrandamiento posibles es estable por multiplicación. En efecto, si se puede teselar con configuraciones de un poliominó $P$ un agrandamiento $P(n)$ según un factor $n$ así como un agrandamiento $P(m)$ según un factor $m$, entonces utilizando las piezas $P(n)$ en el lugar de las piezas $P$ en la combinación que permite realizar la teselación de $P(m)$, se obtiene un agrandamiento de factor $m \times n$ del poliominó $P$. Así, a todo poliominó autoteselante le corresponde una infinidad de factores de agrandamiento.

Agrandamiento según factores 2, 4, 8, etc.

Se nota entonces que, como se puede encontrar amplificaciones tan grandes como se desee, se puede elegir una de ellas para la cual el poliominó inicial no se encuentre en el borde del agrandamiento, sino que se encuentre completamente rodeado por otras configuraciones para fabricar este agrandamiento. Iterando este argumento, se puede llenar completamente el plano sin tener que modificar las configuraciones ya colocadas.

A la pasada, se comprueba que cuando un conjunto de configuraciones de un poliominó tesela un agrandamiento según un factor n, entonces recubre por entero un cuadrado C(n). Se deduce con el comentario anterior que, dado un poliominó autoteselante, se puede recubrir con algunas de sus configuraciones cuadrados tan grandes como uno quiera. De hecho, profundizando esta idea, se podría demostrar un resultado más fuerte que el que nos interesa aquí : todo poliominó autoteselante puede teselar un cuadrante, es decir el conjunto de cuadrados en una cuadrícula cuyas dos coordenadas son positivas (por ejemplo).

Como acabamos de probar sus implicancias, es legítimo tratar de saber si sus recíprocos son verdaderos o no. Ahora bien, no es difícil encontrar poliominós que teselan el plano pero que no son autoteselantes. Es el caso, por ejemplo, del pentaminó siguiente.

Pentaminó teselante pero no autoteselante

En efecto, una condición necesaria que debe verificar un poliominó rectificable es que, de entre todas sus configuraciones, en al menos una de ellas debe haber un cuadrado pequeño que tenga a la vez la más pequeña abcisa y la más pequeña ordenada entre las coordenadas de todos los cuadrados pequeños que la constituyen. ¡Este no es el caso de ese pentaminó !

Subrayemos que solo se puede constituir dos teselaciones diferentes del plano con este pentaminó. Estas teselaciones son de tipo seudocuadrados y verifican una fuerte propiedad de regularidad : son periódicos en dos direcciones o biperiódicos. Así, para cada uno se puede encontrar dos vectores u y v , de manera que la teselación de la grilla sea realizada por todas las configuraciones obtenidas aplicando al poliominó inicial las traslaciones de la forma n u + m v, donde n y m toman todos los valores enteros.

Dos teselaciones del tipo seudocuadrados

Hay que notar que si un poliominó es teselante, es posible que algunas de sus teselaciones no sean biperiódicas. Para convencerse, basta con constituir una teselación con dominós que se apilan unas sobre otras de la manera más desordenada posible, y luego replicar periódicamente en la otra dirección.
A la pasada, se puede también plantear la pregunta para saber si existe un poliominó teselante con el cual solo se pueda obtener teselaciones no periódicas. El problema con esta pregunta es que nos arrastra al complicado mundo de la indecidibilidad, donde (para hacerlo más simple) se puede enunciar propiedades de las cuales no se sabrá nunca si son satisfechas o no.

Acabamos entonces de resolver el caso del segundo recíproco. Hasta hoy, el primero es todavía una pregunta abierta :

¿Existe un poliominó autoteselante que no es rectificable ?

Coloreabilidad

Volvamos a una pregunta que se había dejado temporalmente de lado : dados dos poliominós P1 y P2, ¿de cuáles criterios se dispone para determinar si es posible o no teselar el poliominó P2 con el poliominó P1 ? Hay muchos casos particulares bien conocidos de esta pregunta. Tal vez el más frecuentemente presentado es el siguiente : determinar si es posible teselar con dominós el cuadrado C(8) al cual se le ha quitado dos esquinas opuestas.

Un primer criterio evidente es una condición necesaria para la realización de un teselado : se necesita que el número de cuadrados pequeños que constituyen el poliominó sea un múltiplo del número de cuadrados pequeños que constituyen el poliominó teselador. El cuociente entre esas dos cantidades representa el número de configuraciones a colocar. Sin embargo, esta condición no basta, ya que no es posible colocar 31 dominós en nuestro cuadrado mutilado. Para probar esto, se utiliza un argumento de coloreabilidad. Si nuestra superficie estuviera coloreada como un tablero de ajedrez, habría 32 cuadrados blancos y 30 cuadrados negros (o al revés). Pero cada vez que uno coloca un dominó sobre esta superficie, este recubre exactamente un casillero blanco y uno negro. Así, se podrá colocar como máximo 30 dominós sobre esta superficie, y quedarán dos cuadrados no recubiertos del mismo color.

Esta idea puede ser formalizada con el fin de probar en un gran número de casos la imposibilidad de realizar la teselación. Para saber si un conjunto de configuraciones del poliominó P1 tesela un poliominó P2, se asocia a cada casillero del poliominó P2 un cierto valor, de manera que cualquiera que sea el lugar donde se coloca una configuración del poliominó P1, la suma de los valores de los casilleros afectados por esta configuración sea constante. Para volver al ejemplo anterior, si se dice que un casillero blanco vale 1 y que uno negro vale -1, entonces todo dominó vale 0. Ahora bien, el cuadrado mutilado vale 2 (o -2), por lo que no se puede teselarlo con los dominós. ¿Puede usted probar que es imposible teselar el cuadrado $C(10)$ con tetraminós en forma de $T$ ? (muchos métodos ligeramente diferentes permiten llegar a ese resultado).

Paso 1

Colorear el cuadrado $C(10)$ como un tablero de damas, alternando casilleros negros y blancos...

Paso 2

... atribuir a cada casillero negro el valor 3 y a cada casillero blanco el valor -1...

Paso 3

... señalar que cada tetraminó recubre 3 casilleros negros y 1 blanco, o 3 casilleros blancos y 1 negro...

Paso 4

... por lo tanto, el valor de cada tetraminó es 3+3+3-1=8 o 3-1-1-1=0...

Paso 5

... como el cuadrado está constituido por 50 casilleros blancos y 50 casilleros negros, la suma de los valores de los casilleros es 100...

Paso 6

... sumando los 0 y los 8, ¿se puede obtener 100 ?

Desgraciadamente (¿o felizmente ??), una vez más esta linda idea no provee más que un criterio. Dicho de otra forma, se puede perfectamente no lograr identificar imposibilidad aparente y entonces no se puede concluir nada. Por ejemplo, se verifica fácilmente que coloreando el hexaminó siguiente se obtendrían tantos casilleros blancos como negros y, pese a esto, no se puede lo teselar con dominós.

Otro inconveniente es que este método no puede ser utilizado para cualquier poliominó. Por ejemplo, no se logra nada interesante con el trominó acodado.
Tratemos de comprender por qué. Para esto, se considera una superficie que contiene un cuadrado $C(2)$. Supongamos que se haya atribuido a cada casillero un cierto valor : uno vale $a$, otro vale $b$, un tercero vale $c$ y el último vale $d$. Colocando nuestro trominó en cualquier lugar, las sumas posibles son $a+b+c, a+b+d, a+c+d $ y $b+c+d$. Ahora bien, si se quiere que esas sumas sean todas iguales, entonces se llega a la relación $a=b=c=d$. Así, no es posible distinguir los casilleros atribuyéndoles valores diferentes.

Esta objeción fue profundizada por Conway y Lagarias, que mostraron que ¡a veces es obligatorio definir objetos matemáticos claramente más sofisticados para tratar de resolver nuestra problemática !

Conclusión y propuestas

Hemos abordado muchas preguntas delicadas a las cuales los matemáticos hasta ahora no saben responder. Además, confrontado a problemas complicados, el primer reflejo es buscar preguntas ¡aún más difíciles ! Pasemos revista a diferentes posibilidades para un dolor de cabeza garantizado (esta lista no es en absoluto exhaustiva) :

  • Existen numerosos problemas con formas distintas a las de los poliominós.
    A veces, las formas son todavía simples, como por ejemplo combinaciones de triángulos equiláteros (polidiamantes, esfinges, etc.) ; uno puede, sin embargo, generalizar el marco presentado aquí ¡con formas bastante más irregulares !
  • Se puede también cambiar la naturaleza de las piezas, aumentando la dimensión del espacio de trabajo. ¿Qué pasa con nuestras preguntas si se reemplaza nuestros cuadrados pequeños por cubos pequeños o por hipercubos pequeños de dimensión 4, 5, 37, n ?
  • Se ha visto que para un poliominó autoteselante, el conjunto S de factores de agrandamiento es un subconjunto de los enteros naturales que es estable por multiplicación. Recíprocamente, si uno se da un conjunto S verificando esta propiedad, ¿se puede encontrar un poliominó autoteselante cuyos factores de agrandamiento sean los elementos de este conjunto ? De manera concreta, ¿qué se puede afirmar si si este conjunto S es el conjunto de números impares, el conjunto de números que están constituidos por el menos dos factores primos, todos los cubos de enteros, todos los enteros salvo 2, etc ? Aquí también uno puede, por supuesto, extender el problema a dimensión superior.
  • No hemos mencionado el orden de un poliominó, definido por Klarner como el número más pequeño de configuraciones que permiten teselar un rectángulo. Gracias a este, se puede concebir nuevas preguntas.
  • En todo lo anterior, solo hemos considerado las teselaciones constituidas por un único tipo de poliominó. Uno también puede interesarse en las teselaciones constituidas por diferentes poliominós, lo que permite plantearse nuevos problemas de decidibilidad. ¡El lector no debiera dudar en consultar los recientes trabajos de Nicolas Ollinger para saber más !

Finalmente, para no dejar al lector completamente frustrado ante tantos asuntos sin resolver, un ejercicio claramente más accesible que las problemáticas antes planteadas : demostrar que para el trominó acodado, todo entero natural es un factor de agrandamiento.

Para saber más

Los lectores que se quedaron con hambre encontrarán con qué saciar su apetito en las siguientes fuentes :

  • J. B. Kelly : Polynomials and Polyominoes. American Mathematical Monthly 76 (1966), 464-471. Ahí se ve cómo definir polinomios, con el de fin de generalizar las demostraciones de colorabilidad.
  • J. Propp : A pedestrian approach to a method of Conway, or, A Tale of Two Cities. Mathematics Magazine, Vol. 70, No 5 (Dec 1997), pp. 327-340. Este artículo se concentra en la teselación de diamantes aztecas con un tetraminó especial.
  • J. H. Conway & J. C. Lagarias : Tiling with polyominoes and combinatorial group theory, Journal of Combinatorial theory, Series A, No 53, 1990, pp. 183-208 ainsi que Thurston : Conway’s tiling groups, The American Mathematical Monthly, Vol. 97, No 8, Special geometry issue (Oct. 1990), pp. 757-773. En esos artículos se encuentran las nociones de coloración generalizada y de invarianza de frontera, con el estudio de tribones como bonita aplicación.
  • ¡la mayoría de los libros de Martin Gardner !
  • los libros Polyominoes : Puzzles, Patterns, Problems, and Packings de Solomon W. Golomb y Polyominoes : A Guide to Puzzles and Problems in Tiling de George E. Martin.

Igualmente se puede encontrar en Internet mucho material sobre nuestro tema. Es más bien ingrato tener que hacer una selección entre todos ellos, ya que numerosos autores tienen páginas muy bien provistas que merecen ampliamente ser consultadas. Una opinión personal (¡con mis disculpas hacia los demás !) es que el sitio de Michael Reid debería ser explorado en primer lugar (tiene algunas soluciones a ciertos problemas expuestos durante la lectura).

Post-scriptum :

La redacción de Paisajes Matemáticos, así como el autor, agradecen por su atenta relectura a Gérard Grancher y a Taladris.

Article original édité par Bruno Martin

Partager cet article

Pour citer cet article :

Julio E. De Villegas, Jimena Royo-Letelier — «Algunas preguntas abiertas acerca de los poliominós» — Images des Mathématiques, CNRS, 2019

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?