Quadrilateri nel piano

[Pachisi]

Dati $n$ punti nel piano, a tre a tre non allineati, dimostrare che è possibile formare almeno \( \displaystyle \binom{n-3}{2} \) quadrilateri convessi.

[dan952]

Pensavo di dimostrarlo per induzione, che ne pensi?

[Pachisi]

Io ho fatto diversamente, anche perché non saprei come fare l'ipotesi induttiva. Vedi un po` che succede

[dan952]

"Pachisi":

Anche perché non saprei come fare l'ipotesi induttiva. Vedi un po` che succede

Si dimostra il caso $n=5$, poi supponiamo che valga per i primi $k$ naturali, aggiungiamo un punto e (per far tornare i conti) potremmo costruire almeno altri $n-3$ quadrilateri oltre ai $\frac{(n-3)(n-4)}{2}$ La spiegazione volutamente grossolana solo per rendere l'idea.

[Pachisi]

Cosa ti assicura che i nuovi quadrilateri che costruisci siano convessi?
Ora che ci penso meglio, qui potrebbe essere utile qualcosa che ho usato anche io.

[Sk_Anonymous]

Il numero \( \displaystyle \binom{n-3}{2} \) è uguale alla somma dei primi $n-4$ numeri naturali.
Immaginiamo di partire da 4 punti. In generale non avremo alcun quadrilatero convesso. Con 5 punti ne abbiamo almeno 1. Se ora aggiungiamo un sesto punto avremo avremo lo stesso numero minimo di quadrilateri con i primi 4 punti più almeno un altro mettendo in gioco il 5 punto. In generale al passo k+1-esimo aggiungendo il (k+5)-esimo punto, considerando solo i primi $k+3$ punti, aggiungeremo lo stesso numero $d_k$ di quadrilateri convessi aggiunti al passo k-esimo più almeno 1 considerando anche il punto (k+4)-esimo.
Quindi abbiamo un successione di differenze per cui vale la relazione $d_{k+1}=d_k+1$.
La successione base è quindi quella dei numeri triangolari che è equivalente all'espressione da provare.

[Sk_Anonymous]

un altro modo potrebbe essere questo:

Con 5 punti si ha almeno un quadrilatero convesso. Fisso tre dei punti dati. Per ogni coppia dei rimanenti n-3 punti con i 3 punti fissati ottengo almeno un Q C. Pertanto almeno C(n-3, 2) QC.

[dan952]

"sprmnt21":un altro modo potrebbe essere questo:

Con 5 punti si ha almeno un quadrilatero convesso. Fisso tre dei punti dati. Per ogni coppia dei rimanenti n-3 punti con i 3 punti fissati ottengo almeno un Q C. Pertanto almeno C(n-3, 2) QC.

Ecco questo avevo in mente di fare...

[Pachisi]

Si, esatto

[orsoulx]

@sprmnt21; dan95; pachisi:
la dimostrazione su cui avete trovato l'accordo mi pare almeno incompleta. Gli insiemi di 5 punti sono distinti, ma nulla garantisce che lo siano anche i QC trovati.
Io non riesco a formulare una dimostrazione non ricorsiva.

Ciao
B.

[Sk_Anonymous]

"orsoulx":@sprmnt21; dan95; pachisi:
la dimostrazione su cui avete trovato l'accordo mi pare almeno incompleta. Gli insiemi di 5 punti sono distinti, ma nulla garantisce che lo siano anche i QC trovati.
Io non riesco a formulare una dimostrazione non ricorsiva.

Ciao
B.

Toccato! [per quanto mi riguarda. [Magari gli altri sanno come superare la lacuna]]

Che ne dici dell'altra mia?

Ti convince?

[dan952]

Sia $P$ il punto aggiunto e prendiamo un punto $P_1$ tra gli $n$ punti, per i quali sotto ipotesi induttiva vale la proprietà, fissiamo poi 3 punti $A$, $B$, $C$ in modo che $ABP$ è un triangolo e $C$ un punto interno dunque con questi 4 punti non potremo costruire alcun quadrilatero convesso, abbiamo in tutto 5 punti per i quali sappiamo che è possibile costruire almeno un quadrilatero convesso che ha come vertice il punto $P_1$, successivamente prendiamo un altro punto $P_2$, con $P$, $A$, $B$, $C$ e $P_2$ possiamo costruire almeno un nuovo quadrilatero diverso dal precedente poiché $P_1!=P_2$ e così via fino al $P_{n-3}$ punto

[Pachisi]

@orsoulx:
In effetti hai ragione. Comunque, credo di esserci riuscito ora. La metto in spoiler:

Visto che per ogni 5 punti nel piano si può trovare un quadrilatero convesso, abbiamo $ ((n) , (5)) $ modi di scegliere 5 punti da $n$. Per ogni scelta abbiamo almeno un quadrilatero convesso. Ora, notiamo che ogni quadrilatero convesso può essere formato in $n-4$ delle possibili scelte di 5 punti. Allora, abbiamo almeno $\frac{((n) , (5))}{n-4}$ quadrilateri convessi distinti. Si dimostra facilmente che questo è maggiore o uguale di $((n-3) , (2))$, e quindi abbiamo finito.

[Sk_Anonymous]

"orsoulx":@sprmnt21; dan95; pachisi:
la dimostrazione su cui avete trovato l'accordo mi pare almeno incompleta. Gli insiemi di 5 punti sono distinti, ma nulla garantisce che lo siano anche i QC trovati.
Io non riesco a formulare una dimostrazione non ricorsiva.

Ciao
B.

allora il punto è che se detti P1, P2 e P3 i tre punti perno fisso le coppie CiCj che facciamo variare possono avere un punto in comune ovviamente e quindi in generale i QC ottenuto da P1P2P3CiCj e P1P2P3CiCk possono essere lo stesso quadrilatero.
Per evitare questa eventualità, si deve trovare il modo di assicurare per ogni cinquina che il QC abbia solo due dei Pi ed entrambi gli elementi della coppia CiCj.


PS
in effetti nei casi pratici su cui ho "ragionato" i QC sono molti di più di C(n-3,2), quindi c'è margine.

[orsoulx]

@pachisi:
l'ultima mi piace.

@dani85:
i QC potrebbero essere coincidenti P, A, B, C.

@sprmnt21:
non l'avevo guardata. Dovrei pensarci.

Ciao
B.

[dan952]

@orsoul
Credo che considerando P,A,B,C in modo che non possano formare un quadrilatero convesso il problema si risolve

[axpgn]

la x ...

[orsoulx]

@dan95:
mi pare che, con le modifiche apportate e aggiungendo l'eventualità che sia impossibile trovare i 3 opportuni punti, funzioni anche la tua.

Eviterei le modifiche sostanziali ai post, per due motivi:
a) chi ha già seguito la discussione, non trovando l'indicazione di interventi successivi alla sua ultima visita, non la legge più;
b) chi leggesse per la prima volta non ci capirebbe alcunché.

Come ti ha segnalato quel burlone di axpgn, il mio nick ha una x finale (deriva da un paese dell'alta Val di Susa)

Ciao
B.

[dan952]

Prima di modificare c'era scritto:

Mi sfugge qualcosa...

E Alex ha prontamente commentato con una battuta
Ero indeciso se modificare o no proprio per il motivo a)

[Sk_Anonymous]

"sprmnt21":
allora il punto è che se detti P1, P2 e P3 i tre punti perno fisso le coppie CiCj che facciamo variare possono avere un punto in comune ovviamente e quindi in generale i QC ottenuto da P1P2P3CiCj e P1P2P3CiCk possono essere lo stesso quadrilatero.
Per evitare questa eventualità, si deve trovare il modo di assicurare per ogni cinquina che il QC abbia solo due dei Pi ed entrambi gli elementi della coppia CiCj.
PS
in effetti nei casi pratici su cui ho "ragionato" i QC sono molti di più di C(n-3,2), quindi c'è margine.

forse c'è il modo di colmare la lacuna, con una opportuna scelta della terna perno.

[Sk_Anonymous]

si può fare così: si prendo P1, P2 e P3 tali che tutti gli altri punti stiano all'interno dell'angolo Infatti la retta CiCj dividerà l'angolo in due parti diu cui una conterrà due punti P1, Pk. I quattro punti sulle due rette formano necessariamente un quadrilatero convesso in quanto Ci, Cj stanno nello stesso semipiano dei due determinati dalla retta P1Pk e viceversa. Qualsiasi altra delle C(n-3,2) coppie formerà un quadrialetro convesso distinto dagli altri per almeno un punto.