Los problemas judíos (matemáticas para la xenofobia)

Hace unos días, a través de Twitter, me llegó una historia de xenofobia cargada de interesantes problemas matemáticos. Os la traigo a mi blog, por su valor histórico, no hay que ignorar este tipo de cosas, y también por la belleza de las matemáticas implicadas en ella.

Se trata de una colección de problemas que el Departamento de Matemáticas de la Universidad Estatal de Moscú  proponía a los aspirantes judíos a dicha Universidad, para evitar que éstos u otros grupos de personas "indeseables" accedieran. Para evitar reclamaciones y/o impugnaciones al proceso, todos estos problemas tiene una solución muy sencilla pero difícil de encontrar. Estos problemas son conocidos también, por si queréis buscar sobre ellos,  con los intuitivos nombres de 'Гробы' (ataúdes) o en inglés, como 'killers' (asesinos).

Si intentáis resolver actualmente algunos de estos problemas, puede que no os resulten tan complicados, pero hace 30 años, las cosas eran diferentes y los conocimientos menores. También hay que decir que el procedimiento para estos aspirantes era ir resolviendo un problema tras otro hasta fallar en alguno, momento en el que eran eliminados, con lo que las condiciones de contorno eran peores que las que tenemos nosotros en casa si lo intentamos por el puro gusto de resolver un reto matemático.

Para muestra, un botón, como dicen, elijamos uno sencillito, que podamos intentar todos:

O sea, ¿eres capaz de dibujar 6 puntos en el plano, de forma que la distancia entre cualquier par de ellos sea un número entero, y no haya tres alineados? 

Venga, va, os doy una pista, que es muy fácil. 

Un triángulo rectángulo verifica esa  propiedad, por ejemplo, de lados 3, 4 y 5, si hacemos alguna reflexión del mismo, podríamos generar más puntos...

¿Ya? ¿Te rindes?

A ver. Si tenemos un triángulo rectángulo ABC de lados enteros, el área del mismo es un número racional. Por lo tanto, si consideramos la altura sobre el lado AC, la longitud de dicha altura debe ser también racional. Llamemos D al pie de dicha altura.

Si consideramos el simétrico de B respecto del lado AC, llamémosle E, tendremos cuatro puntos, A, B, C y E, todos a distancia racional unos de otros.

Ya tenemos 4 puntos a distancias racionales, pero tienen que ser 6 y a distancia entera, no lo olvidemos. 

Por otra parte, el triángulo ABC  es semejante al triángulo BDC, lo que implica que tanto el segmento AD como el segmento CD tienen que ser racionales. Si consideramos ahora los simétricos de B y E respecto de la mediatriz entre A y C, tenemos dos nuevos puntos, F y G.  Pues bien, ya tenemos 6 puntos, A, B, C, E, F y G, todos a distancias racionales unos de otros.

Para que las distancias sean enteras, como se nos pedía, basta con multiplicar por el número adecuado para eliminar todos los denominadores. 

Si empezamos con el triángulo rectángulo de lados 3, 4 y 5, con la hipotenusa sobre el eje de abcisas y centrada en el origen de coordenadas, basta con cambiar la escala, multiplicando por 10, la construcción anteriormente descrita, para tener la solución.

Hay muchos más problemas judíos, coffins o killers. Si queréis ver más os recomiendo este trabajo de Khovanova y Radul que fue el que me descubrió la existencia de los mismos.  


Pero lo verdaderamente terrible de esta historia es el trasfondo humano.


Esta página de la misma Tanya Khovanova aporta enlaces a documentos sobre este espisodio.

Sobre este mismo asunto, se ha publicado el libro Your failed your math test, Comrade Einstein: adventures y misadventures of young mathematicians en el que  el matemático Ilan Vardi presenta y compara los problemas mencionados en esta entrada con los de la Olimpiada Matemática del año 2000. Incluye además un ensayo "El genocidio intelectual" explicando el trasfondo histórico de esta práctica llevada a cabo en la URSS en las décadas de los 70 y 80.

Esta historia también tiene su heroína, Беллу Суббатовскую Светлана (Bella Abramovna Subbotovskaya), que ante esta situación de injusticia con los judíos fundó con ayuda de otros colegas la Universidad del Pueblo Judío (Еврейский народный университет) y que murió, de forma extraña cuando sólo tenía 44 años. 

George G. Szpiro, escribió en este artículo sobre ella: "Bella Abramovna Subbotovskaya and the Jewish People Unniversity":

"Exactly 25 years ago, on September 23, 1982, at

about 11 o’clock at night, an accident occurred in

a dark street in Moscow. A woman walked along

the sidewalk. She had just visited her mother and

was on her way home. It was a quiet street, hardly

a vehicle passed by at this hour. Suddenly a truck

appeared at high speed, hit the woman, and drove

off. Moments later another car drove up, stopped

for a moment next to the victim, and also drove

off. An ambulance came—who had called it?—and

took the victim straight to the morgue. The funeral

took place the next day. It was a very low key af-

fair, nobody talked, no eulogy was held. Mourners

only whispered among themselves, all the while

observed by a few official-looking men. Eventu-

ally everybody quietly dispersed. The hit-and-run

driver was never found, and the case was closed.

The accident had all the trappings of a KGB hit.

The victim was the 44-year old mathematician Bella

Abramovna Subbotovskaya. In the days preceding

her death she had been summoned several times

for interrogations to KGB offices. The “crime”

about which she was questioned was the organiza-

tion of a “Jewish People’s University”.

Me temo que ha quedado triste y lúgubre el final de esta entrada, pero esta es la historia, hasta donde yo sé.

Con esta entrada participo en la Edición 2.7 del Carnaval de Matemáticas que este mes se aloja en La aventura de la Ciencia

Si Euclides hubiese conocido Manhattan...

Si Euclides hubiese conocido Manhattan, no diríamos que la distancia más corta entre dos puntos es la línea recta. Puesto que si  estamos pensando en diseñar una ruta que una dos puntos dentro de la Gran Manzana (o cualquier ciudad), la distancia real no siempre es la medida del segmento que une a esos puntos, puesto que en la mayoría de los casos, ese segmento atravesará algún rascacielos. Y eso no está bonito, no. 

Figura 1

En la Geometría Euclideana, que es la geometría que todos aprendemos desde nuestros primeros años de estudios, la distancia entre dos puntos se mide como la longitud del segmento que los une, o dicho de otra forma, como el módulo del vector que esos dos puntos definen. Esa forma de medir la distancia es conocida como distancia euclídea y es la que usamos cuando medimos usando un metro entre los dos extremos de lo que queremos medir. En realidad, se trata de una consecuencia del Teorema de Pitágoras. Si tenemos dos puntos en el plano de coordenadas (a,b) y (c,d) respectivamente y queremos calcular la distancia euclídea entre ellos, basta con fijarse que la longitud de los catetos del triángulo rectángulo que definen son (c-a) la de uno y (d-b) la del otro.  Entonces, por el Teorema de Pitágoras, sabemos que la distancia euclídea se mide como

 √(c-a)²+(d-b)^2.

Ahí todo está bien y correcto, pero esa no es la única forma de medir la distancia entre dos puntos en el plano. Existe otra distancia, conocida como Distancia de Manhattan o Distancia 
L₁, que mediría la distancia entre los puntos de la Figura 1 como 

 (c-a) + (d-b)

Es decir, la suma de las longitudes de los dos catetos del triángulo rectángulo. O bien, la de cualquier ruta que una al punto (a,b)  con el punto (c,d) a través de segmentos horizontales y verticales, en otras palabras, la longitud de cualquier escalera que suba desde (a,b)  con el punto (c,d) 

En verde, la distancia euclídea, y en rojo, azul y amarillo, la distancia Manhattan. (Imagen  sacada de aquí)

Pues bien, cuando se trata de diseñar rutas de recorrido mínimos en ciudades, tiene más sentido usar esta distancia que la Euclídea, por lo de no atravesar rascacielos que habíamos dicho. Es más, puesto que todas las 'escaleras' tienen la misma longitud, nos permite elegir entre distintas opciones, en función de semáforos, zonas de dudosas seguridad, etc...

Evidentemente, no todas las ciudades, ni siquiera Nueva York, están distribuidas como una cuadrícula, pero se considera para según qué problemas de dieños de rutas este tipo de distancia. Y también, cómo no, en el diseño de circuitos ortogonales en los que predominan la conexiones en vertical y horizontal, o en el de un plano de metro.

Otra cosa que no diríamos si pensáramos con la distancia de Manhattan es “No había nadie en 10 Km a la redonda” Porque cuando utilizamos esta expresión, estamos intrínsecamente midiendo con la distancia euclídea. Con esta distancia, la que usamos habitualmente en el día a día, los puntos que están a menos distancia de 10 Km de nosotros, son aquellos que están contenidos en un círculo alrededor nuestra de radio 10 Km.

Pero si pensáramos con la distancia de Manhattan, no sería un círculo, sino ¡un rombo!

Todos los puntos de la frontera del círculo de la izquierda están a la misma distancia euclídea del origen de coordenadas, y todos los puntos de la frontera del rombo de la izquierda están a la misma distancia L₁ del origen de coordenas, como se explica en la siguiente figura:

El punto verde y el punto rojo están a la misma distancia del punto azul (nótese que el ángulo formado por el rombo y el eje en el punto verde es de 45º y, por lo tanto, la longitud de los dos catetos del triángulo rectángulo formado es la misma, está representada con a en la Figura) Y en general, cualquier punto de la frontera del rombo está a la misma distancia del origen (punto azul).

Ahora vamos a ver, que  dependiendo de la distancia elegida, el punto más cercano a uno dado puede ser distinto, lo que sería de utilidad conocer a la hora de diseñar rutas de longitud mínima, por ejemplo, para empresas de distribución, mensajería...

Si usamos la euclídea (la usual) el punto rojo está más cerca del origen (en azul) mientras que si usamos la de Manhattan el origen esá más cerca del punto verde. 

Pues bien, ahora que ya conocemos la distancia Manhattan, os formulo una pregunta. Si tenemos dos puntos sobre el plano, P y Q, los puntos que están a la mitad de camino entre P y Q, a la misma distancia de ambos, definen una recta que conocemos, como mediatriz.

¿Y si usamos la distancia L₁,? ¿Qué aspecto tiene la mediatriz entre P y Q? 

Vamos a verlo. Construimos el rectángulo definido por P y Q

Como la distancia de P a Q es (a+b), los puntos sobre la mediatriz PQ, son los que están a distancia (a+b)/2 de cualquiera de ellos, por ejemplo, R y S

Pero también estarán en la mediatriz PQ todos los puntos del segmento RS, vamos a verlo en la figura siguiente con el punto T

En la figura se ve que d(P,S)=d(P,T)= (a+b)/2 (d(P,S) es la forma de escribir "distancia de P a S") y que la d(Q,R)=d(Q,T)=(a+b)/2 y, por lo tanto, T está en la meditariz PQ. Igualmente, se podría razonar con cualquier punto del segmento RS.

Pues bien, para terminar la mediatriz, sólo hay que añadir las demirrectas verticales que parten, respectivamente, de R y de S, 

obteniendo la siguiente poligonal que divide al plano en dos semiplanos, los que están más cerca de P que de Q y viceversa.

No me negaréis que quedarían más monas las lindes de las parcelas con este tipo de mediatrices, ¿no?.

Eso sí, puede que la distancia Manhattan sea más práctica y refleje mejor la realidad en el diseño y optimización de rutas de distribución, pero mi experiencia como madre me permite asegurar que cuando somos niños es la distancia eulcídea la que 'traemos' instalada: "De aquí para acá, mío, de aquí para allá, tuyo"

PS: Cuando explico esta distancia a mis estudiantes no puedo resistir la tentación de llamarla Distancia del Ensanche, y es que Barcelona es mi debilidad.

Con esta entrada participo en la Edición 2.6 del Carnaval de Matemáticas que este mes se aloja en La vaca esférica

Mind the map

La historia del mapa del metro de Londres es bastante conocida entre los que trabajan o alguna vez hemos trabajado en Teoría de Grafos, o más concretamente, en Inmerión de Grafos (Graph Drawing). ¿Por qué? Pues básicamente, porque nos permite explicar de forma sencilla y casi anecdótica la importancia de la representación de un grafo.

De forma coloquial y sencilla, un grafo no es más que un conjunto de elementos, a los que llamaremos vértices, que se unen entre ellos, por parejas, no necesariamente todos, definiendo lo que llamamos aristas del grafo. Para muestra, un grafo:

Los vértices serán los elementos del conjunto {1, 2, 3, 4} y las aristas {(1,2),(1,3), (1,4), (2,3), (2,4), (3,4)} (vamos, lo que son cuatro puntos, todos unidos con todos).

Ése es el grafo. De hecho, es un grafo conocido como K₄ y una posible representación (dibujo) del mismo  sería ésta (Figura 1)

Figura 1

O sea, que para que nos entendamos, una representación   es un dibujo del grafo. Pero ésa no es la única posible representación  de K₄ también podríamos dar otra, como se puede ver en la Figura 2

Figura 2

Y si te preguntas para qué buscar otra representación distinta, pues, por ejemplo, porque la de la Figura 2 no tiene cruces entre sus aristas, es una representación plana como decimos los de Grafos. Y las representaciones planas son mejores cuando se diseñan, por ejemplo, circuitos.

Ahora, a ver, si tenemos K₅ (5 vértices, todos unidos con todos) ¿es posible dar otra representación distinta sin cruces entre sus aristas? O como decimos en Teoría de Grafos, ¿es posible dar una inmersión plana de K₅? Os dejo unos minutos para que lo intentéis.

Una inmersión de K₅

Venga, no os agobiéis, no es posible. De hecho es uno de los teoremas más famosos de la Teoría de Grafos, el Teorema de Kuratowski

Hasta aquí espero haberos convencidos de la importancia del dibujo de un grafo. Para un mismo conjunto de vértices y una misma lista de conexiones entre ellos, puede haber trazados con o sin cruces entre las líneas. Pero vamos a ver otro ejemplo antes de hablar del mapa del metro de Londres.

En la siguiente ilustración, tenemos 4 grafos.

Si nos fijamos bien, en el grafo I₁, se ve fácilmente que este grafo es Hamiltoniano, hay un camino que pasa por todos los vértices y vuelve al de origen, sin repetir vértices. El grafo I₂ es fácil ver que es un grafo regular, es decir, de todos los vértices sale el mismo número de aristas. En cuanto al grafo I_3, se puede intuir que es un grafo plano, que se puede dibujar sin cruces entre aristas. Y, por último, si miramos el grafo I4, se ve claramente que es bipartito, es decir, se pueden colorear los vértices usando sólo 2 colores, de forma que nunca se conecten vértices del mismo color. 

Pues bien, los 4 son el mismo grafo, son 4 dibujos distintos del  mismo grafo.

En definitiva, depende del dibujo que hagamos de nuestro grafo, de la representación que elijamos, podemos destacar, y por lo tanto aprovechar, una característica u otra  del grafo. Por lo tanto, parece que merece la pena detenerse un poco a la  hora de dibujar un grafo,

Nos vamos a Londres. ¡Venga!

Londres, Febrero de 2001

                                   

Los primeros mapas del metro de Londres eran geográficos, básicamente, consistían en dibujar sobre un plano de la ciudad los recorridos de las distintas líneas.

Mapa del metro de Londres en 1908

Fue Harry Beck, ingeniero electrónico empleado en el metro de Londres, el primero que se percató de que al usuario no le interesaba conocer el recorrido del metro bajo tierra, sino simplemente, conocer la posición relativa de las líneas y estaciones para realizar los trasbordos que necesitase. 

Harry Beck

Se le ocurrió entonces, en 1931, que en realidad, más que un diseño geográfico, lo que resultaría útil sería un diseño topológico, con menos curvas y direcciones en las líneas, y, de broma, hizo su primer diseño basado en los utilizados en circuitos eléctricos. Aún un poco reticentes, lanzaron la idea de Beck entre los usuarios y fue aceptada con entusiasmo por los usuarios del metro.

Primer mapa de Beck de 1933

Y hasta hoy, esa idea topológica del mapa de Beck, es la más utilizada en el mundo para este tipo de  planos, incluso hasta en nuestro metro de Sevilla, aunque aquí, sinceramente, aún podríamos permitirnos el geográfico.

Metro de Sevilla

Éste es otro ejemplo más de la importancia del dibujo de un grafo, puesto que podemos entender las estaciones como vértices y las líneas como aristas. De hecho, Beck, a lo largo de su trayectoria, introdujo diversos cambios a su diseño original en pos de conseguir mayor claridad en el plano. 

En 1936, entre otros cambios, eliminó curvas y sólo permitió ángulos de 45º y 90º 

Mapa de 1936

En 1940, le pidieron, entre otros detalles, que incorporase ángulos de 60º también, idea que se desechó por enturbiar la claridad del plano. 

Mapa en 1941

Se puede consultar aquí la evolución de los mapas de del metro de Londres y observar qué tipo de modificaciones iban apareciendo siempre para mejorar la usabilidad de los mismos. 

Plano de 2011

Pero si  leemos esa evolución, nos damos cuenta de que no sólo se trata de dar un trazado topológicamente correcto y sencillo para el usuario, sino que se topan con otro problema: las etiquetas. Deben tener suficiente tamaño para que se puedan leer, pero lo justo para que no se "amontonen" en el mapa y para que el tamaño del plano del metro no sea del tamaño de una catálogo de Worten. 


Y ese problema, el problema del etiquetado de mapas, map labeling problem, no acerca un poco a algo que me gusta bastante, la Geometría Computacional. 


Lo que me llamó la atención la primera que oí hablar de este tipo de problemas, como muchos de los abordados por la Geometría Computacional, es la sencillez de su planteamiento y la increíble dificultad de dar una buena solución.


¿De qué se trata? Pues de que tenemos que poner etiquetas en un mapa a: puntos, líneas (curvas o poligonales) y regiones. Hay que hacerlo de forma legible, sin ambigüedades y sin solapamiento de las etiquetas. 

Etiquetas para puntos

Hay que cumplir además ciertas reglas, más o menos, aceptadas por todos. 


En el etiquetado de puntos, por ejemplo: se prefiere que la etiqueta esté a la derecha (no a la izquierda), que esté arriba (no por debajo)...


En el etiquetado de líneas poligonales o curvas, las etiquetas deben conservar una distancia mínima, no debe intersectar a la línea etiquetada, con poca curvatura, pocos puntos de inflexión, lo más horizontal posible... 


En el etiquetado de regiones, no debe cruzar la frontera de la región, debe quedar claro cuál es la región completa etiquetada, que no entre en conflicto con etiquetas de puntos o líneas...etc.

Pues bien, dada la complejidad y el hecho de que los problemas de etiquetado de mapas no se reducen sólo al ámbito de transportes públicos, éstos han dado lugar a muchísmos trabajos de investigación y a una larga lista de algoritmos de aproximación para tratar de resolverlos. 


Desgraciadamente, no existen  buenos algoritmos que resuelvan el problema computacional, es por ello que aún hoy en día, el etiquetado de los mapas se hacen a mano. Un experto puede poner entre 20 y 30 etiquetas en un mapa por hora.


Así que en contra de lo que algunos piensan, no es tan fácil colocar etiquetas.... lo dejamos por aquí. Eso sí, colorearlos, sabemos que sólo con cuatro colores.


Si te interesa el tema, te recomiendo un paseo por esta página de Alex Wolff o echarle, por ejemplo un vistazo a este otro trabajo. 

Este mapa, de 2003, está en el London Transport Museum

Con esta entrada participo en la Edición 2.6 del Carnaval de Matemáticas que este mes se aloja en La vaca esférica

Se puede viajar a la dimensión 43 y seguir siendo un tío simpático, como Paco Santos

Si es que volar no debe ser ni bueno... Francisco Santos Leal  (Paco para sus amigos, muchos) es profesor de la Universidad de Cantabria y ha sido noticia en el último año por haber refutado, después de 53 años la conjetura de Hirsch. Paco volaba desde Bilbao camino de Paris leyendo On the Exact Maximum Complexity of Minkowski Sums of Convex Polyhedra (de Fogel et al.) cuando se le ocurrió cómo construir el contraejemplo que la desmontaría. Afortunadamente, anotó las ideas en un cuaderno que llevaba y no en el margen de la citada revista porque la dejó olvidada en el avión y se hubiese repetido la historia de Fermat.

Sobre el trabajo de Paco alrededor de la citada conjetura se han publicado en revistas y en blogs artículos bastante interesantes, no voy a tratar de contarlo mejor de lo que ya lo han hecho, por ejemplo Tomás Recio en este blog,  ni tan  exhaustivamente como lo ha hecho Gaussianos en su blog ... 
También los medios menos especialistas se hicieron eco de la noticia y, sobre todo, me resulta especialmente emocionante este artículo  publicado en Lastampa el pasado 27 de Abril, en el que el profesor Bernd Sturmfels  reconoce honestamente que Paco resolvió con brillantez el problema que él abandonó después de un año por encontrarlo demasiado complicado.

Pero Paco es mi amigo y acabamos de coincidir en la Universidad de Alcalá de Henares durante la celebración del EGC de este año y, aprovechando que estábamos en el Carnaval de Matemáticas, le pedí que me concediera una entrevista para Seispalabras, a lo que accedió con su amplia sonrisa y su mirada alegre y traviesa. La cita sería durante el coffee break de la mañana del Jueves 30 de Noviembre, en la meeting room del congreso. Quiso el azar y los buenos vinos de La Suite en Alcalá de Henares, que la noche anterior, tras el banquete de gala del congreso nos acostáramos un poco tarde y que la mañana del día en cuestión estuviésemos los dos más bien dormidos.

“La grabamos en vídeo, Paco, que no tengo ganas de escribir, ¿vale?”

Y eso hicimos. Un par de preguntas informales, una charla entre dos colegas que se encuentran de cuando en cuando y que se ríen ebrios de geometría y sueño.

Por cierto, podréis ver en el vídeo que, a pesar del cansancio, además de ser un tío brillante como conozco pocos, Paco es simpático, cariñoso y guapo, muy guapo.

Podéis ver el vídeo también en Youtube

Pues sí, como se dice en el vídeo, tengo el honor de llevar en mi tesis doctoral un contraejemplo que se le ocurrió hace algunos años, 14, durante un congreso en Barcelona. También al día siguiente de la cena del congreso, por cierto. Fue un banquete el que nos ofrecieron tan espectacular como delicioso, pero excesivo. Como consecuencia, nadie pudo dormir aquella noche, tratando de hacer la digestión. Los había que paseaban por los pasillos, otros leían, matemáticas y/o ficción, otros veían la tele...pero nuestro desvelado de Santander encontró un contraejemplo que aparecería en mi tesis “Geometría Computacional en Superficies” y posteriormente en nuestro libro. Si es que este chico ¡vale un potosí!

Por cierto, me pidió que os rogara que cada vez que volarais en Air France, miraseis en los bolsillos de los asientos por si encontráis un ejemplar del volumen 42 de Discrete and Computational Geometry, porque aunque no esté descrito el contraejemplo en el margen, le gustaría tenerla de recuerdo.

Gracias Paco, por secundarme en todas mis ocurrencias. Es un verdadero placer y todo un orgullo haber “crecido” cerca tuya. Nos vemos en Puerto Vallarta, a ver si encontramos al Capitán Stubing.

Con esta entrada participo en la edición 2.5 del Carnaval de Matemáticas, en esta ocasión hospedada por Mago Moebius