n punti, una retta

[L'ale]

Siano dati n punti nel piano, con la proprietà che presi comunque due di essi ne esiste un terzo giacente sulla retta passante per i primi due.
Dimostrare che allora tutti gli n punti stanno sulla stessa retta.

[pa]

proviamo per induzione:
per $ n=3 $ e' evidente che i tre punti sono su un unica retta un quanto i primi 2 definiscono un'unica retta e il terzo quindi deve stare su quella retta' per la proprieta'.
aggiungiamo un punto P a un sistema di n-1 punti tutti sulla stessa retta mantenendo la proprieta' del problema: prendiamo in esame questo punto piu' un altro A preso a caso tra gli n-1. deve esistere un punto B sulla retta di AP appartenente agli n-1. quindi la retta di AP e' la stessa di AB che per ipotesi e' la stessa di tutti gli n-1 punti.

[salva90]

proviamo per induzione:
per $ n=3 $ e' evidente che i tre punti sono su un unica retta un quanto i primi 2 definiscono un'unica retta e il terzo quindi deve stare su quella retta' per la proprieta'.
aggiungiamo un punto P a un sistema di n-1 punti tutti sulla stessa retta mantenendo la proprieta' del problema: prendiamo in esame questo punto piu' un altro A preso a caso tra gli n-1. deve esistere un punto B sulla retta di AP appartenente agli n-1. quindi la retta di AP e' la stessa di AB che per ipotesi e' la stessa di tutti gli n-1 punti.

è il classico esempio di quando l'induzione fallisce: non è possibile indurre sulle configurazioni

[L'ale]

e allora come si può risolvere?

[pic88]

Beh, supponiamo che non stiano tutti su una stessa retta. Esiste un minimo tra i valori non nulli che misurano la distanza tra un punto ed una retta che appartenga alla configurazione (cioè che passi per 2 degli n punti). Poi si fanno un po' di osservazioni e si deduce che quello non poteva essere il minimo, e si conclude.

[pic88]

Ah, il motivo per cui non funziona l'induzione è che dati n punti che soddisfano le ipotesi, non è detto che un sottoinsieme fatto da n-1 punti ancora le soddisfi...

[pa]

proviamo per induzione:
per $ n=3 $ e' evidente che i tre punti sono su un unica retta un quanto i primi 2 definiscono un'unica retta e il terzo quindi deve stare su quella retta' per la proprieta'.
aggiungiamo un punto P a un sistema di n-1 punti tutti sulla stessa retta mantenendo la proprieta' del problema: prendiamo in esame questo punto piu' un altro A preso a caso tra gli n-1. deve esistere un punto B sulla retta di AP appartenente agli n-1. quindi la retta di AP e' la stessa di AB che per ipotesi e' la stessa di tutti gli n-1 punti.

è il classico esempio di quando l'induzione fallisce: non è possibile indurre sulle configurazioni

Scusa ti puoi chiarire meglio? in particolare non ho capito perche' l'induzione fallisce in questo caso...

[pic88]

.
aggiungiamo un punto P a un sistema di n-1 punti tutti sulla stessa retta mantenendo la proprieta' del problema:

Il fatto è che l'ipotesi induttiva non dice "un insieme di n-1 punti è fatto di punti allineati", bensì "un'insieme di n-1 tali che nessuna retta ne contenga esattamente 2 è fatto di allineati"... ora, se tu parti da un insieme di n punti, chi ti dice che togliendone 1 ne restino altri n-1 con quella proprietà?

P.S: non riesco a trovare il link alla discussione che tempo fa c'è stata su questo problema

[mod_2]

P.S: non riesco a trovare il link alla discussione che tempo fa c'è stata su questo problema

Se non ricordo male nella lezione "Preliminari" del Senior dell'anno scorso si è parlato di questo problema...

[EvaristeG]

si chiama teorema di sylvester e, tra corsi e ricorsi storici, è stato un argomento di questo forum diverse volte, è stato spesso citato come esempio di cattiva induzione, è stato anche nel test di ammissione sns per l'anno 2004/2005, mi pare.
La soluzione giusta è già stata un po' troppo stringatamente esposta ed è quella di considerare la minima distanza tra le coppie punto retta.

[WiZaRd]

Posso dire che io continuo a non capire perché l'induzione non funziona?
Il principio di induzione dice di assumere che l'asserto sia valido per $ n $ e poi provare che è vero per $ n+1 $... sono confuso: cos'è che mi impedisce di assumere che l'asserto vero per $ n $?

[julio14]

Qual è la tua tesi? che ogni configurazione di n+1 punti tali che ogni retta congiungente due punti contiene almeno 3 punti, ha tutti i punti su una retta. Hai come ipotesi che questo è vero per n. Quando puoi applicare l'induzione? quando a partire dalle configurazioni di n punti che rispettano le ipotesi, aggiungendo un punto, puoi raggiungere tutte le configurazioni di n+1 che rispettano le ipotesi. Allora ovviamente l'induzione funziona. Il problema è che questa cosa non è così scontata: infatti presa una configurazione di n+1 punti che rispetta le ipotesi, non è detto che, tolto un punto P qualunque, troviamo una configurazione che rispetta le ipotesi: magari P stava su una retta con esattamente 3 punti, quindi tolto P quella retta ha solo 2 punti. Ma se la configurazione di n punti che abbiamo trovato non rispetta le ipotesi, allora i punti non stanno tutti su una retta, e quindi ovviamente neanche gli n+1 punti vi stanno.

[WiZaRd]

Qual è la tua tesi? che ogni configurazione di n+1 punti tali che ogni retta congiungente due punti contiene almeno 3 punti, ha tutti i punti su una retta. Hai come ipotesi che questo è vero per n. Quando puoi applicare l'induzione? quando a partire dalle configurazioni di n punti che rispettano le ipotesi, aggiungendo un punto, puoi raggiungere tutte le configurazioni di n+1 che rispettano le ipotesi. Allora ovviamente l'induzione funziona. Il problema è che questa cosa non è così scontata: infatti presa una configurazione di n+1 punti che rispetta le ipotesi, non è detto che, tolto un punto P qualunque, troviamo una configurazione che rispetta le ipotesi: magari P stava su una retta con esattamente 3 punti, quindi tolto P quella retta ha solo 2 punti. Ma se la configurazione di n punti che abbiamo trovato non rispetta le ipotesi, allora i punti non stanno tutti su una retta, e quindi ovviamente neanche gli n+1 punti vi stanno.

Non capisco: se per ipotesi prendiamo una configurazione di $ n $ punti che rispetta le ipotesi, perché dopo non le rispetta più?
E il principio di induzione non mi dice di aggiungere un punto? Perché dagli $ n $ punti togli un punto, non dovresti aggiungerlo?

Chiedo scusa se le domande vi sembrano deficienti, ma veramente non vi seguo...

[julio14]

L'induzione in realtà non ti dice di aggiungere un punto a partire da n, ma ti dice: se, a partire da n+1, tolto un punto, la configurazione rispetta le ipotesi, allora essa rispetta anche la tesi, e rimettendo il punto si nota che anche la configurazione a n+1 deve rispettare la tesi. Il problema è che, tolto un punto, non è detto che la configurazione a n rispetti le ipotesi.

[WiZaRd]

Ma io non devo assumere come ipotesi induttiva il fatto che la configurazione a $ n $ rispetti le ipotesi?

Voglio dire, quando provo che $ [tex] $\sum_{i=1}^{n}i=\frac{n(n+1)}{2}$, nella dimostrazione del passo induttivo, io assumo come ipotesi induttiva la validità della formula per $ n $. Quì tu mi dici che da $ n+1 $ punti che rispettano le ipotesi se ne tolgo uno non ho la sicurezza che le ipotesi siano rispettate, ma l'ipotesi induttiva non mi dice proprio che per $ n $ (e cioè tolto quel punto) l'asserto è buono?

P.S.
Io intanto vado a nanna. Grazie per la disponibilità e scusami per il tempo che ti porto via con queste domande. Buona notte.