Problema del final feliç

De Viquipèdia
Salta a la navegació Salta a la cerca
"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[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à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 als matemàtics hungaresos Paul Erdős i George Szekeres.

Anàlisi de casos[modifica]

  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 dóna 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ó[modifica]

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

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; en base al 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:

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

[7]

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

[8]

Referències[modifica]

  1. A world of teaching and numbers - times two, Michael Cowling, The Sydney Morning Herald, 2005-11-07, cited 2014-09-04
  2. En aquest context, posició general significa que no hi ha dos punts en la mateixa posició ni tres punts colineals
  3. Erdős, Paul; Szekeres, George. «2 A combinatorial problem in geometry». A: (en anglès). Compositio Mathematica, 1935. 
  4. Aquest era el problema original, demostrat per Esther Klein.
  5. According to Erdős & Szekeres (1935), this was first proved by E. Makai; the first published proof appeared in Kalbfleisch, Kalbfleisch & Stanton (1970)
  6. 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.
  7. Erdős & Szekeres (1961)
  8. 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[modifica]