Newsgroup: it.hobby.enigmi
Titolo: quante regioni

Poniamo n punti su di una circonferenza, ed uniamoli tra loro con tutte le
possibili n*(n-1)/2 corde. Supponendo che mai tre corde si incontrano in un
punto, in quante diverse regioni viene suddiviso il cerchio? Per n=3 sono 4
regioni, il triangolo e le tre calotte.
Ciao, Silv:o)

 wrote in message
8r5l46$gn8hf$1...@ID-49224.news.cis.dfn.de...

Ne vengono fuori 2^(n-1), mi pare.
Ciao
et

 regioni, il triangolo e le tre calotte.
per n=4, 8 regioni: quadrilatero con due diagonali; 4 triangoli + 4
calotte
per n=5, 16 regioni: stella a cinque punte; 5 punte, 5 triangoli tra le
punte, 5 calotte e 1 pentagono centrale
a questo punto
n  regioni
3   4
4   8
5  16
verrebbe la tentazione di...
:-)
invece graficamente trovo che
n  regioni
6  31
facile da verificare graficamente, difficile da descrivere senza la
figura.
Non trovo una formula soddisfacente, ma ho un metodo ricorsivo.
Supponiamo di aver fatto il lavoretto completo per n punti, con r_n
regioni;
piazziamo il punto n+1 e tracciamo le n nuove corde.
Se una corda nuova ne interseca z preesistenti, si creano z+1 nuove
regioni;
e facile vederlo considerando che la corda risulta divisa in z+1
segmenti, e ciascun segmento divide in due una regione esistente.
Allora, la generica corda (n+1)_(k) divide la circonferenza in due
archi, che contengono rispettivamente (k-1) ed (n-k) punti. Tutte le
corde che uniscono un punto del primo arco con un punto del secondo
intersecano la nuova corda, per cui tale corda genera (k-1)*(n-k)+1
nuove regioni.
Quindi le nuove regioni attribuibili al punto (n+1) risultano
sum ((k-1)*nk)+1) [per k da 1 ad n]
e le regioni complessive
r_(n+1)=r_n + sum((k-1)*nk)+1) [per k da 1 ad n]
calcolando a mano trovo
n   regioni
6   31
7   57
e per proseguire si potrebbe scrivere un programmino; a mano mi rifiuto.
:-)
ciao
paolo
Sent via Deja.com 
http://www.deja.com/
Before you buy.



regioni, il triangolo e le tre calotte.
Ciao Silvio, il numero di regioni R(n) individuato da n punti dipende
da R(n-1) e dalle nuove intersezioni che si hanno aggiungendo
l'n-esimo punto agli n-1 gia' presenti. Ad esempio, dato un pentagono
ABCDE, aggiungendo un punto F nell'arco AE, si ha:
la corda FA non interseca corde di ABCDE ma forma una nuova calotta;
la corda FB dell'esagono ABCDEF interseca 3 corde di ABCDE formando 4
nuove regioni;
la corda FC ne interseca 4, formando 5 nuove regioni
....
In generale, dato un n-agono con n dispari, esso avra' in piu'
(rispetto al n-1 agono) il numero di regioni
n-1 + 2*[(n-3) + (n-4)*2 + (n-5)*3 + ... + ((n-1)/2)*((n-3)/2)] =
(n^3 - 6 n^2 + 17 n - 12)/6
mentre per n pari si ha 
n-1 + 2*[(n-3) + (n-4)*2 + (n-5)*3 + ... + (n/2)*(n/2-2)] + (n/2-1)^2
= (n^3 - 6 n^2 + 17 n - 12)/6, lo stesso di sopra.
In conclusione, 
R(n) = R(n-1) + (n^3 - 6 n^2 + 17 n - 12)/6 con R(2)=2: 
una funzione ricorsiva che (volendo) si puo' mettere in forma chiusa.
Ciao

 r_(n+1)=r_n + sum((k-1)*nk)+1) [per k da 1 ad n]
si e' perso qualche carattere; la formula corretta e'
r_(n+1)=r_n + sum((k-1)*(n-k)+1) [per k da 1 ad n]


 una funzione ricorsiva che (volendo) si puo' mettere in forma chiusa.
(n^4 - 6 n^3 + 23 n^2 - 18 n + 24) / 24
La maniera piu` compatta per scrivere questa formula e`:
R(n) = sum {(k=0,..,4) C(n-1,k)} ovvero i primi 5 termini della riga n-1 del
triangolo di Pascal (o tutta la riga, per gli n piccoli, e cio` spiega le
potenze di due).
Si puo` dimostrare facilmante per induzione, anche sfruttando la tua formula
ricorsiva che puo` essere riscritta come
R(n) = R(n-1) + C(n-1,1) + C(n-1,3)
R(n) = C(n-2,0)+C(n-2,1)+C(n-2,2)+C(n-2,3)+C(n-2,4) + C(n-1,1) + C(n-1,3)
R(n) = C(n-1,0)+     C(n-1,2)    +    C(n-1,4)      + C(n-1,1) + C(n-1,3)
La spiegazione di Conway e Guy, pur essendo semplice, ha bisogno di figure
altrimenti ci si perde. Si basa sul fatto che ogni regione puo` essere
etichettatta con una stringa di al piu` 4 simboli diversi scelti tra quelli
che individuano i vertici, per cui in totale le regioni sono tante quante le
stringhe di 0,1,2,3 o 4 simboli scelti tra n-1 (uno dei vertici ha un ruolo
particolare). Se c'e` qualche curioso posso postare la tecnica di
associazione regione-etichetta, ma senza figure richiedera` qualche sforzo.