Don't take life too seriously: it's just a temporary situation

Lieto fine (problema del)

Geometria  Problemi  Vari 

Il problema del lieto fine merita il suo nome perché almeno due coppie di matematici si sono sposate dopo aver lavorato su di esso.

 

Paul Erdös e George Szekeres dimostrarono nel 1935 che per un qualsiasi numero n > 2, esiste un numero g(n) tale che un insieme di punti del piano costituito almeno da g(n) punti, tali che non ve ne siano 3 sulla stessa retta, deve per forza comprendere un sottoinsieme di n, che siano ai vertici di un n-agono convesso.

Il problema consiste nel determinare g(n); i due matematici dimostrarono che g(n) ≥ 2n – 2 + 1 e supposero che questo sia il valore di g(n), ma al momento questa congettura è stata dimostrata solo per n < 7.

 

Al momento si sa che Limiti inferiore e superiore per g(n), ma il valore di g(n) è noto solo in 4 casi:

  • è ovvio che g(3) = 3;

  • Esther Klein dimostrò negli anni ’30 che g(4) = 5;

  • Esther Klein dimostrò nel 1935 che g(5) > 8 e poco dopo Endre Makai dimostrò che g(5) = 9;

  • nel 2006 L. Peters e Szekeres dimostrarono che g(6) = 17.

 

Il problema è in un certo senso più semplice se si ricerca il minimo numero di punti tra i quali se ne possano sempre scegliere n per formare un n-agono convesso e vuoto, cioè che non contenga altri punti dell’insieme. Più semplice, perché la ricerca è limitata ai primi valori di n: nel 1983, infatti, J.D. Horton costruì insiemi con un numero grande a piacere di punti che non possono costituire ettagoni convessi e vuoti; vale a dire che in tali insiemi ogni sottoinsieme di 7 (o più) punti costituisce i vertici di un poligono che o non è convesso, o non è vuoto.

Dato che 3 punti qualsiasi costituiscono i vertici di un triangolo vuoto, il problema si pone solo per n = 4, 5 e 6, vale a dire per quadrilateri, pentagoni ed esagoni.

E’ facile vedere che bastano 5 punti per un quadrilatero e H. Harboth dimostrò nel 1978 che bastano 10 punti per un pentagono.

Il problema resta aperto solo per l’esagono; nel 2007 Carlos M. Nicolás dimostrò che ogni insieme di almeno g(25) punti contiene un esagono convesso e vuoto e nel 2008 Tobias Gerken dimostrò che bastano min(g(9), 1718) punti. Il numero di punti è maggiore di 29, perché Mark Overmars el 2003 costruì un insieme di 29 punti senza esagoni convessi e vuoti.

 

Il teorema di Erdös e Szekeres si generalizza facilmente a qualsiasi dimensione maggiore di 2: in d dimensioni ogni insieme abbastanza grande di punti, tali che non ve ne siano 3 allineati, 4 sullo stesso piano ecc., contiene un politopo convesso con n vertici, per qualsiasi valore di n maggiore di d. Sul numero minimo di punti g(d, n) però si sa ben poco; è facile vedere che g(d, n) ≤ g(d – 1, n), e in particolare g(d, n) ≤ g(n); Granko Grünbaum dimostrò nel 2003 che g(d, d +2) ≤ d + 3.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.