Geometria

Uno de los más antiguos problemas de combinatoria con el dominó pide determinar de cuántas formas pueden colocarse en hilera todas las fichas de un juego completo (occidental), sometidas a la reglahabitual: que los extremos de piezas en contacto tengan valores iguales. (Una colección se llama completa cuando contiene todos los pares desde el 0-0 hasta el n-n ). El problema es interesante porqueadmite traducción inmediata a un problema de grafos (véase la Figura 59).
Despreciemos el conjunto trivial, que consta sólo de la pieza 0-0, y tomemos el juego completó más sencillo: 0-0, 0-1, 1-1(a). La línea que va de 0 a 1 corresponde a la pieza 0-1. Los círculos indican que cada dígito está emparejado consigo mismo, y representan las piezas dobles del juego. El número de formas en que lastres piezas pueden ser dispuestas en fila es idéntico al número de formas en que el grafo puede ser recorrido mediante un camino continuo que no pase dos veces por una misma línea. Evidentemente, sólohay dos itinerarios así, que difieren únicamente en el sentido de recorrido. Estos dos (0-0, 0-1, 1-1, y su inverso) dan las únicas formas de colocar las piezas en hilera, de forma que los valores delos extremos que se tocan sean iguales.
El problema es menos trivial para el juego de tamaño inmediatamente superior, formado por las seis piezas de 0-0 a 2-2. Su gráfico triangular (b) admite tambiénun sólo recorrido (más el de sentido contrario) pero ahora el camino tiene que cerrarse y retornar al punto de partida, lo que significa que la correspondiente concatenación de dominós es un anillocerrado: 0-0, 0-1, 1-1, 1-2, 2-2, 2-0; imaginemos unidos los dos extremos: 2-0, 0-0. La cadena puede abrirse por seis sitios, formando cada vez una hilera como la pedida, y por tanto hay seissoluciones distintas, ó 12, si se considera que sentidos de recorrido distintos dan hileras distintas.
[pic]
Figura 59. Grafos para resolver el problema de colocar en hilera, un juego completo...