In matematica, il "problema del lieto fine" (così chiamato da Paul Erdős perché portò al matrimonio di George Szekeres ed Esther Klein ) è la seguente affermazione:
Teorema: Un qualunque insieme di cinque punti nel piano in posizione generale ha un insieme di quattro punti che sono i vertici di un quadrilatero convesso.
Nel contesto del piano, un insieme di punti si dice in posizione generali se nessuna coppia di essi coincide e nessuna terna di essi è collineare.
Questo fu uno dei risultati originali che portarono allo sviluppo della teoria di Ramsey.
Il teorema del lieto fine può essere dimostrato con una semplice analisi: se quattro o più punti sono vertici dell'inviluppo convesso relativo, è possibile scegliere quattro punti qualsiasi tra questi. In caso contrario l'inviluppo convesso deve avere la forma di un triangolo con due punti al suo interno; in questo caso la retta che unisce i due punti interni ne lascia uno da una parte e due dall'altra; si scelgono allora questi due punti e i due punti interni.
Poligoni più grandi
Paul Erdős e George Szekeres hanno dimostrato la generalizzazione seguente:
Teorema: per un qualunque intero positivo N, esiste un insieme finito di punti nel piano in posizione generale che ha un sottoinsieme di N punti che sono i vertici di un N-agono convesso.
Il teorema del lieto fine dimostra il caso N = 4. In generale, sia f(N) il minimo valore M per cui qualsiasi insieme di M punti in posizione generale deve contenere un N-gono convesso. I risultati noti sono i seguenti:
f(3) = 3, banalmente.. f(4) = 5, come appena visto. f(5) = 9. Un insieme di otto punti senza alcun pentagono convesso è mostrato in figura, mostrando così che f(5) > 8; la parte davvero complicata è mostrare che ogni insieme di nove punti in posizione generale contiene i vertici di un pentagono convesso. f(6) = 17. Questo è stato dimostrato mediante una ricerca al computer che ha eliminato tutte le possibili combinazioni di 17 punti senza esagoni convessi. Il valore di f(N) è ignoto per N > 6.
La congettura di Erdős–Szekeres afferma una relazione tra il numero di punti in un insieme di punti in posizione generale e il suo sottoinsieme più grande che forma un poligono convesso: il numero più piccolo di punti per cui qualsiasi disposizione in posizione generale contiene un sottoinsieme convesso di punti è . Erdős e Szekeres hanno dimostrato che quello indicato è un limite inferiore:
Note
Categoria:Teoria di Ramsey Categoria:Problemi matematici Categoria:Poligoni Categoria:Quadrilateri Categoria:Geometria piana Categoria:Geometria discreta