No te acostarás sin aprender algo más

Hace poco charlaba con un amigo al que quiero un montón y me decía

-Hoy me voy a la cama sin aprender nada nuevo

En ese momento, consciente de que él iba a entender de lo que hablaba y de lo atractivo del problema que le iba a proponer, le pregunté:

-¿Cuántos guardianes son suficientes para vigilar una galería de arte de N paredes?

-¿Ein?

-Supón que la galería de arte viene representada por un polígono simple plano de N lados y que los vigilantes se tienen que situar, forzosamente, en vértices (esquinas) ¿Cuántos vigilantes son suficientes?

En la figura siguiente tenemos representado un posible ejemplo, los lados (paredes de la galería) son los segmentos verdes y los vértices (esquinas) son los puntos de color morado.

Era tarde, él estaba cansado y no era el momento de ponerse a argumentar sobre Geometría Computacional y menos via Gtalk. Le prometí entonces que se lo contaría otro día, adelantándole, para que pudiese ir tranquilo a dormir habiendo aprendido algo, que fuese cuál fuese la forma de la planta de la galería (el polígono) siempre eran suficiente N/3 guardianes en los vértices para vigilar toda la galería. Por mucho que un “malvado” arquitecto diseñara una planta diabólica para nuestro museo.

No olvidé mi promesa, por varias razones, una de ellas porque él me lo recordaba regularmente via Twitter. Pero este fin de semana, estuve en el EBE10 celebrado en Sevilla y conocí a mucha gente a la que estoy segura de que les gustaría conocer este lindo problema y además, todo hay que decirlo, el evento me alteró este gusanito bloguero incipiente en mi estomago. Así que decidí contarlo en este espacio recién estrenado y compartirlo con todos los que pasean alguna vez por aquí.

Eso sí, voy a permitirme abusos del lenguaje y cierta relajación en el rigor matemático con el fin de llegar a todo el mundo. Al final del post, encontraréis la referencia del libro del que extraigo esto, por si a alguien le interesa.

El problema de la Galería de Arte, parafraseando a D. Fernando Pessoa, puede ser tan bello como la Venus de Milo, lo que pasa es que hay menos gente que disfruta de su belleza. Prueba de ello es que  forma parte del Proofs on the Book, un libro maravilloso donde los haya, que recoje, siguiendo una sugerencia del genial matemático Erdos, las demostraciones más bellas de la historia de las Matemáticas. Como dijera el torero, “hay gente pa tó”

Aparte de esa belleza intrínseca al problema, para mí tiene un significado muy importante, tanto a nivel profesional como personal. Cuando yo terminé mis estudios de Matemáticas, fui a buscar a un profesor de la Universidad de Sevilla para pedirle que me dirijiese la tesis en el campo de las Ecuaciones Diferenciales. Quiso el azar que este profesor hubiera salido a desayunar y que una amiga mía me hablara del profesor Alberto Márquez y de su línea de Investigación en Geometría Computacional. Me acerqué al despacho del Dr. Márquez, no tenía nada mejor que hacer y no perdía nada por escucharlo. Él me dio el libro de O'Rourke y me propuso leerme el capitulo dedicado al Problema de la Galería de Arte. Fue tal mi fascinación, que mi tesis doctoral y mi investigación actual están enmarcadas en la Geometría Computacional. 

Ah, y me casé con el Dr. Márquez y tenemos dos hijos maravillosos.

Volviendo al problema. Recordemos que tenemos la galería, como en la figura, y queremos saber cuál es el número suficiente de guardianes para vigilarlo.  No se trata de resolver el problema para cada figura, sino de dar un método para resolverlo sin ver la figura, sólo conociendo el número de vértices (puntos morados) de la misma.

Como así, de golpe, pudiera resultar dificil, vayamos por partes, como Dexter (o como Jack el Destripador como dice el Dr. Márquez que es más mayor).

Si tenemos un triángulo, ¿cuántos guardianes son suficientes?

Muy bien, veo que todos habéis dicho 1, menos el de la última fila que está paveando con su compañera.

¿Y un cuadrilátero?

Efectivamente, uno también. ¿Y con 5?

Uno también. Muy bien, muy bien. ¿Y con 6?

Aquí puede que necesitemos 2. Menos mal, estaban los empleados de seguridad temiendo por sus trabajos.

¿Y para un número N cualquiera?  

Estaréis de acuerdo conmigo en que, como un guardián siempre es suficiente para vigilar un triángulo, si divido la planta de la galería y ponemos un vigilante en cada triángulo, la galería quedaría totalmente vigilada, ¿verdad?

Pero, un momento, como los vamos a situar en los vértices (esquinas) un mismo guardian podría vigilar todos los triángulos que llegaran a él. No necesitamos guardianes distintos para cada triángulo de la división. (Estamos suponiendo que los guardianes tienen un campo de visión de 360º, vamos que se giran de vez en cuando, y que no son miopes, que ven a cualquier distancia, siempre que no haya un muro por medio)

Pues si hacemos esto, ¿cuántos son suficientes? 

Hagamos una cosa. Pintemos los vértices del polígono (de la galería) usando 3 colores diferentes: azul, rojo y amarillo, en un alarde de originalidad. Pero de tal forma, que los lados de los triángulos conecten siempre vértices de distinto color.

Si hacemos esto, cada uno de los triángulos de la división tendrá un vértice de cada uno de estos tres colores. Elegimos uno de esos colores, digamos el rojo, y colocamos un guardián en cada punto rojo. Como todos los triángulos tienen un punto rojo, todos los triángulos tienen un guardián y todos están vigilados. 

¿Fin? No del todo. No escogemos el color así, por afinidades, si no contando el número de vértices de cada uno de los colores y quedándonos con el que menos veces se repita, os recuerdo que aún estamos en crisis.

Entonces, con 3 colores, el que menos se repite, lo hace como mucho N/3 veces. No se pueden repetir los 3 más de N/3 veces, porque si no, ¡sumarían más de N!

Por lo tanto, para galerías de Arte con N esquinas, por muy “malvado” y moderno que haya sido el arquitecto, con N/3 guardianes son suficientes. 

Es chulo, ¿verdad? A mí me encanta. Espero que lo hayáis disfrutado y que mi amigo se haya quedado satisfecho, porque en otro caso, tendré que ir a Barcelona a explicárselo tomándonos una cerveza en algun bar de Gracia. 

Nota: En la demostración de Fisk, se prueba que siempre existe la triangulación del polígono y que siempre se puede colorear con 3 colores.