De cómo proponer un problema cambió totalmente la vida de Esther Klein

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.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

14 Comentarios

  1. Buen artículo.

    En la generalización, solo por aclarar, los puntos también están en posición general, es decir: dados los n puntos, no existen n-1 puntos que estén alineados.

    Cordial saludo.

    Publica una respuesta
  2. ¡Perdón! En este caso es la misma posición general que habló ^DiAmOnD^: es decir, no hay tres puntos alineados.

    Cordial saludo.

    Publica una respuesta
  3. 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?

    Publica una respuesta
  4. 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?

    Publica una respuesta
  5. 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.

    Publica una respuesta
  6. 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, {{2n-4}\choose{n-2}} + 1, se ha conseguido mejorar hasta {{2n-5}\choose{n-2}} + 1 [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 H(n).

    (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. Es decir, para demostrar que H(4)=5=N(4).

    (2.2) Más tarde, Harborth demostró [Harborth 78]que todo conjunto de 10 puntos tiene un pentágono convexo vacío, es decir, que H(5)=10. Este número ya es distinto del N(5)=9 (es lógico que al ser más exigentes con el polígono, necesitemos más puntos).

    (2.3) Más recientemente, Gerken demostró [Gerken 2009] que todo conjunto que tenga un nonágono convexo tiene un hexágono convexo vacío, es decir, que H(6)\leq N(9).

    (2.4) Lo más fascinante es que Horton demostró [Horton 1983] que no existe H(7), es decir, que se puede construir un conjunto de puntos tan grande como se quiera ¡¡sin que contenga ningún heptágono convexo vacío!!

    Un buen enlace para encontrar información sobre este problema puede ser Forcing empty convex polygons.

    Publica una respuesta
  7. Una cosa más:

    El argumento de Esther Klein demuestra que N(4)\leq 5 y que H(4)\leq 5.

    Para demostrar la igualdad basta observar que N(4)>4 y H(4)>4, 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).

    Publica una respuesta
  8. 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 definición de multiconvexidad para dimensiones superiores.

    EDITADO: Te he editado el enlace para que se pueda acceder a él.

    Publica una respuesta
  9. ¡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?

    Publica una respuesta
  10. Magnífico artículo. Y no menos interesante y entrañable el final feliz de la pareja

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com Valora en Bitacoras.com: Proponer un problema atractivo puede traer consigo consecuencias muy interesantes, como la satisfacción por…
  2. De cómo proponer un problema cambió totalmente la vida de Esther Klein - […] De cómo proponer un problema cambió totalmente la vida de Esther Klein […]

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *