teselaciones

Páginas: 11 (2522 palabras) Publicado: 22 de octubre de 2015
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

7 Teselaciones

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...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • TESELACIONES
  • Teselaciones
  • Teselados
  • Teselado
  • teselado
  • Teselados
  • teselado
  • Teselaciones

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS