Proponer un problema atractivo puede traer consigo consecuencias muy interesantes, como la satisfacción por la propia resolución del mismo o el posterior estudio de sus posibles, y siempre enriquecedoras, generalizaciones. Esto es lo que ocurrió en la siguiente historia, protagonizada por Esther Klein, pero en este caso el problema propuesto cambió tanto su vida (principalmente por culpa de Paul Erdős y, sobre todo, de George Szekeres) que el problema eN cuestión ha pasado a la historia con el «problema del final feliz» (happy ending problem en inglés).

Antes de plantear este problema y de contar la historia que lo rodeó vamos a recordar un par de cuestiones relacionadas con polígonos:

  • Un polígono convexo es un polígono que cumple que cualquier segmento que una dos puntos de dicho polígono queda totalmente contenido dentro de él.

    En la siguiente imagen podéis ver un polígono convexo y uno no convexo:

  • La envolvente convexa de un conjunto de puntos del plano es la intersección de todos los conjuntos convexos que contienen a todos esos puntos.

    Vamos a explicar esto de forma más intuitiva. Supongamos que tenemos unos cuantos puntos en el plano, y pensemos en ellos como clavos clavados en el suelo. Tomemos ahora una goma elástica y estirémosla hasta que todos los puntos queden encerrados por ella. Si la soltamos, se apoyará en algunos de esos puntos quedando a su vez totalmente tensa. Entonces, el polígono formado por la goma es la envolvente convexa del conjunto inicial de puntos:

Bien, comencemos con nuestra historia. Nos desplazamos a Hungría, Budapest concretamente, en 1933. Esther Klein, una estudiante de Físicas de la Universidad de Budapest, asiste habitualmente a reuniones en las que todos los miembros son apasionados de las matemáticas y hablan y discuten sobre ellas. En un momento de esa reunión Esther decide proponer el siguiente problema:

Dados cinco puntos en el plano tal que no haya tres de ellos que estén alineados (lo que se llama en posición general), demostrar que hay cuatro de ellos que son los vértices de un cuadrilátero convexo.

Os dejo un ratito para que intentéis resolverlo…

…¿ya? Bueno, por si acaso no habéis podido os echo una mano. Un primer vistazo a la situación nos dice que la envolvente convexa de esos puntos puede un pentágono, un cuadrilátero o un triángulo. Vamos a estudiar los tres casos por separado:

  1. Si la envolvente convexa es un pentágono, tomando cuatro puntos cualesquiera ya tenemos un cuadrilátero convexo:

  2. Si la envolvente convexa es un cuadrilátero, los cuatro vértices del mismo nos sirven como vértices del cuadrilátero que buscamos:

  3. Si la envolvente convexa es un triángulo, tenemos que los otros dos puntos son interiores a dicho triángulo. Si tomamos la recta que pasa por esos dos puntos, habremos dividido el triángulo en dos partes, de tal forma que en una de ellas queda uno de sus vértices y en la otra quedan los otros dos (esto es seguro, ya que hemos dicho que tres de esos puntos en ningún caso están alineados). Tomando los dos puntos interiores y los dos vértices del triángulo que queda en una de las partes ya tenemos los vértices del cuadrilátero buscado:

Fue la propia Esther quien lo resolvió de la forma descrita anteriormente, pero además propuso como problema la siguiente generalización del mismo:

Dado un entero positivo n, ¿podemos encontrar un número N(n) tal que para cualquier conjunto que contenga al menos N puntos sea posible seleccionar n de ellos que formen un polígono convexo?

En el caso anterior, n=4, la respuesta es, por tanto, afirmativa, y además N(4)=5.

El caso es que este enunciado encandila principalmente a dos de los asistentes a la reunión: Paul Erdős y George Szekeres, y son ellos dos, en un artículo conjunto, quienes en 1935 publican dos demostraciones sobre la existencia de ese valor N(n) que podéis ver en A combinatorial problem in geometry.

Paul Erdős (izquierda; fuente) y George Szekeres (derecha; fuente).

Pero, como podéis ver en dicho artículo, queda una pregunta sin responder: dado un entero positivo n, ¿cuál es el menor número N(n) que cumple el enunciado anterior? Erdős y Szekeres no fueron capaces de responder a esto satisfactoriamente….en ese momento, ya que 30 años más tarde, en On some extremum problems in elementary geometry, sí que pudieron responder parcialmente a dicha pregunta. No consiguieron dar un valor exacto, pero sí acotar N(n) de la siguiente forma:

2^{n-2}+1 \leq N(n) \displaystyle{\leq {{2n-4} \choose {n-2}}}

Y ahí se quedaron, no pudieron avanzar más…y nadie ha podido llegar mucho más lejos. Actualmente este problema sigue abierto, aunque desde que Erdős y Szekeres encontraron estas cotas se ha hecho algún pequeño avance.

Desde hace tiempo se cree que la cota inferior es en realidad el valor de N(n), aunque todavía no se ha podido demostrar. Esa creencia está reforzada por lo que se sabe para los casos n=5 y n=6. Para n=5, en el artículo original de Erdős y Szekeres ya se comenta que Endre Makai había demostrado que

N(5)=2^{5-2}+1=9

pero esa prueba nunca se llegó a publicar. La primera publicada de la que se tiene constancia aparece en el artículo A combinatorial problem on convex regions, de J.D. Kalbfleisch, J.G. Kalbfleisch y R.G. Stanton, de 1970. No he podido encontrar el artículo original (si alguien lo encuentra le agradecería que dejara link en un comentario), pero, por ejemplo, se puede ver una demostración de este hecho (junto con mucha más información sobre este problema) en The Erdős-Szekeres problem on points in convex position – A survey, de W. morris y V. Soltan.

Y para n=6, en 2006 se publicó el artículo Computer solution to the 17-point Erdős-Szekeres problem, del propio Szekeres (que había fallecido el año anterior) y Lindsay Peters, en el que demostraban que

N(6)=2^{6-2}+1=17

Hasta la fecha no se conoce el valor exacto de N(n) para n > 6.

Después de todo esto todavía queda una pregunta por responder: ¿por qué se llama a este resultado el problema del final feliz (o happy ending problem)? Muy sencillo: porque a raíz de la propuesta de problema inicial y el estudio de esta generalización Esther Klein y George Szekeres acabaron casándose.

George y Esther Szekeres (fuente).

De hecho fue el propio Erdős quien bautizó, por esta razón, al problema como el happy ending problem. El matrimonio de Esther y George duró casi 70 años, hasta que la salud de Esther se deterioró, afectando mucho al propio George. Al parecer ambos murieron con menos de una hora de diferencia.

Toda una vida juntos gracias a un problema propuesto en una reunión de personas apasionadas por las matemáticas, y todo un mundo nuevo por explorar: la geometría combinatoria. Creo que nadie podrá negar que es una historia maravillosa, tanto en lo personal como en lo matemático.

Además de los enlaces a los artículos que he ido dejando entre el texto, también os recomiendo que le echéis un vistazo a este pdf sobre el happy ending problem de Theorem of the Day, a este artículo de Derek Lief, a la entrada sobre el happy ending problem de la Wikipedia en inglés y a este vídeo de pimedios en el que su autor nos habla sobre el problema. Y también quiero resaltar que conocí más en profundidad esta historia leyendo el libro El arte de contar, de Juanjo Rué.

Y quiero recordaros también que si en algún momento estáis interesados en consultar algunos de los artículos que publicó Erdős lo tenéis fácil, ya que como comenté en este minipost todos ellos están disponibles para descargar.

Esta entrada participa en la Edición 5.8: Betty Scott del Carnaval de Matemáticas, que en esta ocasión organiza Tocamates.

Print Friendly, PDF & Email
5 2 votes
Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉