Loco

Teselaciones

Federico Ardila
Universidad de Washington Seattle WA EEUU

Congreso Nacional de Matem´ticas a Bogot´, 8 de agosto de 2005 a
1

Teselaciones

Pregunta: ¿Es posible teselar esta regi´n o

usando estas fichas?

1

2

3

4

6 5

7

Federico Ardila

2

Teselaciones

4 5 6 1 7 2

3

1

2

3

4

6 5

7

Respuesta: Es posible, pero no muyinteresante.

Federico Ardila

3

Teselaciones

El tablero y las fichas deber´ ser interesantes matem´ticamente. ıan a

E.g., los 12 pentomin´s teselan un tablero de 3 × 20 o dos de 5 × 6 o

de una forma esencialmente unica. ´ ´ Esto es un poco m´s interesante, pero no muy profundo. a
Federico Ardila 4

Teselaciones

Definici´n: Una teselaci´n es una forma de llenar un tablero o ocon fichas que no se superponen, ni se salen del tablero.

El plan a seguir:
1. ¿Existe una teselaci´n? o 2. ¿Cu´ntas teselaciones hay? a 3. ¿M´s o menos cu´ntas teselaciones hay? a a 4. ¿C´mo es una teselaci´n “t´ o o ıpica”? 5. ¿Qu´ invariantes algebraicos tiene una teselaci´n? e o 6. ¿Qu´ tan regular o irregular puede ser una teselaci´n? e o 7. ¿Qu´ utilidad tiene contestar estas preguntas? eFederico Ardila

5

Teselaciones

1. ¿Existe una teselaci´n? o
Una pregunta m´s f´cil, pero m´s interesante: a a a

¿Es posible teselar este tablero con 31 domin´s (o d´ o ımeros)?

Federico Ardila

6

Teselaciones

No es posible. Coloreemos el tablero como si fuera de ajedrez.

• Cualquier domin´ va a cubrir una casilla blanca y una negra. o • El tablero tiene 32 casillasblancas y 30 negras. ´ Este es el ejemplo m´s sencillo de un argumento de coloraci´n. a o

Federico Ardila

7

Teselaciones

Si elimino una casilla blanca y una negra, ¿ser´ posible teselar el a tablero que resulta?

Federico Ardila

8

Teselaciones

S´ es posible, sin importar cu´les casillas sean eliminadas. ı a

Federico Ardila

9

Teselaciones

¿Qu´ pasa si eliminodos casillas blancas y dos negras? e

A veces es posible, y a veces no. Pregunta: Si elimino k casillas blancas y k casillas negras, ¿cu´ndo puedo teselar el tablero con domin´s? a o

Federico Ardila

10

Teselaciones

Por ejemplo, este tablero tiene 16 casillas blancas y 16 negras, pero no puede ser teselado con domin´s. o

Federico Ardila

11

Teselaciones

Una explicaci´n: Hayun “conjunto deficiente de casillas” - una o especie de cuello de botella.

* * * * *

Las seis casillas negras con • son adyacentes a un total de s´lo o cinco casillas blancas ∗!

Federico Ardila

12

Teselaciones

´ ¡Esta es la unica explicaci´n posible! ´ o Teorema del matrimonio. (Hall, 1935.) Un tablero puede ser teselado con domin´s si y s´lo si o o no existe un “conjunto decasillas infelices”. Idea: Hombres y mujeres que s´lo est´n dispuestos a casarse con o a sus vecinos. Para k mujeres necesitamos por lo menos k esposos. ´ ıa Este es el inicio de la teor´ de emparejamientos. Podemos permitir que cada persona le asigne puntajes a sus posibles parejas, y encontrar el mejor emparejamiento posible. • Muchas aplicaciones en la pr´ctica. a • Conexiones con optimizaci´n yteor´ de matroides. o ıa

Federico Ardila

13

Teselaciones

Es f´cil determinar si es posible teselar una regi´n dada con a o domin´s. o ¡Pero esta pregunta es muy dif´ para casi cualquier conjunto de ıcil fichas! Por ejemplo: Teorema. (Beauquier et al, 1995.) No existe un algoritmo que decida si un tablero puede ser teselado con rect´ngulos 1 × 3 y 3 × 1. a (Este problema es NP-completo.)Federico Ardila

14

Teselaciones

2. ¿Cu´ntas teselaciones hay? a
Un resultado poco interesante: Teorema. (Un computador, 1965.) El n´mero de teselaciones de un rect´ngulo de 6 × 10 u a con los 12 pentomin´s es 2339. o El primer resultado interesante: Teorema. (Kasteleyn, Fisher-Temperley, 1961.) El n´mero de teselaciones de un rect´ngulo de 2m × 2n u a con 2mn domin´s es: o...