diagonali e parti

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Giuseppe M.
Messaggi: 17
Iscritto il: 19 ott 2009, 17:46

diagonali e parti

Messaggio da Giuseppe M. »

Un esercizio dalla finale Bocconi di quest'anno chiedeva in quante parti, al massimo, un ottagono convesso può essere diviso dalle sue diagonali.
Per evitare ambiguità dico che il numero di parti in cui un quadrilatero è diviso dalle sue diagonali è 4, per un pentagono è al massimo 11.

Dopo la gara sono riuscito a risolvere l'esercizio ed anche a trovare una formula generale (credo) per un poligono di $n$ lati.
Vorrei confrontare le vostre soluzioni con la mia (anche perché la parte di geometria l'ho risolta ad occhio piuttosto che formalmente).
Posterò la mia procedura più avanti.
TheRoS
Messaggi: 30
Iscritto il: 25 feb 2018, 13:05

Re: diagonali e parti

Messaggio da TheRoS »

Hai usato anche tu la formula di Eulero ($v-e+f=2$) per generalizzarlo?
Giuseppe M.
Messaggi: 17
Iscritto il: 19 ott 2009, 17:46

Re: diagonali e parti

Messaggio da Giuseppe M. »

In realtà no. Ho appena visto come si dimostra quella formula, che finora avevo sentito nominare solo una volta in vita mia, e non vi avevo mai prestato attenzione.
TheRoS
Messaggi: 30
Iscritto il: 25 feb 2018, 13:05

Re: diagonali e parti

Messaggio da TheRoS »

Allora, premetto che devo fare ancora tutti i calcoli, ma per massimizzare le parti in cui viene diviso secondo me bisogna prendere i poligoni convessi che non hanno mai tre diagonali concorrenti. Una volta trovati i punti che si creano da tutte le intersezioni (i nodi del grafo), si possono trovare gli archi (sai che il grado dei vertici del poligono è $n-1$, mentre dei nodi interni è sempre 4) e poi si applica la formula di Eulero (tenendo conto che il risultato conterà la faccia costituita dal piano esterno al poligono).
Ultima modifica di TheRoS il 27 giu 2018, 21:16, modificato 1 volta in totale.
Giuseppe M.
Messaggi: 17
Iscritto il: 19 ott 2009, 17:46

Re: diagonali e parti

Messaggio da Giuseppe M. »

Grazie a queste nuove conoscenze teoriche sono riuscito a formalizzare meglio il calcolo.

Comincio dal caso dell'ottagono convesso.
Esso ha 8 diagonali di ordine 1, ovvero tali che un solo vertice dell'ottagono si trova da un lato della diagonale (ovviamente gli altri 5 vertici si troveranno dall'altro lato). Analogamente, ha 8 diagonali di ordine 2, e 4 diagonali di ordine 3.
Ciascuna diagonale di ordine 1 viene intersecata da altre 5 diagonali, formando cosi' 5 vertici interni e 6 spigoli interni al poligono. Le 5 diagonali sono quelle che partono dal vertice che si trova da solo da un lato della diagonale.
Ciascuna diagonale di ordine 2 viene intersecata da 2 gruppi di 4 diagonali che partono dai due vertici che si trovano da un lato della diagonale, formando cosi' 8 vertici interni e 9 spigoli interni al poligono.
Ciascuna diagonale di ordine 3 viene intersecata da 3 gruppi di 3 diagonali che partono dai due vertici che si trovano da un lato della diagonale, formando cosi' 9 vertici interni e 10 spigoli interni al poligono.
Il totale dei vertici interni sarà:
$
V_{i} = \frac{8*5+8*8+4*9}{2} = 70
$
La divisione per 2 è dovuta al fatto che ogni vertice è contato 2 volte, essendo intersezione di due diagonali.
Per gli spigoli interni invece:
$
S_{i} = 8*6+8*9+4*10 = 160
$
Se vogliamo calcolare il numero totale di vertici e spigoli basterà sommare 8 ad entrambi, dunque $V=78$ e $S=168$.
Per la formula di Eulero:
$
F = S-V+2 = 92
$
ma questo conteggio include l'area esterna al poligono, che non va conteggiata ai fini dell'esercizio.
Le regioni interne al poligono sono pertanto 91.

Notare che non era necessario calcolare $S$ e $V$, poichè $S-V = S_i - V_i$.
Giuseppe M.
Messaggi: 17
Iscritto il: 19 ott 2009, 17:46

Re: diagonali e parti

Messaggio da Giuseppe M. »

Per il caso generale distinguo tra poligoni con $n$ pari e dispari.

Caso $n$ dispari.
Testo nascosto:
$n=2m+1$
Conteggio dei vertici interni
$n$ diagonali di ordine 1: $n-3$
$n$ diagonali di ordine 2: $2*(n-4)$
$n$ diagonali di ordine 3: $3*(n-5)$
...
$n$ diagonali di ordine $m-1$: $(m-1)*(n-m-1) = (m-1)m$
Riscrivo gli stessi numeri in maniera diversa partendo dal fondo:
$(m-(m-1))(m+(m-2)) = m^2 - m - (m-2)(m-1)$
...
$(m-3)(m+2) = m^2 - m - 6$
$(m-2)(m+1) = m^2 - m - 2$
$(m-1)m = m^2 - m$
La somma dei termini in queste $m-1$ righe sarà quindi:
$ (m-1)m^2 - (m-1)m - \sum_{k=0}^{m-1} k(k-1) $
Ora mi concentro sulla sommatoria, calcolandola prima fino ad $m$ per usare facilmente le sommatorie note:
$ \sum_{k=0}^{m} k(k-1) = \sum_{k=0}^{m} k^2 - \sum_{k=0}^{m} k = \frac{m(m+1)(2m+1)}{6} - \frac{m(m+1)}{2} = \frac{m(m+1)}{2} \left ( \frac{2m+1}{3} - 1 \right ) = \frac{(m-1)m(m+1)}{3} $
Sostituendo $m-1$ al posto $m$:
$ \sum_{k=0}^{m-1} k(k-1) = \frac{(m-2)(m-1)m}{3} $
Andando a sostituire questo risultato nella somma dei termini delle varie righe:
$ (m-1)m^2 - (m-1)m - \frac{(m-2)(m-1)m}{3} = ... = \frac{2m^3 - 3m^2 + m}{3} $
Da cui il numero di vertici interni al poligono sarà:
$ V_i = \frac{2m+1}{2} \frac{2m^3 - 3m^2 + m}{3} = \frac{4m^4 - 4m^3 - m^2 + m}{6} $
Se si vuole il numero totale di vertici basta aggiungere i $2m+1$ vertici esterni:
$ V = \frac{4m^4 - 4m^3 - m^2 + 13m + 6}{6} $

Il calcolo degli spigoli è analogo. Basta ricordare che ogni riga di quelle scritte prima conterrà 1 spigolo in più rispetto ai vertici, e che non bisogna introdurre il fattore $1/2$.
$ S_i = (2m+1) \left [ \frac{2m^3 - 3m^2 + m}{3} + m-1 \right ] = ... = \frac{4m^4 - 4m^3 +5m^2 -2m -3}{3} $
$ S = \frac{4m^4 - 4m^3 + 5m^2 + 4m}{3} $

Il numero di regioni senza contare quella esterna al poligono sarà:
$ F' = S-V+1 = \frac{4m^4 -4m^3 + 11m^2 - 5m}{6} $
A questo punto sostituisco $m=(n-1)/2$ e ottengo:
$ F' = \frac{n^4 - 6n^3 + 23n^2 -42n +24}{24} = \frac{(n-2)(n-1)(n^2-3n+12)}{24} $
Caso $n$ pari.
Testo nascosto:
$n=2m$
Conteggio dei vertici interni:
Conteggio dei vertici interni
$n$ diagonali di ordine 1: $n-3$
$n$ diagonali di ordine 2: $2*(n-4)$
$n$ diagonali di ordine 3: $3*(n-5)$
...
$m$ diagonali di ordine $m-1$: $(m-1)*(n-m-1) = (m-1)^2$
Riscrivo gli stessi numeri in maniera diversa partendo dal fondo:
$(m-(m-1))(m+(m-3)) = m^2 - 2m - (m-3)(m-1)$
...
$(m-3)(m+1) = m^2 - 2m - 3$
$(m-2)m = m^2 - 2m$
$(m-1)(m-1) = m^2 - 2m + 1$
La somma dei termini di queste prime $m-1$ righe sarà quindi:
$ (m-1)m^2 -2m(m-1) - \sum_{k=0}^{m-1} k(k-2) $
Mi concentro sulla sommatoria, calcolandola prima fino ad $m$ per usare facilmente le sommatorie note:
$ \sum_{k=0}^{m} k(k-2) = \sum_{k=0}^{m} k^2 - 2 \sum_{k=0}^{m} k = \frac{m(m+1)(2m+1)}{6} - m(m+1) = \frac{m(m+1)(2m-5)}{6} $
$ \sum_{k=0}^{m-1} k(k-2) = \frac{(m-1)m(2m-7)}{6} $
Andando a sostituire questo risultato nella somma dei termini delle varie righe:
$ (m-1)m^2 -2m(m-1) - \frac{(m-1)m(2m-7)}{6} = ... = \frac{4m^3 - 9m^2 + 5m}{6} $
Da cui il numero di vertici interni al poligono sarà:
$ V_i = \frac{2m}{2} \frac{4m^3 - 9m^2 + 5m}{6} - \frac{m}{2} (m^2 - 2m + 1) = ... = \frac{4m^4 -12m^3 +11m^2 -3m}{6} $
La sottrazione è dovuta al fatto che il fattore moltiplicativo per l'ultima riga è la metà rispetto alle altre.
Se si vuole il numero totale di vertici basta aggiungere i $2m$ vertici esterni:
$ V = \frac{4m^4 -12m^3 +11m^2 + 9m}{6} $

Per gli spigoli risulta:
$ S_i = 2m \left ( \frac{4m^3 - 9m^2 + 5m}{6} + m-1 \right ) - m (m^2 - 2m + 2) = ... = \frac{4m^4 - 12m^3 + 17m^2 - 12m}{3} $
$ S = \frac{4m^4 - 12m^3 + 17m^2 - 6m}{3} $

Il numero di regioni senza contare quella esterna al poligono sarà:
$ F' = S-V+1 = \frac{4m^4 - 12m^3 + 23 m^2 - 21m + 6}{6} $
A questo punto sostituisco $m=n/2$ e ottengo:
$ F' = \frac{n^4 - 6n^3 + 23n^2 -42n +24}{24} = \frac{(n-2)(n-1)(n^2-3n+12)}{24} $
La stessa formula finale vale per $n$ pari e dispari.
Rispondi