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.
diagonali e parti
Re: diagonali e parti
Hai usato anche tu la formula di Eulero ($v-e+f=2$) per generalizzarlo?
-
- Messaggi: 17
- Iscritto il: 19 ott 2009, 17:46
Re: diagonali e parti
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
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.
-
- Messaggi: 17
- Iscritto il: 19 ott 2009, 17:46
Re: diagonali e parti
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$.
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$.
-
- Messaggi: 17
- Iscritto il: 19 ott 2009, 17:46
Re: diagonali e parti
Per il caso generale distinguo tra poligoni con $n$ pari e dispari.
Caso $n$ dispari.
Caso $n$ pari.
Caso $n$ dispari.
Testo nascosto:
Testo nascosto: