Problema del final feliç

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.)

El 1935, Erdős i Szekeres^[3] 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.^[4]
• 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.
• f(6) = 17.^[6]
• 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:

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

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

${\displaystyle f(N)\geq 1+2^{N-2},}$ ^[7]

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

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