Pagina 1 di 1
diagonali e parti
Inviato: 15 giu 2018, 12:57
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.
Re: diagonali e parti
Inviato: 18 giu 2018, 10:58
da TheRoS
Hai usato anche tu la formula di Eulero ($v-e+f=2$) per generalizzarlo?
Re: diagonali e parti
Inviato: 18 giu 2018, 11:54
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.
Re: diagonali e parti
Inviato: 18 giu 2018, 15:34
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).
Re: diagonali e parti
Inviato: 19 giu 2018, 17:36
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$.
Re: diagonali e parti
Inviato: 19 giu 2018, 19:18
da Giuseppe M.
Per il caso generale distinguo tra poligoni con $n$ pari e dispari.
Caso $n$ dispari.
Caso $n$ pari.