Dopo lungo tempo, sono tornato!
Supponiamo di avere una circonferenza e di segnare su di essa n punti. Tracciamo tutti i segmenti del piano, interni alla circonferenza, che hanno per estremi questi punti. Sia R(n) il numero di regioni che si vengono a creare. Si ha cosi' R(0)=R(1)=0, R(2)=2, R(3)=4, R(4) = 8. Calcolare R(50).
Buona giornata ed in bocca al lupo ai maturandi!
Catraga.
Partizioni della circonferenza
3527?
In formula chiusa dovrebbe essere:
$ R\left(n\right)=\frac{3\left(n-2\right)\left(n-1\right)}{2}-1\quad \forall n \in \mathbb{N} \mid n \geq 5 $
Ovviamente il granchio è in agguato...
In formula chiusa dovrebbe essere:
$ R\left(n\right)=\frac{3\left(n-2\right)\left(n-1\right)}{2}-1\quad \forall n \in \mathbb{N} \mid n \geq 5 $
Ovviamente il granchio è in agguato...
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Sicuro? A me, guardando il disegno, risulta R(5) = 16 e R(6) = 31, che non vengono con la tua formula.moebius ha scritto:3527?
In formula chiusa dovrebbe essere:
$ R\left(n\right)=\frac{3\left(n-2\right)\left(n-1\right)}{2}-1\quad \forall n \in \mathbb{N} \mid n \geq 5 $
Ovviamente il granchio è in agguato...
Io sono arrivato ad un altro risultato, mooolto meno bello a vedersi (simpatico polinomio di quarto grado), da cui esce R(50) = 231526.
Se confermate scrivo per benino la dimostrazione.
Devo anche aggiungere il fatto che i punti sono scelti in modo da rendere MASSIMO il numero di regioni che si vengono a creare (questo equivale al fatto che non vi sono mai tre segmenti concorrenti in un punto). Vedo che nessuno ha sollevato obiezioni, quindi immagino sia una cosa ovvia.
Lo scopo intrinseco del problema non e' dare il risultato esatto, ma il metodo per calcolarlo.
Comunque, a meno di ciofeche, il risultato e' dell'ordine di 10^5
Lo scopo intrinseco del problema non e' dare il risultato esatto, ma il metodo per calcolarlo.
Comunque, a meno di ciofeche, il risultato e' dell'ordine di 10^5
Cio' mi rincuora. Allora partiamo:Catraga ha scritto:Comunque, a meno di ciofeche, il risultato e' dell'ordine di 10^5
Osservazione uno
In una circonferenza in cui sono tracciati segmenti in questo modo, se tracciamo un nuovo segmento che interseca $ n $ segmenti preesistenti, allora questo crea $ n+1 $ nuove regioni del cerchio.
Primo step
Supponiamo di avere gia' $ n $ punti ($ A_1,A_2,...,A_n $) numerati in senso orario per comodita' e di aggiungere il successivo $ A_{n+1} $ nell'arco $ A_nA_1 $.
Connettendo il nuovo punto con un punto $ A_k $, il segmento che si forma divide il cerchio in due regioni ed interseca tutti i segmenti che hanno i loro due estremi in regioni diverse. In una regione si trovano i punti $ A_1,A_2,...,A_{k-1} $, che sono $ k-1 $ e nell'altra i punti $ A_{k+1},A_{k+2},...,A_n $, che sono $ n-k $.
Quindi i segmenti che intersecano $ A_{n+1}A_k $ sono $ (k-1)(n-k) $ e, per l'Osservazione uno le nuove regioni che si formano sono $ (k-1)(n-k) + 1 $.
Se ripetiamo il procedimento con ugnuno dei punti $ A_1,A_2,...,A_n $, in totale le nuove regioni sono:
$ $$\displaystyle{\sum_{k=1}^{n} ((k-1)(n-k) + 1) = \sum_{k=1}^{n} (k(n+1) - k^2 -n +1) = }$$ $ $ \frac{n^3 - 3n^2 + 8n}{6} $.
Quindi $ R(n+1) = R(n) + \frac{n^3 - 3n^2 + 8n}{6} $ per n intero con $ n \geq 2 $.
Secondo step
Adesso, fissato $ R(2) = 2 $, basta rompere la ricorsione.
Detto $ H(n) = \frac{n^3 - 3n^2 + 8n}{6} $, si avra'
$ R(n+1) = R(n) + H(n) $
e quindi
$ R(n) = R(2) + \sum_{k=2}^{n-1} H(k) $ e, dopo un po' di conti,
$ R(n) = \frac{(n-2)(n^3 - 4n^2 + 15n + 12)}{24}+2 $.
Da qui, infine, $ R(50) = 231526 $
Ciao,
Loth