2 Problemi di calcolo combinatorio

[DamianoY]

Il primo problema che voglio proporvi è preso dalla GaS 2012 (semifinale A problema 16), il secondo mi è stato proposto a un campus di matematica che si è svolto quest'estate ad Assisi.

Primo problema:
Nonostante tutte le profezie, il mondo finirà in realtà per la diffusione nei prossimi mesi di un virus che annienterà quasi completamente gli esseri umani. Il virus è composto da 8 dischetti complanari identici legati tra di loro ad anello. Ciascun dischetto ha una faccia ricca di plutonio e una ricca di arsenico. Il virus può mutare ribaltando uno o più dei dischetti scambiandone quindi le facce. C’è bisogno di un vaccino specifico per ogni diversa configurazione del virus, ma si tenga presente che un vaccino funziona anche se l’intero virus cambia posizione rigidamente, ruotando attorno al centro dell’anello o ribaltandosi completamente. Quanti diversi vaccini dovranno preparare i pochi superstiti per debellare il virus?
(Lasciando perdere il risultato che è 22, qual' è la strategia migliore da adottare durante una gara a squadre per risolverlo? Fosse stata una gara individuale invece? Premetto che sono riuscito a farlo solo a "tentativi")

Secondo problema:
(Non ho il testo sotto mano, ma ricordo che chiedeva questo)
Dato un poligono di n lati:
1-Quante sono le diagonali? (Questo direi che è banale)
2-Quanti sono i punti di intersezione delle diagonali, sapendo che comunque ne prendo 3 esse non sono concorrenti? (Anche questo è piuttosto semplice)
3-In quante aree viene suddiviso il poligono dalla sue diagonali (sempre a 3 a 3 non concorrenti)?
(Di questo problema sono riuscito ad arrivare solo ad una formula ricorsiva, ho tentato di scriverla in maniera diretta, solo in funzione di n, ma non ci riesco)

Spero di essere stato chiaro e che possiate togliere i miei dubbi! Grazie mille a tutti in anticipo!

[GimmyTomas]

Rispondo al problema del poligono.
1) $ \displaystyle d=\frac{n(n-3)}{2} $.
2) Ogni quaterna di vertici determina una intersezione, quindi $ \displaystyle i=\binom{n}{4}. $
3) Propongo un procedimento abbastanza semplice e non ricorsivo che si basa su una specie di double counting del numero di intersezioni. Consideriamo un vertice $ V $ e tracciamo le diagonali che partono da esso, supponiamo di farlo in senso orario. Indichiamo con $ j $ il numero di vertici strettamente compresi tra $ V $ e il vertice corrispondente all'altro estremo della diagonale, contando in senso orario. A questo punto, si vede facilmente che il numero di intersezioni su una diagonale $ j $ è $ j(n-j-2) $, quindi il numero totale di intersezioni sulle diagonali che partono da $ V $ è $ \displaystyle q=\sum_{j=1}^{n-3} j(n-j-2) $. Moltiplicando $ q $ per $ n $ abbiamo il numero totale di intersezioni di diagonali, ma moltiplicato per 4 (perché contiamo due volte ogni diagonale e due volte ogni intersezione). Quindi $ \displaystyle nq=4\binom{n}{4} $, cioè $ q=\displaystyle\frac{4}{n}\binom{n}{4} $.
Adesso, supponiamo di voler contare il numero $ S'' $ di segmenti in cui viene divisa ogni diagonale: esso è il numero di intersezioni più 1. Quindi, per una diagonale $ j $, $ S''=j(n-j-2)+1 $. Per un vertice $ V $, allora, il numero totale di segmenti è $ \displaystyle S'=\sum_{j=1}^{n-3} (j(n-j-2)+1)=n-3+q=n-3+\frac{4}{n}\binom{n}{4} $. Invece, per tutto il poligono, il numero totale di segmenti $ S $ in cui vengono divise le diagonali è (il fratto due è per non contare due volte le diagonali) $ \displaystyle S=S'\cdot\frac{n}{2}=\frac{n^2}{2}-\frac{3}{2}n+2\binom{n}{4} $. Per la formula di Eulero per i solidi, applicata al grafo con vertici nei vertici del poligono e nelle intersezioni delle diagonali e con archi nei lati e nei segmenti in cui le diagonali sono divise dalle intersezioni, $ f+v=s+2 $. Qui, $ f=F+1 $, dove $ F $ è il numero cercato, $ \displaystyle v=i+n=\binom{n}{4}+n $, $ s=S+n $. Riscriviamo la formula: $ \displaystyle F+\binom{n}{4}+n=\frac{n^2}{2}-\frac{n}{2}+2\binom{n}{4}+1 $, da cui $ \displaystyle F=\frac{n^2}{2}-\frac{3}{2}n+\binom{n}{4}+1 $.

[karlosson_sul_tetto]

Inoltre è praticamente un problema abbastanza noto (e passato sul forum non troppo tempo fa): http://en.wikipedia.org/wiki/Dividing_a ... into_areas

[DamianoY]

Grazie GimmyTomas, spiegazione perfetta! Non ero riuscito a trovare questo problema ne su internet n'è in particolare nel forum, anche se l' ho cercato per un bel po' di tempo!
Grazie anche a karlosson_sul_tetto per il link di wikipedia!
Era da almeno una settimana che cercavo di risalire alla formula, trovata la ricorsiva non sapevo più dove mettere le mani!
Quindi a questo punto solo per curiosità vorrei sapere se è possibile arrivarci in maniera semplice e mi è sfuggito qualcosa, oppure è molto più complesso..

Grazie ancora, stava diventado quasi un assillo per me!