Nani numerabili e cappelli

[Vincent46]

Un'infinità numerabile di nani è disposta in fila indiana, di modo che ognuno abbia di fronte la schiena del successivo. Quindi, ogni nano ne ha un altro sia di fronte che dietro di sé, eccetto il primo, che non ha nessuno dietro di sé. Ogni nano ha in testa un cappello, che può essere bianco o nero. Ognuno può vedere i cappelli dei nani di fronte a sé, ma non il proprio, né quello di chi gli sta dietro.
Ogni nano viene interrogato sul colore del proprio cappello, a partire da quello che sta dietro a tutti, e procedendo uno per volta, verso la testa della fila infinita. Chi indovina si salva, chi sbaglia muore. È noto che i nani hanno udito perfetto, e possono sentire le risposte di chiunque li abbia preceduti, non importa quanto indietro nella fila. Le risposte possibili sono solo "bianco" o "nero".
Prima di essere messi in fila, i nani hanno avuto possibilità di parlare fra loro e di elaborare una strategia.
Se voi foste uno di loro, che strategia proporreste per minimizzare le perdite?

Nota per i pignoli: I nani sono esseri superiori e trascendono le limitazioni fisiche degli umani. Possono, ad esempio, memorizzare una quantità infinita di informazioni e svolgere conti dalla complessità computazionale infinita.

[axpgn]

Hai detto che hanno un udito finissimo ma quant'è lunga la loro vista?

Testo nascosto, fai click qui per vederlo

Penso che possa funzionare una variante della strategia con un numero finito di nani (o prigionieri)
I nani suddividono la fila in blocchi da $n+1$ con $n$ dispari.
Il primo di ogni blocco dice il colore che risulta dispari tra gli $n$ cappelli che ha davanti, in tal modo chi gli sta davanti può capire di che colore è il suo cappello così come gli altri dello stesso blocco ricostruendo ogni volta la situazione.
In tal modo le perdite (eventuali) sono una ogni $n+1$ nani

Cordialmente, Alex

[Vincent46]

Hai detto che hanno un udito finissimo ma quant'è lunga la loro vista?

Testo nascosto, fai click qui per vederlo

Penso che possa funzionare una variante della strategia con un numero finito di nani (o prigionieri)
I nani suddividono la fila in blocchi da $n+1$ con $n$ dispari.
Il primo di ogni blocco dice il colore che risulta dispari tra gli $n$ cappelli che ha davanti, in tal modo chi gli sta davanti può capire di che colore è il suo cappello così come gli altri dello stesso blocco ricostruendo ogni volta la situazione.
In tal modo le perdite (eventuali) sono una ogni $n+1$ nani

Cordialmente, Alex

Non sai che i nani hanno risoluzione infinita?

Testo nascosto, fai click qui per vederlo

Questa è ok, ma... si può fare di meglio?

[3m0o]

Certo che si può fare di meglio...

Testo nascosto, fai click qui per vederlo

Solo il primo nanetto ha una probabilità di $ \frac{1}{2} $ di morire dopodiché tutti gli altri hanno la certezza di indovinare il colore del proprio cappello!

[Vincent46]

Certo che si può fare di meglio...

Testo nascosto, fai click qui per vederlo

Solo il primo nanetto ha una probabilità di $ \frac{1}{2} $ di morire dopodiché tutti gli altri hanno la certezza di indovinare il colore del proprio cappello!

Con quale strategia?

[thedarkhero]

La mia proposta dovrebbe funzionare per un insieme finito di nani.

Testo nascosto, fai click qui per vederlo

L'ultimo nano della fila (cioe' il primo che viene interrogato) rispondera' 'bianco' se il numero di cappelli bianchi che vede davanti a se' e' pari, rispondera' 'nero' altrimenti: cosi' facendo avra' probabilita' pari a $1/2$ di morire ma avra' messo in salvo tutti gli altri nani.
Infatti, il penultimo nano potra' dedurre con certezza il colore del suo cappello vedendo tutti i cappelli davanti a se' e sapendo se i cappelli bianchi che possiedono lui e tutti i nani che ha davanti sono pari o dispari (grazie alla risposta data in precedenza dall'ultimo nano).
Lo stesso fara' ciascun altro nano.

Sono pero' curioso di sapere come ci si potrebbe comportare nel caso proposto da Vincent, ovvero quando i nani sono un'infinita' numerabile...

[Vincent46]

Hint per il caso numerabile:

Testo nascosto, fai click qui per vederlo

Utilizzare l'assioma della scelta!

[Drazen77]

Io arrivo a salvarne il 75%.
Si può fare di meglio? Come?

[crisz96]

Considerando che i nani sono infiniti numerabili, possiamo considerare che i cappelli neri abbiano valore 1 e i cappelli bianchi abbiano valore 0.

Il primo nano fa lo XOR di tutti i cappelli che ha di fronte, dice "bianco" se lo XOR ha come risultato 0 e "nero" se ha come risultato 1. In questo modo, ha il 50% di probabilità di sopravvivere in quanto il colore del suo cappello è indipendente dal colore dei cappelli tutti gli altri.

Il secondo nano, fa lo XOR di tutti i cappelli che ha di fronte, con il risultato ottenuto fa lo XOR con la risposta del nano che lo precedeva, in questo modo può dire con certezza il colore del proprio cappello.

Così via per tutti i nani! Considerando che sono infiniti e che ne perdiamo solo mezzo (infilandoci un po' di logica fuzzy), alla fine ne avremo salvato il 100%.

Chiedo scusa a tutti i matematici che non sanno cos'è lo XOR è un operatore binario molto caro a noi informatici.
Qua riporto una tabella:

XOR

Op. 1	Op. 2	Risultato
0	0	0
0	1	1
1	0	1
1	1	0

Se ho tempo dopo lo riporto sotto formalismo matematico

[axpgn]

... mmm ... so cos'è l'XOR ma come funziona su un numero infinito di istanze? (se funziona ...)