# Problema del final feliç

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:
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 hongaresos Paul Erdős i George Szekeres.

## Anàlisi de casos

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

## Generalització

El 1935, Erdős i Szekeres van demostrar la següent generalització:
    Per cada enter positiu N, qualsevol conjunt finit prou 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).$

## Referències

* ↑ A world of teaching and numbers - times two, Michael Cowling, The Sydney Morning Herald, 2005-11-07, cited 2014-09-04
* ↑ En aquest context, posició general significa que no hi ha dos punts en la mateixa posició ni tres punts colineals
* ↑ Erdős, Paul; Szekeres, George. «2 A combinatorial problem in geometry». A: {{{títol}}} (en anglès). Compositio Mathematica, 1935, p. 463-470.
* ↑ Aquest era el problema original, demostrat per Esther Klein.
* ↑ According to Erdős & Szekeres (1935), this was first proved by E. Makai; the first published proof appeared in Kalbfleisch, Kalbfleisch & Stanton (1970)
* ↑ 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.
* ↑ Erdős & Szekeres (1961)
* ↑ Tóth & Valtr (2005). Veure Coeficient binomial i Cota superior asimptòtica per la notació usada aquí i Nombres de Catalan per l'expansió asimptòtica.

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