Ancora nanetti e cappelli.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

7 nanetti vengono rapiti. La strega cattiva gli mette in testa dei cappelli neri o bianchi con probabilità 1/2. Ciascun nanetto vede il colore dei cappelli di tutti gli altri ma non il proprio!
I nanetti dopo aver visto i cappelli di tutti, e senza poter comunicare in alcun modo tra loro, dovranno scrivere su un foglietto personale una delle seguenti tre cose: "Nero", "Bianco" oppure "Non lo so".
I nanetti si salvano se: Almeno un nanetto indovina il proprio colore e nessun nanetto sbaglia il proprio colore.
I nanetti muoiono se: Almeno un nanetto sbaglia il proprio colore oppure se scrivono tutti "non lo so".

Trovare una strategia tale per cui i nanetti si salvano a meno che tutti i cappelli non siano bianchi.

[axpgn]

Io l'ho letta ma ...

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Ma... che cosa ?

[axpgn]

Già alla prima riga ci ho messo un po' a capire perché se ci sono $2^n$ vertici allora i $v$ vanno da $1$ a $n$ (i $v$ sono le varie combinazioni di colori possibili).
Poi un altro bel po' per capire il significato della sommatoria (un arco esiste solo tra combinazioni che differiscono per un colore soltanto).
E altro tempo per capire che un nanetto, vedendo gli altri, sa su quale arco si trova ma non su quale estremo.
E questo solo per finire il primo paragrafo, figurati il resto

Ah, sia chiaro che è un mio problema, non la tua esposizione, che è fin troppo dettagliata (come sempre )

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Una domanda che mi sono fatto a cui non ho una risposta!

Chiamato con \(p(n)\) la probabilità ottimale con \(n \) nanetti è vero che \( \lim_{n \to \infty} p(n) = 1 \) ?
Se non è vero allora cosa vale \( \lim_{n \to \infty} p(n) \) ?

Sicuramente è vero che \(p(9)= \frac{225}{256} \leq \lim_{n \to \infty} p(n) \leq 1 \).
Infatti abbiamo che
\[ p(n) = \max \{ p(n-1), 1- \frac{g(n)}{2^n} \} \]
e questo è vero perché se succedesse che \( 1- \frac{g(n)}{2^n} < p(n-1) \), cosa che comunque non penso sia possibile, allora avremmo una strategia migliore ovvero dimenticare l'\(n\)-esimo nanetto, egli dice "non lo so", e gli altri si comportano come se sono \(n-1\) nanetti.
Pertanto essendo che \( p(2) \leq \ldots p(n-1) \leq p(n) \leq \ldots \leq 1 \) per ogni \(n \in \mathbb{N}\) ed essendo limitata abbiamo che esiste il limite.