teselaciones
Federico Ardila
Universidad de Washington
Seattle WA EEUU
Congreso Nacional de Matem´aticas
Bogot´a, 8 de agosto de 2005
1
Teselaciones
Pregunta: ¿Es posible teselar esta regi´on
usando estas fichas?
1
2
6
5
Federico Ardila
4
3
2
7
Teselaciones
4
5
6
3
2
1
7
1
2
4
3
6
7
5
Respuesta: Es posible, pero no muy interesante.
Federico Ardila
3
TeselacionesEl tablero y las fichas deber´ıan ser interesantes matem´aticamente.
E.g., los 12 pentomin´os teselan un tablero de 3 × 20 o dos de 5 × 6
de una forma esencialmente u
´nica.
´
Esto
es un poco m´as interesante, pero no muy profundo.
Federico Ardila
4
Teselaciones
Definici´
on: Una teselaci´on es una forma de llenar un tablero
con fichas que no se superponen, ni se salen del tablero.
El plan aseguir:
1. ¿Existe una teselaci´on?
2. ¿Cu´antas teselaciones hay?
3. ¿M´as o menos cu´
antas teselaciones hay?
4. ¿C´omo es una teselaci´on “t´ıpica”?
5. ¿Qu´e invariantes algebraicos tiene una teselaci´on?
6. ¿Qu´e tan regular o irregular puede ser una teselaci´on?
7. ¿Qu´e utilidad tiene contestar estas preguntas?
Federico Ardila
5
Teselaciones
1. ¿Existe una teselaci´on?
Una preguntam´as f´acil, pero m´as interesante:
¿Es posible teselar este tablero con 31 domin´os (o d´ımeros)?
Federico Ardila
6
Teselaciones
No es posible.
Coloreemos el tablero como si fuera de ajedrez.
• Cualquier domin´o va a cubrir una casilla blanca y una negra.
• El tablero tiene 32 casillas blancas y 30 negras.
´
Este
es el ejemplo m´as sencillo de un argumento de coloraci´
on.
Federico Ardila
7Teselaciones
Si elimino una casilla blanca y una negra, ¿ser´a posible teselar el
tablero que resulta?
Federico Ardila
8
Teselaciones
S´ı es posible, sin importar cu´ales casillas sean eliminadas.
Federico Ardila
9
Teselaciones
¿Qu´e pasa si elimino dos casillas blancas y dos negras?
A veces es posible, y a veces no.
Pregunta: Si elimino k casillas blancas y k casillas negras,¿cu´ando puedo teselar el tablero con domin´os?
Federico Ardila
10
Teselaciones
Por ejemplo, este tablero tiene 16 casillas blancas y 16 negras, pero
no puede ser teselado con domin´os.
Federico Ardila
11
Teselaciones
Una explicaci´on: Hay un “conjunto deficiente de casillas” - una
especie de cuello de botella.
*
*
*
*
*
Las seis casillas negras con • son adyacentes a un total de s´
olocinco casillas blancas ∗!
Federico Ardila
12
Teselaciones
´
¡Esta
es la u
´nica explicaci´on posible!
Teorema del matrimonio. (Hall, 1935.)
Un tablero puede ser teselado con domin´os si y s´
olo si
no existe un “conjunto de casillas infelices”.
Idea: Hombres y mujeres que s´
olo est´an dispuestos a casarse con
sus vecinos. Para k mujeres necesitamos por lo menos k esposos.
´
Este
es el inicio dela teor´ıa 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´actica.
• Conexiones con optimizaci´
on y teor´ıa de matroides.
Federico Ardila
13
Teselaciones
Es f´acil determinar si es posible teselar una regi´on dada con
domin´os.
¡Pero esta pregunta es muy dif´ıcil paracasi cualquier conjunto de
fichas! Por ejemplo:
Teorema. (Beauquier et al, 1995.)
No existe un algoritmo que decida si un tablero puede
ser teselado con rect´angulos 1 × 3 y 3 × 1.
(Este problema es NP-completo.)
Federico Ardila
14
Teselaciones
2. ¿Cu´antas teselaciones hay?
Un resultado poco interesante:
Teorema. (Un computador, 1965.)
El n´
umero de teselaciones de un rect´angulo de 6 × 10con los 12 pentomin´os es 2339.
El primer resultado interesante:
Teorema. (Kasteleyn, Fisher-Temperley, 1961.)
El n´
umero de teselaciones de un rect´angulo de 2m × 2n
con 2mn domin´os es:
Federico Ardila
15
Teselaciones
El primer resultado interesante:
Teorema. (Kasteleyn, Fisher-Temperley, 1961.)
El n´
umero de teselaciones de un rect´angulo de 2m × 2n
con 2mn domin´os es:
m
4
n
mn...
Regístrate para leer el documento completo.