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[1]), és el següent enunciat:
«Qualsevol conjunt de cinc punts en el pla en posició general[2] (no colineals) conté un subconjunt de 4 punts que són vèrtexs d'un quadrilàterconvex.»
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.
Si els 5 punts formen els vèrtexs d'un pentàgon convex, poden ser elegits 4 punts qualssevol (cas vermell en la imatge).
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).
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.)
El 1935, Erdős i Szekeres[3] van demostrar la següent generalització:
Per cada enterpositiuN, 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(5) = 9.[5] 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.
Això ha estat demostrat per Szekeres & Peters (2006). Van fer una recerca amb ordinador que eliminava totes les configuracions possibles de 17 punts sense hexàgons convexos mentre examinaven només una petita part de totes les configuracions.