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:
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
, ¿podemos encontrar un número
tal que para cualquier conjunto que contenga al menos
puntos sea posible seleccionar
de ellos que formen un polígono convexo?
En el caso anterior, , la respuesta es, por tanto, afirmativa, y además
.
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 que podéis ver en A combinatorial problem in geometry.
Pero, como podéis ver en dicho artículo, queda una pregunta sin responder: dado un entero positivo , ¿cuál es el menor número
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
de la siguiente forma:
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 , aunque todavía no se ha podido demostrar. Esa creencia está reforzada por lo que se sabe para los casos
y
. Para
, en el artículo original de Erdős y Szekeres ya se comenta que Endre Makai había demostrado que
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 , 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
Hasta la fecha no se conoce el valor exacto de para
.
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.
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.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Tienes una erratilla en la etiqueta látex. Has puesto «katex».
Muy buen artículo.
Un saludo
Información Bitacoras.com
Valora en Bitacoras.com: 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. …
AlfonsoFR, solucionado, gracias por el aviso. Y por tu comentario sobre el post :).
Buen artículo.
En la generalización, solo por aclarar, los puntos también están en posición general, es decir: dados los
puntos, no existen
puntos que estén alineados.
Cordial saludo.
¡Perdón! En este caso es la misma posición general que habló ^DiAmOnD^: es decir, no hay tres puntos alineados.
Cordial saludo.
¡Qué gran post! Gracias ^DiAmOnD^
Todavía se puede generalizar más el problema (no sé si alguien lo ha hecho ya):
Buscar el mínimo número de puntos N(n) para que en cualquier conjunto de N puntos en el espacio tridimensional s(en posición general, es decir, que ni haya tres alineados ni cuatro coplanarios) sea posible seleccionar n de ellos que formen un poliedro convexo.
¡Y para espacios de 4 o más dimensiones?
Todavía se puede generalizar más el problema (no sé si alguien lo ha hecho ya):
Buscar el mínimo número de puntos N(n) para que en cualquier conjunto de N puntos en el espacio tridimensional s(en posición general, es decir, que ni haya tres alineados ni cuatro coplanarios) sea posible seleccionar n de ellos que formen un poliedro convexo.
¡Y para espacios de 4 o más dimensiones?
Para espacios n-dimensionales, se calcula el casco convexo (convex hull) o su generalización, la alfa-forma (α-shape). Si el politopo es cóncavo, siempre se puede subdividir en politopos convexos mediante una cantidad finita de cortes hiperplanares.
Buen artículo sobre un problema muy interesante. Me toca de cerca, por mi campo de investigación, así que permitidme un par de aportaciones: (1) La cota superior de Erdős y Szekeres, , se ha conseguido mejorar hasta [Tóth-Valtr 2005]. (2) Hay una versión muy interesante del problema, consistente en ponerse un poco más exigentes y buscar un polígono convexo vacío. A éstos se les llama «agujeros» y por eso su número se denota por . (2.1) La demostración de Esther Klein sirve (adaptando muy ligeramente el paso 2) para encontrar un cuadrilátero convexo vacío en cualquier conjunto de cinco puntos.… Lee más »
Una cosa más:
El argumento de Esther Klein demuestra que
y que
.
Para demostrar la igualdad basta observar que
y
, porque en un conjunto de cuatro puntos con la configuración «uno dentro del triángulo que forman los otros tres» no hay ningún cuadrilátero convexo (vacío o no).
Esto de los politopos vacíos me recuerda a los politopos fractales, de los que imagino que no se puede establecer su convexidad porque el término no aplica, ya que sería necesario realizar un número ilimitado de comprobaciones. Así y todo aunque existen alternativas, como las que detalla el artículo enlazado, para construir politopos fractales en base a polícoros convexos y otros politopos de dimensión superior a 4. Parecería, e ignoro si existe demostración, que un politopo fractal determinado, como la esponja de Menger, es cóncavo en cualquiera de las direcciones consideradas, si es que existe (que seguro que sí) una… Lee más »
[…] De cómo proponer un problema cambió totalmente la vida de Esther Klein […]
¡Qué buen artículo!
Lo encontré buscando una solución para un problema que me planteé hace tiempo y no puedo hallarle respuesta. Quiero poner un árbol en la mitad justa del patio de mi casa que tiene forma de pentágono irregular. Al tratar de determinar el «punto central» no puedo encontrar ninguna circunferencia que contenga a los cinco puntos; sólo una elipse. ¿Será que debo tomar como «punto central» la intersección de los ejes de la elipse?
El centro de masas del pentágono, Julio Romeo!!
Magnífico artículo. Y no menos interesante y entrañable el final feliz de la pareja