II gara a squadre UNIMI- Quesito 5

[Boll]

Lo posto qui più che altro per una ragione estetica, con la geometria a parer mio c'entra ben poco...

Fissiamo $ n $ punti su una circonferenza e tracciamo tutte le possibili corde aventi come estremi gli $ n $ punti. Supponiamo che non ci siano $ 3 $ corde passanti per uno stesso punto interno al cerchio. Determinare il numero delle regioni in cui viene suddiviso il cerchio dalle corde.

[enomis_costa88]

Sia $ f(n) $ il numero di regioni presenti tracciate tutte le corde possibili tra n punti.
Trovo facilmente $ f(0)=1 $
Sia $ f(n+1)=f(n)+g(n+1) $.

Essendo tracciate tutte le corde possibili sarà disegnato pure l’n-agono inscritto alla circonferenza.
Definisco $ d(P_1,P_2) $ il numero di lati dell’n-agono inscritto alla circonferenza che bisogna percorrere per andare da $ P_1 $a $ P_2 $ in senso orario.

Considero una corda che parta da $ P_n $ e arrivi a $ P_i $;
Tra $ P_n $ e $ P_i $ sono compresi (estremi esclusi) $ d(P_n;P_i)-1 $ punti in senso orario (che chiamo punti rossi) e $ n- d(P_n;P_i)-1 $ in senso antiorario (che chiamo punti gialli).
Voglio ora sapere quante nuove regioni crea la corda tra $ P_n $ e $ P_i $.
Da ognuno dei $ d(P_n;P_i)-1 $ punti rossi parte una corda verso ciascuno dei $ n- d(P_n;P_i)-1 $ punti gialli .
La corda tra $ P_n $ e $ P_1 $ intersecherà solamente e tutte queste corde (inoltre abbiamo supposto che per ogni corda ci sia un’intersezione differente).
Coloro di verde i punti delle intersezioni tra $ P_n $ e le corde che collegano i punti rossi e ai punti gialli, chiamo questi punti $ V_i $ (numerandoli in base alla distanza con $ P_n $: $ V_1 $ il più vicino ecc).
La nuova corda disegnata divide in due parti la regione che attraversa andando da $ P_n $ a $ V_1 $.
Ma ciò vale anche in generale: la nuova corda disegnata divide in due parti la regione che attraversa andando da $ V_i $ a $ V_{i+1} $ e da $ V_k $ a $ P_i $ (dove $ V_k $ è l’intersezione più distante da $ P_n $).
Il nuovo numero di regioni create risulta quindi essere uguale al numero di intersezioni create più uno.
Il numero di intersezioni create è uguale al numero di corde che vanno dai punti rossi ai punti gialli ovvero: $ (d(P_n;P_i)-1)(n- d(P_n;P_i)-1) $
da cui posso ricavare il numero di nuove regioni aggiunte da un n-esimo punto.
$ g(n)= \sum_{i=1}^{n-1}(d(P_n;P_i)-1)(n- d(P_n;P_i)-1)+1) $

Suppongo di numerare i vertici in senso orario.
Allora per arrivare dal punto $ P_n $ al punto $ P_d $ bisogna percorrere $ d $ lati in senso orario.
Quindi $ d(P_n;P_d)=d $ (e posso semplificarmi la vita con g(n)).

$ \displaystyle g(n)= \sum_{d=1}^{n-1}(d-1)(n- d-1)+1) $
= $ \displaystyle \sum_{d=1}^{n-1} (-n+2+dn-d^2) $
$ \displaystyle = (n-1)(2-n)+n (\sum_{d=1}^{n-1} d)-(\sum_{d=1}^{n-1} d^2) $
= $ \displaystyle (n-1)(2-n)+n(\frac{(n-1)n}{2})-\frac{(n-1)n(2n-1)}{6} $ $ \displaystyle =\frac{n^3-6n^2+17n-12}{6} $
da cui la relazione ricorsiva:

$ \displaystyle f(n)= \frac{n^3-6n^2+17n-12}{6}+f(n-1) $
$ \displaystyle =f(0)+ \frac{1^3-6*1^2+17*1-12}{6}+\frac{2^3-6*2^2+17*2-12}{6} $+…+ $ \displaystyle \frac{n^3-6n^2+17n-12}{6} $
$ \displaystyle = 1+\frac{(\sum_{i=1}^{n} i^3)- 6 (\sum_{i=1}^{n} i^2)+17(\sum_{i=1}^{n} i)-12n}{6} $
$ \displaystyle = 1+ \frac{(\frac{n(n+1)}{2})^2-6(\frac{(n+1)n(2n+1)}{6}+17(\frac{n(n+1)}{2})-12n}{6} $
$ \displaystyle =\frac{n^4-6n^3+23n^2-18n+24}{24} $