Clara y Raquel dibujadas por Raquel Garcia Ulldemollins
(Clara es la pelirroja)
Francamente, tenía muchas ganas de aparecer por aquí. Tengo que reconocer que nunca antes me había conquistado la Física, a pesar de que algunos físicos no me caen nada mal… Pero quiere la vida que mi hijo mayor, al que llamamos amorosamente el gafotas, haya conseguido que me interese por ella. Y es que según él:
“Las mates molan, pero la Física sirve para hacer muchas más cosas”
Ya saben lo que dicen: cría cuervos…
Al principio creí que se le pasaría, fases de las criaturas, pero desde que el pasado verano me despertara de la siesta para pontificar:
«Los matemáticos siempre presumís de que descubristeis la música pero la música no es más que una vibración y las vibraciones, mamá, son cosa de nosotros, los físicos.»
supe que, de momento, no había vuelta atrás.
Así que cuando Enrique me invitó a escribir una entrada en su blog el día de su segundo aniversario no solo no pude negarme sino que acepté con alegría y entusiasmo. Solo faltaba elegir el tema de la entrada y, claro, eso era fácil: si me lo pide Enrique, voy a hablar de flechazos. Ajá, de esos flechazos.
Hace pocos días tuve el placer de descubrir a una artista española, de Albacete para más señas, en uno de los conciertos gratuitos que, con motivo del día del Orgullo Gay, se celebran en las plazas de Madrid. Fue en la Plaza del Rey. Ella era Rozalén. Y sí, fue un flechazo. Más aún, cuando sonó esta canción:
Me vinieron a la cabeza muchos flechazos, muchos momentos de “te vi y, desde el primer momento, supe que eras ‘pa’ mí”.
Como es este un portal de divulgación científica, de los mejores actualmente en lengua castellana, me limitaré a contar un flechazo científico, dejando para otra ocasión y para mi blog personal, quién sabe, hablar de los de que tiran del ombligo con aleteos de maripositas a las que no nos da la gana cortarle las alas.
El flechazo científico al que me refiero tuvo que ver con este libro y muy especialmente con el primer capítulo del mismo: Polygon triangulation.
Más concretamente, lo que me atrapó en las redes de la, para mí entonces desconocida a pesar de ser ya licenciada en Matemáticas (otro día hablamos de planes de estudio y tal), Geometría Computacional y, en muchos sentidos, modificó mi vida, fue el Problema de la Galería de Arte.
No es la primera vez que hablo de este problema, los que me conocen deben estar cansados de oírlo, pero es que me parece fascinante. Trataré de ser breve, para que no me cierren las puertas de este blog 😉
Imaginemos que tenemos un gato metido en una caja cerrada y queremos saber en todo momento si está vivo o muerto. Sí, sí. Nada de incertidumbres, que a mí las incertidumbres me dan un fatiguita mu rara…
Queremos al gato en todo momento vigilado.
Usaremos cámaras de vigilancia dentro de la caja, en las esquinas de esta. La pregunta es: ¿cuántas cámaras son suficientes para asegurar que el gato está vigilado, se ponga donde se ponga? Si estáis pensando en una caja como un prisma rectangular (lo que viene siendo una caja de zapatos), la respuesta es fácil, ¿no? Con una cámara es suficiente.
Podemos pensar no en la caja completa y el dibujo tridimensional, sino en la base de la caja. Si la caja es un prisma rectangular, la base será un rectángulo.
No es difícil deducir que para vigilar un rectángulo es necesaria y suficiente una única cámara en una de las esquinas, debido a la ausencia de paredes que pudieran impedir la grabación en alguna zona de la caja.
(Nota: Estamos suponiendo que la cámara ve 360º a la redonda y tiene alcance ilimitado)
También, a poco que nos fijemos y juguemos con un lápiz y un papel, llegaremos a la conclusión de que si la base de la caja es un triángulo, un polígono cualquiera de 4 vértices o uno de 5, siempre es suficiente (y necesaria, claro) una sola cámara.
Ya con 6 vértices encontraremos cajas que necesitan 2 cámaras. De hecho, si exploramos los distintos polígonos de 6 vértices posibles, llegaremos a la conclusión de que para cualquier polígono de 6 vértices son suficientes 2 cámaras para vigilarlo. Aunque, no siempre son necesarias 2, como se puede ver en el hexágono regular de la derecha en la siguiente figura.
Podríamos decidir seguir con este estudio añadiendo un vértice cada vez al polígono que da forma a la base de la caja, pero sería tedioso y aburrido…
Así que os propongo un reto: si os digo solamente el número de vértices que tiene la base de la caja, ¿me podéis decir cuántas cámaras son suficientes para vigilarla, sea como sea el polígono de la base? Es broma, ¿eh? No es un problema para resolver en un rato ni mucho menos, de hecho, ese es básicamente el planteamiento del Problema de la Galería de Arte, cambiando la caja por un museo. Fue planteado en 1973 por Victor Klee y la primera respuesta la dio Václav Chvátal en 1975:
si el polígono es simple (no se cortan las aristas entre sí) y tiene N vértices, siempre serán suficientes 
Pues nada, lo que probó Chvátal es que si me dibujas un polígono muy enrevesado, todo lo enrevesado que quieras, con 22 vértices, por ejemplo, siempre serán suficientes 7 cámaras para vigilarlo. Sí, vamos a verlo con el siguiente polígono:
Sin desprestigiar a nuestro amigo Chvátal al que admiro, no voy a usar su demostración para convenceros de que en el polígono del dibujo de arriba son suficientes 7 cámaras para vigilar todo el polígono. No. Voy a usar la demostración que, de este mismo hecho, dio Fisk en 1978. Una demostración bella y cautivadora por su elegancia y sencillez, como todo en la vida en general y en las Matemáticas, en particular. De hecho, la extrema belleza de esta prueba de Fisk le valió que Erdös la señalara como candidata a estar en el Libro de las Demostraciones que, según él, tenía algún dios con las demostraciones más bellas e iba repartiendo a algunas mentes privilegiadas. Nuestro amigo Paul Erdös era más ateo que yo, si se puede. Lo del libro era una metáfora.
Bueno, que me derivo, vamos a repetir los argumentos de la prueba de Fisk para ver que en polígono de 22 vértices que acabamos de dibujar (lo he dibujado yo, pero bueno) son suficientes 7, 
Lo primero que vamos a hacer es triangular el polígono. Para ello, lo que hacemos es añadir todas las diagonales posibles (en amarillo) que sean interiores al polígono, que unan 2 vértices no consecutivos del mismo, y que no crucen a una ya dibujada. Esto es muy apañao además si queréis tener a alguien un rato entretenido dibujando rayitas.
Ahora vamos a colorear los vértices del polígono de tal forma que si 2 vértices están unidos por un segmento (ya sea blanco, de la frontera del polígono; o amarillo, si es una diagonal interior) no pueden estar coloreados con el mismo color. No lo vamos a ver aquí, pero Fisk demuestra en su trabajo que un polígono simple triangulado siempre se puede colorear (siguiendo la regla anterior) usando solo 3 colores. Ea, pues cogemos 3 Alpinos, de nuestros 3 colores favoritos y coloreamos.
Ya lo tenemos. Que sí, que lo tenemos.
Para asegurarnos de vigilar todo el polígono, bastaría con asegurarnos de que vigilamos todos los triángulos de la triangulación del mismo, ¿no? Los triángulos recubren todo el polígono, si todos están vigilados, lo estará también él. En todos los triángulos hay un vértice rojo, uno azul y otro verde. Si ponemos una cámara en cada vértice rojo, por ejemplo, ya hemos terminado. Claro; puesto que en todos los triángulos hay, necesariamente, un vértice rojo, si en cada uno de estos, de los vértices rojos, ponemos una cámara, todos los triángulos estarán vigilados y ¡chim pón!
Pero no las vamos a poner en los vértices rojos, no, porque son 8, y estoy segura de que uno de los colores aparece, como máximo, 7 veces…
¿Que cómo lo sé? Por el Principio del Palomar.
¿Que cuál es el Principio del Palomar? Que si tienes más palomas que palomares, en uno de los palomares tienes que guardar más de una paloma.
¿Que qué tienen que ver las palomas con la vigilancia de gatos bicromáticos? Si tengo que colorear 22 vértices con 3 colores, es como si tuviese que colocar 22 palomas en 3 palomares distintos. En uno de los palomares, como máximo, hay 7 palomas,
¡Anda que no! No pueden tener los 3 palomares 8 palomas o más, que, hasta donde yo sé, eso son 24 palomas como poco.
Efectivamente, si nos fijamos en el dibujo con los vértices coloreados, el color verde aparece 7 veces y también el azul. En este caso, podemos elegir cualquiera de los 2 para ubicar las cámaras, pero, en general, usaremos el color menos popular en la coloración de vértices, el que menos aparezca. Y, de nuevo, por el Principio del Palomar, será menor que
Maravilloso, ¿que no?
Esto es un ejemplo de cómo Fisk demuestra que 
La pregunta ahora es: ¿son siempre necesarias
Entonces, igual podemos mejorar el valor de Fisk, el de 
Pues no. A veces, son necesarias
Este fue el problema por el que, como dije al principio, sentí un flechazo por la Geometría Computacional y me enredé con ella.
En realidad, es una de las versiones más simples de este tipo de problemas, hemos supuesto que, por ejemplo, las cámaras graban 360º a la redonda y tienen alcance ilimitado… Os podéis imaginar, entonces, toda la variante de problemas, ninguno de ellos fáciles de tratar computacionalmente, que se derivan de este si, por ejemplo, limitamos el ángulo de visión de la cámara (pueden ser focos y queremos no vigilar, sino iluminar); o si limitamos el alcance de la misma; si permitimos que las cámaras se muevan; si queremos que cada cámara esté vigilada por otra cámara por motivos de seguridad; si en lugar de cámaras son routers que sí atraviesan paredes pero con restricciones… hay todo un mundo de problemas derivados del Problema de la Galería de Arte y todos son, al menos para mí, preciosos. Si me dejan volver a este blog, podemos explorar alguno de ellos otro día 😉
Ahora toca despedirse.
Felicidades a todos los cuentistas de este blog. Espero que sigáis adelante mucho tiempo y creo que mi gafotas también lo espera. Hacéis algo grande, de verdad.
Muchas gracias por la invitación, Enrique. Ha sido para mí un verdadero honor aparecer por vuestra casa. Y aunque la canción de Rozalén, además de la Galeria de Arte, me recuerda a la primera vez que nos vimos y me dijiste aquel “Hola”, me despido con una de mi Zenet que me evoca a ti, porque con este blog me enseñas a entender el Universo, también.
¡Feliz cumpleaños, Fis!
Mati y Fis dibujados por Raquel para Mati y sus mateaventuras
Cuentos Cuánticos 