Problema del final feliç

"Qualsevol distribució de 5 punts no alineats conté els vèrtexs d'un quadrilàter convex"

En matemàtiques, el problema del final feliç (anomenat així per Paul Erdős, ja que va conduir a la relació i el posterior matrimoni entre el seu amic matemàtic George Szekeres i Esther Klein), és el següent enunciat:

«Qualsevol conjunt de cinc punts en el pla en posició general (no colineals) conté un subconjunt de 4 punts que són vèrtexs d'un quadrilàter convex.»

Aquest plantejament de 1933 és un dels resultats que van portar al desenvolupament de la teoria de Ramsey, un camp de les matemàtiques que estudia les condicions sota les quals l'ordre ha d'aparèixer.

També és anomenat Conjectura d'Erdős-Szekeres en honor dels matemàtics hungaresos Paul Erdős i George Szekeres.

Anàlisi de casos

1. Si els 5 punts formen els vèrtexs d'un pentàgon convex, poden ser elegits 4 punts qualssevol (cas vermell en la imatge).
2. Si en la configuració de punts es forma un triangle amb dos punts interiors, s'agafen els dos punts interiors i dos punts concrets del triangle (cas verd en la imatge).
3. Si els punts formen un quadrilàter amb un punt interior, i no es dona el cas anterior, aquest quadrilàter és convex (cas en blau en la imatge, tot i que també es pot utilitzar el punt interior.)

Generalització

Un conjunt de 8 punts en posició general que no conté cap pentàgon convex

El 1935, Erdős i Szekeres van demostrar la següent generalització:

Per cada enter positiu N, qualsevol conjunt finit suficientment gran de punts en el pla en posició general té un subconjunt de N punts que formen els vèrtexs d'un polígon convex.

La prova va aparèixer en el mateix document que demostra el teorema d'Erdős-Szekeres sobre subseqüències monòtones en seqüències de nombres, un resultat que precisa un dels corol·laris del teorema de Ramsey.

Sigui f(N) la funció que denota el nombre mínim M pel qual qualsevol conjunt d'M punts en posició general ha de contenir un polígon convex d'N costats, se sap que:

• f(3) = 3, de manera trivial.
• f(4) = 5.
• f(5) = 9. A set of eight points with no convex pentagon is shown in the illustration, demonstrating that f(5) > 8; the more difficult part of the proof is to show that every set of nine points in general position contains the vertices of a convex pentagon.
• f(6) = 17.
• El valor de f(N) és desconegut per tot N > 6; a partir del resultat de Erdős & Szekeres (1935) es conjectura que és finit.

Basant-se en els valors coneguts de f(N) per N = 3, 4 i 5, Erdős i Szekeres van conjecturar en el seu escrit que:

$f(N)=1+2^{N-2}\quad {\mbox{for all }}N\geq 3.$

Posteriorment van demostrar, construint exemples explícits, que:

$f(N)\geq 1+2^{N-2},$

però la millor cota superior coneguda quan N ≥ 7 és:

$f(N)\leq {2N-5 \choose N-2}+1=O\left({\frac {4^{N}}{\sqrt {N}}}\right).$

Enllaços externs

• P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Math., Vol. 2, p. 463-470 (1935)
• «Happy ending problem» (en anglès). PlanetMath. Arxivat de l'original el 2006-09-25. [Consulta: 19 agost 2009].
• «Ramsey-theoretic proof of the Erdős-Szekeres theorem» (en anglès). PlanetMath. Arxivat de l'original el 2006-09-25. [Consulta: 19 agost 2009].
• Weisstein, Eric W., «Happy End Problem» a MathWorld (en anglès).