Partizioni della circonferenza

[Catraga]

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.

[moebius]

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

[Loth]

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

Sicuro? A me, guardando il disegno, risulta R(5) = 16 e R(6) = 31, che non vengono con la tua formula.

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.

[Catraga]

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

[Loth]

Comunque, a meno di ciofeche, il risultato e' dell'ordine di 10^5

Cio' mi rincuora. Allora partiamo:

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

[Loth]

Allora, cosa ne dite?

[moebius]

A me convince... ho guardato la mia e c'era un baco enorme...
La tua mi convince