Quadrilateri e Pentagoni

[axpgn]

Quanti punti, come minimo, sono necessari affinché disponendoli sul piano in un modo qualsiasi (escludendo quelli con più di due punti allineati), sia sempre possibile formare un quadrilatero convesso?
E quanti necessitano, come minimo, per poter sempre formare un pentagono convesso?
Dimostrazione?

Cordialmente, Alex

[orsoulx]

Il primo quesito ha una facile risposta: bastano cinque punti.
Per la dimostrazione basta considerare l'inviluppo convesso dei cinque punti, se questo ha quattro vertici abbiamo il quadrilatero cercato, se ne ha cinque basta eliminare uno qualsiasi dei punti, se ne ha solo tre i restanti due saranno interni al triangolo e la retta cui appartengono lascia due vertici del triangolo in un semipiano e uno nell'altro; eliminando quest'ultimo il problema è risolto.
Per il secondo ci penserò, a naso direi sei o sette.

Ciao

[Vincent46]

edit: ho sbagliato

[axpgn]

Per il quadrilatero: ok, (io l'ho pensata come orsoulx)

Per il pentagono: non va bene ...

[Vincent46]

"axpgn":Per il quadrilatero: ok, (io l'ho pensata come orsoulx)

Per il pentagono: non va bene ...

È vero! Sono stato troppo frettoloso.

Penso che con questa costruzione si possano trovare otto punti senza pentagoni convessi:

1. i primi quattro punti li prendo come vertici di un quadrilatero convesso;
2. considero le semirette che partono da un punto $P$ interno al quadrilatero e passanti per i suoi vertici, con $P$ non appartenente alle sue diagonali;
3. gli ultimi quattro punti li prendo uno su ciascuna di queste quattro semirette, tutti esterni al quadrilatero di partenza.

[axpgn]

@Vincent46
Ricordati di mettere sotto spoiler le tue idee ...

Difatti, $8$ punti non sono sufficienti, un controesempio "semplice" è quello formato dagli otto vertici di due rettangoli "concentrici" ma che NON hanno le diagonali in comune.

Cordialmente, Alex

[orsoulx]

@Alex,
perdonami se non sono intervenuto prima, ma ripensando al problema mi ero ricordato di averlo già incontrato e di averne vista la soluzione... e poi, col passar del tempo, non tutti i matrimoni risultano felici
Ciao

[axpgn]

Se conosci la dimostrazione per i pentagoni rendi felici anche noi
So quanti punti necessitano ma diversamente dai quadrilateri non riesco a dimostrarlo ...

Cordialmente, Alex

[orsoulx]

"axpgn":rendi felici anche noi

lo farei volentieri, ma non conosco la dimostrazione in questione. Mi imbattei in questo problema quando internet non offriva ancora le risorse attualmente disponibili. Adesso ho provato a fare una ricerca con "problema del lieto fine", tanto in inglese quanto in francese ci sono trattazioni ben esposte, ma prive della dimostrazione. Bisognerebbe risalire agli articoli linkati, ma non ne ho voglia.
Ciao

[axpgn]

La questione è decisamente molto più seria di quello che pensavo
Ho provato a fare qualche ricerca anch'io, non ho trovato la dimostrazione per il pentagono ma quella per l'esagono sì
A questo link c'è una soluzione per l'esagono convesso, trovata al computer però.
Per quanto riguarda i pentagoni, nel documento si afferma questo:

"... At the time when the conjectures (Pk) and (Qk) were proposed they seemed to be a hazardous extrapolation from a few trivial and not very convincing cases, but a few years later Makai and Turan verified that indeed 9 points always contain a convex pentagon. As far as we know this proof has never appeared in print but some of us who knew of its existence saw in it modest support for the belief that (Pk) is true for all k. (See Morris and Soltan [7], Kalbfleisch etal. [5] and Bonnice [1] for proofs for 9 points.) Many years later Erdos and Szekeres [4] produced an explicit example of 2k~2 points which contained no convex k-gon, thereby confirming the truth of (Qk) for all k > 1. This construction showed at any rate that no(k) > 2k~2. For recent results on the upper bound for no(k) see Toth and Valtr [8]. ..."

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Ecco la dimostrazione per il pentagono:

Io ho trovato (non è mia) questa dimostrazione, non so se è la dimostrazione originale.
Notazione:
Dato un insieme finito \(K\) di punti nel piano di cardinalità \( \left| K \right| \) abbiamo che \( (k_1,\ldots,k_j)\) denota la seguente affermazione:
\( \left| K \right| = k_1 + \ldots + k_j \) e l'inviluppo convesso di \(K\), denotato \( \operatorname{conv} K \), è un poligono a \(k_1\) vertici, e quando i vertici di \( \operatorname{conv} K \) sono tolti da \(K\), l'inviluppo convesso dei punti rimanenti è un poligono a \(k_2\) vertici, e così via.

Lemma: Se un insieme planare \(K\) è \( (3,3,2) \), \( (4,3,1) \) oppure \((3,4,2)\), allora \(K\) determina un pentagono convesso.

(La dimostrazione del Lemma la aggiungo quando avrò più tempo)

Denotiamo con \(r(5) \) il numero cercato di punti

Teorema: \( r(5)=9\)
Dato un insieme di \(9\) punti in posizione generale che non determina un pentagono convesso, allora ha una delle seguenti forme \( (4,4,1), (4,3,2),(3,4,2) \) oppure \( (3,3,3)\). Nei primi due casi abbiamo un sottoinsieme di \(8\) punti che è \( (4,3,1)\) e negli ultimi due casi abbiamo un sottoinsieme di punti che è \((3,3,2)\), il lemma precedente si applica e abbiamo dimostrato che \(r(5) \leq 9 \).
Per l'altra direzione è sufficiente trovare un esempio di insieme con \(8\) punti che non possiede un pentagono convesso, ad esempio i vertici di un quadrato dentro i vertici di un altro quadrato centrati nello stesso punto.

Con un metodo analogo si può dimostrare che \( r(6) = 17 \), che oltre a \( r(3)=3\) e appunto \(r(4)=5 \) e \( r(5)=9 \) sono gli unici numeri conosciuti di questo problema.