Entradas etiquetadas como ‘Erdős’

¿Cuántos nos están vigilando?

La semana pasada la terminamos con una noticia tan gratificante como ésta. Y una se plantea ¿quién está decidiendo nuestros destinos? ¿Quién está dibujando el futuro de nuestras familias? ¿Cuántos nos están vigilando? Y porque sospecho, digo sospecho, que también nos vigilan desde ese polígono de 5 vértices, el Pentágono, se me ha venido a la cabeza uno de mis problemas favoritos de Geometría Computacional que mezcla esos dos conceptos, vigilancia y polígonos: El problema de la Galería de Arte.  Aparte de la belleza intrínseca de este problema, de la que intentaré convenceros a lo largo de esta entrada, mi debilidad por él tiene un origen romántico: fue el primer problema de esta disciplina que leí y que me atrapó en las redes de esta forma de hacer Matemáticas.

¿Cuál es el Problema de la Galeria de Arte?

El problema fue planteado por Victor Klee  en 1973, pero antes de plantearlo, dejadme que demos algunas nociones muy sencillitas. Vamos a hablar de galerías de artes, museos, que tenemos que vigilar para que nadie toque ni se lleve nada. Pues bien, para nosotros, en esta versión del problema que vamos a contar (hay muchísimas variantes), la galería que queremos vigilar estará representado por un polígono simple, y cuando decimos simple lo que queremos decir es que los lados de nuestro polígono no se cortan entre ellos, voy a hacer un dibujo por si se ve más claro.

Seguimos.  Cuando decimos que queremos vigilar la galería de arte, lo que queremos es decidir dónde colocaremos a los vigilantes en el polígono que representa a la galería con el fin de que toda ella quede cubierta por la mirada de éstos. En esta primera versión del problema, los vigilantes tienen que estar situados en los vértices (esquinas) del polígono, fijos, no se pueden mover. Tienen visión de 360ª y no son miopes, es decir, pueden ver a cualquier distancia, siempre que no haya una pared que se lo impida. A ver, voy a hacer otro dibujo por aquello de que  una imagen….

En la imagen superior, hemos situado un vigilante en un vértice del polígono y hemos sombreado la zona que sería cubierta por éste, sin moverse, suponiendo que puede ver a cualquier distancia y 360º a la redonda.  Con estas restricciones, ya podemos plantear la pregunta que planteó Klee:

Dado un polígono con N vértices ¿cuántos vigilantes son siempre suficientes para vigilar todo el polígono?

Ahora bien, el problema que plantea Klee no es que nos dan un polígono, dibujado, con N vértices y que nosotros coloquemos el menor número de vigilantes para ese polígono en concreto. Lo que plantea Klee es que demos una fórmula o relación, de forma que podamos saber para un número de vértices N cualquiera, cuántos guardianes serán suficientes para vigilar esa galería, sin saber siquiera qué forma tiene la galería,  sólo a partir del numero de vértices que tiene el polígono que representa la planta del  museo. Pero, ¿eso como va a ser? La forma del polígono tiene mucho que ver, de hecho puede haber polígonos con muchos vértices que se vigilen con un sólo vigilante y otros que con muchos menos necesiten más de uno… Otro dibujo nos vendrá bien.

En el dibujo anterior, tenemos una galería con 13 vértices que puede ser vigilada por un sólo guardián y otra con 6 vértices, que va a necesitar 2. Entonces, ¿cómo vamos poder dar un número en función del número de vértices? Si pensamos en un hexágono regular, podemos entender que será vigilado con 1 sólo vigilante, y el polígono de 6 lados de nuestra anterior figura necesita 2, ¿cómo vamos a encontrar esa fórmula?

Pues sí, se encontró. Bueno,  la relación que encontró Chvátal en 1975, es que cualquier galería de N vértices, sea como sea, con la forma que sea, por muy enrevesado que sea el Calatrava de turno,  se puede vigilar siempre con N/3 guardianes. En realidad, más concretamente, con la parte entera por defecto de ese número, que escribimos así ⌊N/3⌋, esto es, que si N/3 no nos sale un número natural, sino que sale con decimales, nos quedamos con ése mismo número pero sin decimales, nada de poner trozos de vigilantes, eso lo dejamos para Dexter y otros como él. Por ejemplo, cualquier galería de 13 vértices, sea como sea, necesitará como máximo, 4 vigilantes (13/3 = 4’33333333…) Que sí, que la del último dibujo necesita sólo 1, vale, pero no es posible encontrar ninguna que necesite más de 4, eso es lo que nos asegura el Teorema de la Galería de Arte de Chvátal. Eso y que siempre es posible encontrar un polígono de N vértices que necesite exactamente ⌊N/3⌋ guardianes.

Pues bien, aunque el mérito de encontrar la fórmula que relacionara el número de vértices del polígono con el número máximo de guardianes que se necesitarían para vigilarlo es de Chvátal, ha sido la demostración de este hecho dada por Fisk en 1978 la que más ha trascendido por su elegancia y sencillez. Tanto que ha sido una de las elegidas para aperecer en el Libro de las Demostraciones del que tanto hablaba Erdős y del también hablamos aquí.

Vamos a contar la demostración de Fisk porque es concisa, sencilla, brillante y hermosa.

Lo primero que observa Fisk es que un triángulo, sea como sea, sólo necesita siempre un vigilante en uno de sus vértices, ¿verdad? Pues lo que propone hacer es dividir la galería en triángulos, asegurar la vigilancia en cada unos de esos triángulos y con ello tendrá asegurada la vigilancia del polígono completo. Vamos allá…

En primer lugar, lo que hay que hacer es triangular el polígono ¿Cómo? Añadiendo diagonales interiores uniendo vértices no consecutivos del polígono, siempre que no corten a otra diagonal ya dibujada o a la frontera del polígono.

Ahora vamos a asignar colores a los vértices del polígono respetando únicamente una regla: dos vértices con el mismo color no pueden estar unidos en el dibujo de la triangulación que hemos hecho del polígono. Pues bien, respetando esta regla, Fisk demuestra que se puede colorear la triangulación del polígono con 3 y sólo 3 colores.

Venga. Ahora contamos cuántos vértices hay de cada uno de los 3 colores en la triangulación del polígono. En el ejemplo que estamos haciendo en nuestro cuaderno, tenemos 6 vértices azules, 4 vértices rojos, y 3 vértices verdes. Elegimos el color menos popular de los 3, en esto caso el verde, y colocamos un vigilante en cada uno de los 3 vértices verdes y ¡tachán! Ya está todo el polígono vigilado ¿Por qué? Pues porque todos los triángulos del polígono tienen que tener un vértice verde (en realidad, todos los triángulos tienen un vértice de cada uno de los colores) y como en todos los vértices verdes hay un vigilante, todos los triángulos estarán vigilados.

Sí, es maravillosa la demostración. Yo también me quedé boquiabierta la primera vez que la leí.

Bueno, nos queda apuntar un detalle ¿Cómo sabemos que el color menos popular de la triangulación siempre aparece como máximo ⌊N/3⌋ veces? Pues por el Prinicipio del palomar. Supongamos que los vértices son palomas y los colores, 3 palomares. Asignar colores a los N vértices se puede interpretar como asignar las N palomas a uno de los 3 palomares. Pues ya está, uno de los 3 palomares como mucho, tiene N/3 palomas. Porque si los tres tuvieran más de N/3 palomas, la suma de las 3 cantidades sería superior a N.

Lo que sabemos entonces a partir de este teorema es que sea como sea el polígono de N vértices que nos propongan, como máximo, vamos a necesitar ⌊N/3⌋ vigilantes para vigilarlo. Eso sí, hay veces que necesitaremos muchos menos, y otra en que necesitaremos exactamente ⌊N/3⌋.

Este problema de la Galería de Arte ha dado lugar a una inmensa cantidad de problemas geométricos relacionados, simplemente con modificar algunas de las  condiciones: permitiendo que los vigilantes se muevan, obligando a que cada vigilante esté controlado por otro de sus compañeros en todo momento, restringiéndose a un ángulo de visibilidad (pensando en focos e iluminación), permitiendo que se atraviesen paredes (si pensamos en routers)… Todos problemas muy sencillos de plantear pero la mayoría muy difíciles de resolver.

Lo dejamos por aquí y espero que haya servido para olvidar durante un rato cuántos y quiénes son los que nos están vigilando a todos nosotros…

Si a George Clooney le gustasen las matemáticas…

Cada vez que veo el comercial del señor Clooney ése de la cafetera, no me preguntéis por qué, pero siempre recuerdo esta cita atribuida a Paul Erdős


Un matemático es una máquina que transforma café en teoremas.

Alfrèd Rényi

 

Entonces me lo imagino trabajando conmigo en mi departamento, transformando capsulitas en bellos y elegantes resultados de Geometría Computacional, emborronando la pizarra de mi despacho con puntos en posición general… Bueno, lo normal.

Pero esta entrada no está dedicada al protagonista de Good night, and good luck (foto). Tampoco al profesor Rényi, auténtico autor de la cita sobre el café  y los teoremas. Por cierto, la frase fue dicha en alemán haciendo, además, un juego de palabras con satz que significa teorema y también poso de café (kaffee satz).

Hoy, y ahora que los niños salieron a jugar, os quiero hablar de Paul Erdős (en húngaro con el símbolo “ encima de o y no con diéresis), posiblemente el matemático más famoso del siglo pasado.

 

 

El matemático más famoso del siglo XX fue un vagabundo. Nunca tuvo una casa y todas sus posesiones cabían en una maleta, ganó dinero y distinciones, pero sólo se quedaba con lo estricto para cubrir unas mínimas necesidades y el resto lo donaba a personas necesitadas o a causas que él consideraba justas. Su personalidad sin duda fue muy, muy peculiar.

Paul Erdős nació en Budapest en 1913 , hijo de unos profesores de instituto de origen judío. Ya desde muy niño se vio muy atraído por las matemáticas (a los tres años podía estimar cuántos segundos vive una persona). A los 21 obtuvo su doctorado en matemáticas, pero ese mismo año debido al creciente antisemitismo en Hungría se trasladó a Inglaterra. En 1938 se desplazó a EE.UU. Y empezó su vida itinerante.

Desde entonces su vida consistió en ir de universidad en universidad trabajando con colegas durante unos días hasta que hubieran obtenido algunos resultados dignos de publicarse (los matemáticos, como el resto de los científicos hemos de intentar difundir el fruto de nuestras investigaciones en artículos publicados en revistas científicas). Erdős ha sido el matemático con más publicaciones y, por su método de trabajo, el que más coautores tiene.

Este hecho ha dado lugar en  la comunidad matemática a hablar del número de Erdős.

 

¿En qué consiste dicho número?

 

De alguna manera, mide la distancia a Erdős: él tiene asignado un número 0, todos sus coautores tienen asignado un número de Erdős 1, a los coautores de aquellos que tienen número de Erdős 1 se les asigna número de Erdős 2 y así sucesivamente. Murió en 1996. lo digo por si alguien está haciéndose ilusiones con tener número de Erdős 1.

Algo similar ocurre en otras disciplinas, por ejemplo en el cine se considera el número de Kevin Bacon (no tengo ni idea de por qué ya que existen muchos otros actores con más colaboradores que Kevin Bacon). En dicho número Kevin Bacon tiene asignado el número 0, aquellos que han trabajado en una película con él tiene número 1 y así sucesivamente. Se puede consultar dicho número en esta página. Y tiene su gracia, no crean. Por poner un ejemplo, ¿qué número de Kevin Bacon tiene Chiquito de la Calzada? Sí, 3. Pueden probar con otros actores que se les ocurra, es igualmente llamativo.

 

O por ejemplo, ¿qué número de Kevin Bacon tiene Jin Akiyama del que ya hablamos por aquí?

Eso sí, el número de Erdős de Jin Akiyama es menor que su número de Kevin Bacon.

Una de las autoras de este blog tiene el mismo número de Erdős que de Kevin Bacon, pero no esperen que les cuente por qué tiene número de Bacon 3, aún no ha podido superar ese trauma…

Todo esto del número de Erdős no es más que algo anecdótico y representativo de la gran cantidad de colaboradores que tuvo el matemático húngaro. Sin embargo, se ha llegado a situaciones tan absurdas, en mi opinión, como que, al menos  en dos ocasiones se hayan subastado  números de Erdős en el portal de subasta Ebay. El 20 de abril de 2004, Bill Tozier un investigador con un número de Erdös de 4, ofreció la posibilidad de colaboración para obtener un número de Erdös de 5. El mismo año, en Julio, se llegó a subastar un número de Erdős 2 (el mejor que se puede conseguir en la actualidad ya que Erdős no está en condiciones de seguir publicando artículos).

Por último, tengo que  decir que el que la mayoría de los matemáticos activos tengan un número de Erdős bajo (o que casi todos los actores tengan un número de Bacon bajo) tiene que ver con un fenómeno conocido como mundo pequeño o seis grados de separación, pero eso será tema de otro día.

Siguiendo con Erdős, otra de sus características como matemático era que sabía escoger problemas interesantes. De hecho, cuando él creía que un problema tenía interés, ofrecía dinero por su resolución (dinero que pagaba religiosamente). Alguna vez le preguntaron que qué ocurriría si se resolvían todos los problemas por los que ofrecía dinero. Él contestó que no tendría dinero suficiente para pagar, pero que si todos los clientes de todos los bancos acudieran a retirar su dinero, los bancos tampoco tendrían dinero suficiente y que esta segunda hipótesis era mucho más probable que el que se resolvieran todos sus problemas. Y tan probable… ay…

Le gustaban, como nos gustan a todos los matemáticos, las demostraciones bellas y elegantes. Él sostenía algo así como que Dios, aunque él no creía en esas cosas,  tenía un libro, el Libro, donde estaban las más bellas demostraciones de los resultados matemáticos.

No tienes que creer en Dios, pero deberías creer en el Libro.

Paul Erdős

Cada vez que veía una demostración hermosa de un teorema afirmaba: «Ésta es de la del Libro». De hecho, dos matemáticos, Martin Aigner y Günter M. Ziegler, aceptaron el reto de recopilar en un libro todas aquellas demostraciones que cumplieran los tres requisitos que según Erdős deberían cumplir para estar en el Libro: elegantes, fáciles de entender y notoriamente difíciles de resolver. El propio Erdős sugirió algunas de las demostraciones que deberían figurar. La idea era presentar este libro en marzo de 1998, haciéndolo coincidir con el 85 cumpleaños del matemático húngaro. Lamentablemente, éste murió en 1996 y no llegó a verlo terminado. En España, la editorial Nivola ha publicado la traducción del libro de Aigner y Ziegler, traducido.

Paul Erdős murió tal y como había vivido, de un ataque al corazón durante la celebración de un congreso en Varsovia a la edad de 83 años.

¿Por qué son bellos los números? Es como preguntar por qué es bella la novena sinfonía de Beethoven. Si no ves por qué, nadie te lo puede decir. Yo sé que los números son bellos. Si no lo son, entonces nada lo es.

Paul Erdős

 

Volviendo al principio de este artículo, si Clooney fuese matemático, el que tendría el Libro sería nada más y nada menos que ¡John Malkovich! Mira por donde, así hasta me puedo plantear ser creyente… total, si me regala una bella demostración a cambio de unas capsulitas de voluto… Aunque bien mirado, tampoco me importaría tener que conseguir esa demostración trabajando, codo a codo, con George.

Foto de http://www.nespresso.com/

Pero tal y como se están poniendo las cosas en este país para investigar…mejor será que se quede haciendo películas y anunciando cafeteras.