Resultados recientes sobre mosaicos de Penrose

LAGACETA DE LA RSME,Vol. 6.3 (2003), P´ ags. 699–711 699 EL DIABLO DE LOS N ´ UMEROS Secci´on a cargo de Javier Cilleruelo Mateo Resultados recientes sobre mosaicos de Penrose por J. C´aceres, M. E. Geg´undez, M. Maestre, A. M´arquez y A. Moreno-Gonz´alez 1.INTRODUCCI ´ ON En un n´umero anterior de La Gaceta [9] (y en diferente secci´on), algunos de los autores ya presentamos parte de nuestros trabajos sobre mosaicos aperi´odicos. En aquel entonces expon´ıamos un nexo de uni´on entre los mosaicos aperi´odicos y una de las disciplinas de las matem´aticas de mayor auge en los ´ultimos tiempos, la Geometr´ıa Computacional. M´as concretamente, ve´ıamos que una de las herramientas principales de dicha disciplina, Diagramas de Voronoi, permiten generar infinidad de conjuntos de losetas aperi´odicas. En este art´ıculo pretendemos explicar a un nivel m´as divulgativo en qu´e consiste un mosaico aperi´odico y algunas de sus propiedades num´ericas m´as curiosas. La teor´ıa de los mosaicos estudia las diferentes maneras en las cuales una superficie o espacio puede cubrirse mediante copias de unos pocos objetos originales, sin superposiciones ni huecos vac´ıos, intentando al mismo tiempo responder cuestiones acerca de las propiedades de los patrones creados. Actualmente el inter´es por los mosaicos sigue vigente y no s´olo por su uso decorativo sino tambi´en por sus aplicaciones en contextos tan diferentes como la Biolog´ıa [1], la Geograf´ıa [18] y naturalmente, en la Cristalograf´ıa [13]. En la mayor´ıa de estos contextos, el inter´es radica en las reglas que gobiernan los procesos y en las propiedades que determinadas reglas producen en los mosaicos. Como hemos dicho, en este trabajo repasamos algunos de los conceptos b´asicos de la teor´ıa de los mosaicos aperi´odicos. Como una primera idea intuitiva que pronto matizaremos, un mosaico peri´odico es aquel en el que se repite un cierto patr´on y un mosaico aperi´odico es aquel en el que no se repite. En alg´un sentido, de hecho en m´as de uno, los mosaicos peri´odicos juegan el papel 700 ELDIABLO DE LOS N´ UMEROS ττ θ 2 θθ θ6 1 1 ττ 2θ2θ 4θ 11 θ2 θ θ 4 4θθ 2 2 3 3 θ θ θθ 11 Dardo—Cometa Rombos Figura 1: Mosaicos de Penrose de los n´umeros racionales y los mosaicos aperi´odicos el papel de los irracionales. Adem´as abordamos el estudio de la coloraci´on de dos mosaicos muy especiales, los mosaicos de Penrose del “Dardo” y la “Cometa” y el de los Rombos (ver Figura 1) y probamos que ambos tipos de mosaicos son 3–coloreables. Para aquel lector interesado en profundizar un poco m´as sobre la materia, y dado que no vamos a incluir ning´un tipo de detalles ni demostraciones, referencias obligadas en este tema son el texto de Gr¨unbaum y Shepard [11], a un nivel divulgativo, el de Gardner [10] y m´as especializado, el de Senechal [20]. Con respecto a la relaci´on entre mosaicos aperi´odicos y diagramas de Voronoi, adem´as del citado trabajo de la Gaceta [9], se puede consultar el trabajo [8]; y la coloraci´on de mosaicos de Penrose est´a tratada en [6] 2.CONCEPTOS B ´ ASICOS Un mosaico plano es una familia numerable de regiones cerradas denominados losetas oteselas que recubren completamente el plano sin huecos ni superposiciones. De forma m´as expl´ıcita, la uni´on de las losetas cubre todo el plano y sus interiores son disjuntos dos a dos. Sin embargo, esta definici´on es demasiado general. Exigiremos adem´as dos condiciones adicionales con las que eliminaremos los casos indeseados, por triviales, y consideraremos, de esta forma, s´olo el tipo m´as com´un de losetas y los mosaicos que generan. La primera condici´on es que las losetas sean homeomorfas a discos cerrados y la segunda es que s´olo haya un n´umero finito de losetas distintas en un mosaico. Un parche en un mosaico es cualquier conjunto finito de losetas cuya frontera es una curva cerrada simple. Un entorno de un v´ertice en un mosaico es el m´ınimo parche que lo cubre y el conjunto de todos los distintos entornos de los v´ertices de un mosaico es el atlas del mosaico. Observar que si el mosaico est´a generado por un n´umero finito de losetas, el atlas contiene un n´umero finito de entornos. LAGACETA 701 Ya estamos en condiciones de introducir algunos de los conceptos que se manejar´an en esta nota. Decimos que un mosaico es peri´odico si existen dos traslaciones no paralelas que lo deja invariante y no peri´odico en otro caso. Al considerar un conjunto determinado de losetas tenemos tres escenarios posibles en funci´on de los mosaicos que puedan formar: •que todos los mosaicos posibles formados con las losetas sean todos peri´odicos; este es el caso del hexagono regular, que s´olo recubre el plano formando el t´ıpico dibujo de una colmena, •que algunos sean peri´odicos y otros no peri´odicos; como en el caso del cuadrado (ejercicio para el lector: encontrar una teselaci´on no peri´odica por cuadrados), •y por ´ultimo, tambi´en puede ocurrir que con ese conjunto de losetas s´olo se tesele el plano de forma no peri´odica en cuyo caso diremos que el conjunto de losetas es aperi´odico. El inter´es por las losetas aperi´odicas comenz´o hace relativamente poco tiempo; en 1961, H. Wang conjetur´o que no exist´ıan tales losetas [22], pero ya en 1966 Berger [3], descubri´o el primer conjunto aperi´odico con ¡20146 losetas!; n´umero que r´apidamente redujo a 104. Posteriormente, en 1968, Knuth [12] consigui´o un nuevo conjunto de 92 losetas. La reducci´on m´as importante la realiz´o Robinson [19] en 1971, hallando un conjunto con tan s´olo 6 losetas que b´asicamente son cuadrados con modificaciones en sus esquinas. Finalmente entre 1973 y 1974, Roger Penrose descubri´o tres conjuntos aperi´odicos de losetas [15]. El primero de ellos, que denot´o como P1, consta de 6 losetas, que se basan en rombos, pent´agonos regulares y estrellas de cinco puntas con ciertas modificaciones en las aristas, para que no todas encajen bien la una con la otra. Habitualmente las modificaciones en las aristas a las que hemos hecho referencia en el p´arrafo anterior, que obligan a las teselas a unirse de una determinada forma, son sustituidas por ciertas condiciones o reglas combinatorias denominadas reglas de emparejamiento y generalmente se definen mediante etiquetas en los v´ertices y en las aristas, que han de coincidir para que dos aristas puedan identificarse. El segundo conjunto de Penrose, P2, es el m´as conocido de los conjuntos aperi´odicos de losetas y est´a formado por tan s´olo dos losetas, el dardo y la cometa, de la Figura 1, donde θ=π/5rad. yτes la raz´on a´urea. Y por ´ultimo, el conjunto denominado P3que est´a formado por dos tipos de rombos (Figura 1). En la Figura 1 se observan la reglas de emparejamiento a las que hac´ıamos referencia anteriormente, as´ı los v´ertices m´as oscuros s´olo pueden coincidir con otros v´ertices oscuros y los claros con los claros, adem´as, en el caso de los rombos las flechas han de coincidir en su direcci´on. Ambos conjuntos de losetas son interesantes por ser los conjuntos de losetas m´as peque˜nos que 702 ELDIABLO DE LOS N´ UMEROS Figura 2: Sir Roger Penrose se conocen. En lo que sigue, a estas losetas las llamaremos losetas de Penrose y a los mosaicos que generan, mosaicos de Penrose. Los mosaicos de Penrose verifican propiedades muy interesantes, y entre otras veremos aqu´ı algunas de car´acter num´erico y, sobre todo, nos centraremos en la coloraci´on de los mosaicos de Penrose. 3.NUMERABILIDAD, RAZ ´ ON A´ UREA Y OTROS Para fijar ideas, centr´emonos en el ejemplo m´as conocido de mosaicos de Penrose: los generados por el dardo y la cometa (aunque la gran mayor´ıa de lo que vamos a decir tambi´en es v´alido para los otros mosaicos aperi´odicos). La primera de las cuestiones que uno se puede preguntar es cu´antos mosaicos distintos se pueden formar con un dardo y una cometa siguiendo las reglas de emparejamiento a las que hac´ıamos referencia en la secci´on anterior. En principio se podr´ıa pensar que s´olo se puede formar un solo mosaico ya que reglas tan restrictivas parecen determinar la manera de ir colocando las losetaso. Sin embargo, esto no s´olo no es as´ı sino que se pueden formar una cantidad no numerable de mosaicos distintos con nuestras dos losetas. La demostraci´on de este hecho se basa en que todo mosaico de Penrose se puede transformar en otro mosaico aperi´odico siguiendo ciertas reglas de subdivisi´on de losetas y nueva reagrupaci´on. Esta operaci´on es conocida como la composici´on, que en su versi´on m´as simple consiste en la capacidad que tienen algunos mosaicos de unir sus losetas para construir losetas semejantes a las primeras (y con reglas de emparejamiento equivalentes) pero m´as grandes, de forma que se obtiene un conjunto de losetas equivalente al original. En su versi´on m´as compleja se permite dividir las losetas del mosaico original para obtener un segundo conjunto que ser´a al que se le aplicar´a la composici´on LAGACETA 703 simple. Por ´ultimo, las losetas ampliadas se agrupan para obtener un conjunto equivalente al primero. Esta ´ultima versi´on de la operaci´on composici´on es la que se utiliza por ejemplo con el dardo y la cometa (en [11], se puede consultar la construcci´on en detalle). Ambas losetas se dividen por su eje de simetr´ıa obteniendo otro mosaico formado por dos tipos de tri´angulos. Siguiendo las reglas adecuadas y de manera un´ıvoca, ciertos tri´angulos adyacentes se unen para formar versiones ampliadas de s´ı mismos con lo que se obtiene un nuevo mosaico de tri´angulos m´as grandes. Finalmente en este ´ultimo mosaico se pegan las teselas adecuadas para generar nuevos dardos y cometas aumentados. Es conocido que si la operaci´on de composici´on es ´unica, y ´este es el caso de los mosaicos de Penrose, el mosaico es no peri´odico. As´ı, a partir de un mosaico de Penrose determinado T, se puede construir, por medio de la composici´on, otro T1y as´ı sucesivamente (ver [11] para una descripci´on m´as precisa de estos nuevos mosaicos). Cada uno de estos mosaicos no son exactamente mosaicos de dardos y cometas (ya hemos dicho que en los pasos intermedios son tri´angulos), pero comparten algunas de su propiedades, en concreto, siempre est´an formados por dos tipos de losetas una grande y una peque˜na. De este modo podemos asignar a cada par (P, T) donde Pes un punto del plano y Tun mosaico de Penrose, una sucesi´on {ai}de ceros y unos de la siguiente forma: a partir de Tconstruimos la sucesi´on Tiy entonces aj ser´a cero si Ppertenece a una loseta peque˜na de Tjy ser´a uno si est´a en una loseta grande. Se pueden probar dos hechos importantes: 1. Cualquier sucesi´on de ceros y unos que no contenga dos unos consecutivos es la sucesi´on asignada a un cierto par (P, T). 2. Las sucesiones de dos puntos distintos del mismo mosaico difieren s´olo en una cantidad finita de t´erminos (llega un momento en el que los dos puntos caen en la misma loseta). A partir de estos dos resultado se concluye que existe una cantidad no numerable de mosaicos de Penrose. Aunque acabamos de decir que existe una cantidad no numerable de Mosaicos de Penrose distintos entre s´ı, una propiedad muy curiosa es que dichos mosaicos, en realidad, se parecen mucho. Cualquier trozo finito de ellos se repite infinitamente en cualquiera de los restantes mosaicos y, por lo tanto, localmente son indistiguibles uno de otros. Cuando vemos una porci´on de un mosaico de Penrose (y los autores de este trabajo es todo cuanto han visto hasta el momento) no sabemos en qu´e mosaico nos encontramos. Esta propiedad se denomina isomorfismo local. En general podemos decir que localmente los mosaicos de Penrose tienen una estructura muy regular pero bastante irregular a nivel global. Otra cuesti´on curiosa es que muchos de los primeros mosaicos aperi´odicos encontrados originalmente presentaban de alguna u otra forma una relaci´on 704 ELDIABLO DE LOS N´ UMEROS con la raz´on a´urea. Ello est´a relacionado con la simetr´ıa pentagonal que presentaban estos mosaicos. Por ejemplo, puede verse que en el dardo o la cometa un par de lados tiene esa longitud. 4.3–COLORACI ´ ON DE LOS MOSAICOS DE PENROSE: DARDO–COMETA YROMBOS En esta secci´on nos proponemos estudiar la coloraci´on de los mosaicos de Penrose. Aunque el problema de la coloraci´on de mapas es bien conocido (cualquier mapa plano admite una coloraci´on con cuatro colores de tal forma que dos regiones lim´ıtrofes tienen asignados colores distintos), su relaci´on con otros muchos problemas (de asignaci´on de tareas, de clasificaci´on u otros m´as algebraicos) lo hace hoy en d´ıa casi m´as actual que cuando Appel y Hanken dieron su demostraci´on del teorema de los cuatro colores en 1976. El problema de colorear mosaicos aperi´odicos consiste en determinar cu´antos colores se necesitan para colorear las teselas de un mosaico de modo que cualesquiera dos losetas adyacentes tengan colores distintos; donde dos losetas son adyacentes si comparten un lado completo. Obviamente, si fuera posible, dado un mosaico Tnos gustar´ıa conocer una coloraci´on del mismo o un procedimiento que lo colorease. La coloraci´on de mosaicos aperi´odicos es un problema que ha atra´ıdo la atenci´on de los investigadores en los ´ultimos a˜nos (ver [16]). Concretamente el n´umero de colores necesarios para colorear los Rombos de Penrose fue resuelto por T. Sibley y S. Wagon en [21] dando un resultado general para todos los conjuntos formados por cuadril´ateros. Nosotros presentamos aqu´ı, muy sucintamente, un m´etodo unificado tanto para los rombos como para los dardos y cometas que, adem´as puede ser utilizado para otros tipo de mosaicos aperi´odicos. Tal y como se ha comentado en la secci´on anterior, dos de las propiedades m´as importantes de la inmensa mayor´ıa de los mosaicos aperi´odicos son la propiedad del isomorfismo local para los mosaicos generados por un mismo conjunto y la propiedad de composici´on–descomposici´on para las losetas de un conjunto de losetas (ver [11]). La propiedad del isomorfismo local junto con un conocido resultado de N.G. de Bruijn y P. Erd¨os [5] sirve para probar que basta con ver la 3– coloraci´on de un mosaico de Penrose para inferir la 3–coloraci´on de todos los mosaicos de Penrose usando las mismas losetas. Efectivamente, el resultado de N.G. de Bruijn y P. Erd¨os dice que es equivalente probar que un grafo infinito es n–coloreable a que cualquier subgrafo finito suyo lo sea. As´ı si sabemos que un mosaico de Penrose concreto es 3–coloreable, entonces todo submosaico suyo finito lo es. Por otra parte, por la propiedad del isomorfismo local, los submosaicos finitos son comunes a todos los mosaicos de Penrose del mismo tipo, y s´olo nos queda aludir al teorema de N.G. Bruijn y P. Erd¨os para concluir que todos mosaico del mismo tipo es 3–coloreable. LAGACETA 705 Figura 3: Composici´on de dardos y cometas Algunos de los autores de este trabajo han usado las propiedades b´asicas de la composici´on para demostrar que los mosaicos de Penrose con dardos y cometas y con rombos pueden ser coloreados utilizando s´olo tres colores. Como veremos, el problema de la 3–coloraci´on lo resolveremos subdividiendo los mosaicos de Penrose en una cantidad numerable de parches donde cada parche es una copia isom´etrica de un elemento de un conjunto finito de parches legalmente coloreados. Inicialmente nos vamos a concentrar en la subdivisi´on del mosaico en un conjunto finito de tipos de regiones acotadas. Sea Tun mosaico con un conjunto finito de losetas. Consideremos Tcon las losetas decoradas con un conjunto de l´ıneas de Jordan, denominadas J–l´ıneas b´asicas, de la siguiente forma: •Para cada v´ertice de las losetas existe una J–l´ınea b´asica separ´andolo del resto de v´ertices de la loseta. •Las J–l´ıneas b´asicas de v´ertices consecutivos uyvde una loseta deben llegar unidas a la arista uv de la loseta; i.e. debe haber un ´unico punto de contacto de las J–l´ıneas b´asicas sobre la arista uv. •Para cada v´ertice del mosaico las J–l´ıneas b´asicas deben coincidir, esto es, continuar entre una loseta y la adyacente sobre las aristas del mosaico. Obviamente cualquier mosaico puede decorarse con J–l´ıneas b´asicas; para hacerlo es suficiente con elegir un punto en el interior de cada loseta y unirlo mediante una curva de Jordan con los puntos medios de los lados de la loseta. La raz´on principal para introducir las J–l´ıneas b´asicas es que las J–l´ıneas b´asicas sobre un mosaico subdividen el plano en regiones acotadas de una cantidad finita de tipos distintos; a lo sumo una regi´on por cada elemento en el atlas del mosaico. Partiendo de las J–l´ıneas b´asicas (nivel 0) sobre el dardo y la cometa, vamos a definir las J–l´ıneas de nivel i( que no son propiamente l´ıneas, sino conjuntos de losetas ) inductivamente de la siguiente forma: pasaremos de un mosaico de un nivel a otro superior mediante la operaci´on de descomposici´on 706 ELDIABLO DE LOS N´ UMEROS Figura 4: J–l´ıneas b´asicas en el dardo y la cometa Figura 5: L´ıneas sobre los 7 entornos de Penrose (la operaci´on inversa de la composici´on comentada anteriormente). Las J– l´ıneas de nivel 1 ser´an todas las losetas del mosaico de nivel 1 que contienen alg´un punto de las J–l´ıneas b´asicas y, en general, las J–l´ıneas de nivel iser´an todas las losetas necesarias para tapar las J–l´ıneas de nivel i−1. As´ı en cada nivel, fuera de las J–l´ıneas nos quedan s´olo una cantidad finita de tipos distintos de parches. Por lo tanto, si en un nivel dado somos capaces de 3–colorear legalmente todas las losetas de las J–l´ıneas y los parches que componen su complementario, habremos conseguido dar una 3–coloraci´on de un mosaico de Penrose y, por lo comentado anteriormente, habremos probado que todos los mosaicos de Penrose con sus mismas losetas se pueden 3–colorear. 4.1 MOSAICOS DE PENROSE: DARDO–COMETA Sobre cada dardo y cometa de cualquier mosaico consideramos unas l´ıneas como las l´ıneas gruesas de la Figura 4; teniendo en cuenta que las intersecciones LAGACETA 707 Figura 6: Regiones sobre el plano de Penrose de las l´ıneas con los lados de las losetas deben coincidir en la frontera del dardo y de la cometa. Si generamos el atlas del mosaico de Penrose con estas losetas decoradas, obtenemos 7 tipos de entornos (Figura 5) de los v´ertices que nos divide el plano, como se puede observar en la Figura 6. Ahora la estrategia est´a clara. Llegar a un nivel apropiado de complejidad (nivel 6 en este caso) para poder colorear legalmente las J–l´ıneas de dicho nivel de tal manera que se puedan pegar bien, y para poder colorear legalmente las partes complementarias (entornos de los v´ertices originales no cubiertos por las J–l´ıneas), evitando incompatibilidades con las J–l´ıneas. Y podemos probar el siguiente resultado: TEOREMA Los mosaicos de Penrose con dardos y cometas se pueden colorear con s´olo 3 colores 4.2 MOSAICOS DE PENROSE: ROMBOS Al igual que en el caso anterior sobre cada rombo de cualquier mosaico consideramos unas l´ıneas como las l´ıneas gruesas de la Figura 8; teniendo en cuenta que las intersecciones de las l´ıneas con los lados de las losetas coinciden en los rombos. Si generamos el atlas del mosaico de Penrose con estas nuevas losetas, obtenemos una regi´on acotada por cada uno de los 8 entornos de los v´ertices excepto en los tres primeros casos (ver Figura 9). Pero en esos casos, debido a las reglas de emparejamiento, las posibles configuraciones que se forman son solamente dos ya que tanto el primer como el segundo entorno han de unirse con el tercer. Por tanto, cualquier mosaico de Penrose con estas nuevas losetas, al igual que en el caso anterior, nos divide el plano en exactamente 7 tipos de regiones distintas.