Quadrilateri nel piano

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

Testo nascosto, fai click qui per vederlo

Pensavo di dimostrarlo per induzione, che ne pensi?

Testo nascosto, fai click qui per vederlo

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

Testo nascosto, fai click qui per vederlo

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

Testo nascosto, fai click qui per vederlo

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.

Testo nascosto, fai click qui per vederlo

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.

Testo nascosto, fai click qui per vederlo

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.

Ultima modifica di sprmnt21 il 10/10/2015, 07:30, modificato 1 volta in totale.

un altro modo potrebbe essere questo:

Testo nascosto, fai click qui per vederlo

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.

un altro modo potrebbe essere questo:

Testo nascosto, fai click qui per vederlo

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...

Si, esatto

@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.