Hi, gentaglia!
Vi propongo il seguente problema.
Fissiamo un numero intero positivo n.
Supponiamo di avere 2n nani.
Poniamo in testa a ciascun nano un cappello, che puo' essere di colore rosso o blu.
Il colore del cappello e' determinato in maniera casuale, tirando una moneta per ciascun nano.
Supponiamo che ciascun nano possa vedere i cappelli di tutti gli altri nani, ma non il proprio, e che i nani non possano comunicare tra di loro.
Ogni nano scrive segretamente su di un foglietto un colore, cercando di indovinare il colore del proprio cappello.
Infine si leggono i foglietti, e i nani che hanno sbagliato ad indovinare vengono uccisi.
Prima di mettere i cappelli, i nani si erano messi d'accordo per una qualche strategia con cui decidere i colori.
1) Trovare una strategia che salva sempre almeno n nani, indipendentemente dalla distrubuzione dei cappelli.
2) Fissiamo una strategia.
Si chiede se sia vero che in media (sulle possibili distribuzioni di cappelli) si salvano n nani, indipendentemente da quale sia la strategia usata (in tal senso, non ci sarebbero strategie "migliori" di altre).
3) Supponiamo che i nani ricevano meno informazioni: incece di vedere di che colore e' il cappello di ogni altro nano, sappiano solo il numero di cappelli rossi e di cappelli blu in testa agli altri nani.
Trovare una strategia che, anche in questo caso, salva sempre almeno n nani.
4) Generalizzare al caso di k colori ed n nani.
Per chiarezza, esempi di strategie possibili sono:
a) ogni nano scrive sempre rosso.
b) ogni nano dice che il proprio cappello e' dello stesso colore della maggioranza dei cappelli che vede.
c) il primo nano dice sempre rosso, gli altri decidono tirando una moneta.
d) il primo nano dice sempre rosso, gli altri il colore del cappello che vedono in testa al primo (tale strategia non e' valida nel caso 3).
