Numero di intersezioni fra rette

[rafz123]

Supponiamo di avere $ n $ punti nel piano a tre a tre non allineati. Le rette passanti per questi punti sono $ ( (n), (2) ) $ . Quante sono al massimo le intersezioni di queste rette?

Io ero tentato nel calcolarle come combinazioni delle rette trovate a due a due, ovvero come $ N= ( (( (n), (2) ) ), (2) ) $ intersezioni. Mi sono però reso conto che la soluzione non è questa, in quanto per ognuno degli n punti scelti all'inizio passano esattamente $ n-1 $ rette "annullando" le intersezioni che avremmo se tali rette non passassero per lo stesso punto. Si deve quindi sottrarre alle $ N $ intersezioni prima trovate il numero di intersezioni contate in più. Dato che ho per $ n-1 $ rette al massimo $ ( (n-1), (2) ) $ intersezioni, devo togliere questo numero di intersezioni moltiplicato per il numero dei punti che avevo all'inizio, cioè devo togliere a $ N $ il numero $ n* ( (n-1), (2) ) $. A questo punto però mi chiedo, non vanno aggiunti nuovamente i punti che ho "tolto" eliminando tutte le possibili intersezioni fra le $ n-1 $ rette passanti per uno degli $ n $ punti che avevo all'inizio? Se così fosse, il risultato dovrebbe essere:

$ N=( (( (n), (2) ) ), (2) ) -n*( (n-1), (2) ) +n $

Avendo svolto questo esercizio nel caso di n=6, mi sono reso conto che mi trovo il risultato (pari a $ 45 $ ) solo se non includo $ n $ nel calcolo, ma non riesco a capire concettualmente il perché. Scusate per la formulazione forse molto contorta, e grazie in anticipo a chi risponderà

[Bokonon]

"Raff_321":Supponiamo di avere $ n $ punti nel piano a tre a tre non allineati. Le rette passanti per questi punti sono $ ( (n), (2) ) $ . Quante sono al massimo le intersezioni di queste rette?

Fin qua è ok

"Raff_321":Avendo svolto questo esercizio nel caso di n=6, mi sono reso conto che mi trovo il risultato (pari a $ 45 $ ) solo se non includo $ n-1 $ nel calcolo, ma non riesco a capire concettualmente il perché. Scusate per la formulazione forse molto contorta, e grazie in anticipo a chi risponderà

Ma esattamente come hai ottenuto quel 45? Per tentativi sul foglio?
E' per caso un compito assegnato a casa?

[rafz123]

Ho comprato un libro di calcolo combinatorio per esercitarmi per le olimpiadi di matematica e questo è uno degli esercizi. Il testo dell'esercizio è: "Dati 6 punti del piano, a 3 a 3 non allineati, quante rette si ottengono congiungendoli 2 a 2? Quanti sono, al massimo, i punti di intersezione di queste rette?" Io ho risolto l'esercizio in questo caso particolare ma ho provato a generalizzare il risultato supponendo di avere non 6 punti nel piano ma n punti, con le stesse identiche richieste. In ogni caso ciò che non mi viene nel problema per n=6 è il numero di intersezioni fra le rette, che secondo la formula trovata dovrebbe essere pari a 51 e non a 45 (soluzione riportata dal libro), motivo per cui volevo sapere cosa c'era di sbagliato nel procedimento adottato, che ho riportato nel caso generico e non in quello particolare dell'esercizio

[Bokonon]

Ci ho pensato su perchè all'inizio ero giunto a una conclusione completamente sballata.
La prima considerazione che ho fatto è stata che gli n punti sono tutti centri di fasci composti da (n-1) rette.
La seconda considerazione è che, a due a due, nessuna retta deve essere parallela.

Il modo più semplice per giungere alla soluzione IMHO è considerare un solo fascio di rette, quindi un solo punto.
La logica è che ogni retta del fascio di un punto generico P, attraversa un solo altro degli n punti (che ignoriamo) e poi inciderà le rimanenti rette. Quante sono? Sono tutte le rette passanti per i rimanenti (n-2) punti, ovvero $C(n-2,2)$. Per P passano (n-1) rette, quindi incideranno (unicamente) un totale di $(n-1)C(n-2,2)$ rette.

Sommando i punti iniziali (centri dei fasci) si ottiene un totale di intersezioni uniche pari a
$T=(n-1)C(n-2,2)+n=[(n-1)(n-2)(n-3)]/2+n$

$n=3 rArr 3$
$n=4 rArr 7$
$n=5 rArr 17$
$n=6 rArr 36$
$n=7 rArr 67$
etc. etc.

Il risultato del libro non mi torna
Tu come hai risolto il caso n=6?

[axpgn]

Io avrei ragionato così …

In generale, ogni volta che viene tracciata una retta nel piano, questa interseca una sola volta tutte le altre già presenti, quindi se ci sono già $r$ rette nel piano, la $r+1$-esima aggiungerà $r$ intersezioni, le quali in totale saranno $(r(r+1))/2$

Perciò dati $n$ nel punti nel piano, non più di due sulla stessa retta, congiungendoli tutti tra loro avremo $r=((n),(2))$ rette.
Ed in generale avremo $t=(r(r-1))/2$ intersezioni.

Questo è vero se in ogni punto concorrono solo due rette ma nel nostro caso non è così; in ognuno dei punti solo le prime due rette formano una nuova intersezione, quelle che arrivano dagli altri punti non aggiungono niente, né al punto considerato (quello di arrivo), né a quello di partenza.

Quindi al numero $t$ vanno sottratte un certo numero di intersezioni, vediamo quante …

La prima retta che passa da uno dei punti dati non crea intersezioni, la seconda ne crea uno, la terza ne creerebbe due ma coincidono col precedente quindi niente, la quarta idem, ecc.
Quindi in ognuno dei punti dati ci sarebbero teoricamente $((n-2)(n-1))/2$ intersezioni che invece non esistono tranne una.
Di conseguenza vanno sottratte $(n(n-1)(n-2))/2-n$ intersezioni da $t$

Esempio:

$n=5$
$r=10$
$t=45$

$T=45-(5*4*3)/2+5=20$

Ci sono tutte e solo quelle, le ho contate

IMHO

Cordialmente, Alex

[Bokonon]

Bravo Alex!
Io non le ho contate e ho immaginato solo il caso n=4 e bastava un fascio.
Vanno invece inserite anche le intersezioni dei fasci successivi con (n-1), (n-2),..., 3 punti.
Ponendo $K_n=(n-1)C(n-2,2)=1/2(n-1)(n-2)(n-3)$ si ha la sequenza:
$K_3=0$
$K_4=3$
$K_5=12$
$K_6=30$
$K_7=60$
etc. etc.

$T_n=n+sum_(n=3)^n K_n$
Perciò:
$T_3=3+0=3$
$T_4=4+3=7$
$T_5=5+15=20$
$T_6=6+45=51$
$T_7=7+105=112$
etc. etc.