I 10 prigionieri

[Brancaleone1]

A 10 prigionieri viene data l'opportunità di essere scarcerati: viene spiegato loro che saranno disposti uno davanti all'altro su una gradinata con un cappello in testa di colore bianco oppure nero, in modo che tutti possano vedere solo i cappelli di coloro che sono posizionati più in basso (quindi il prigioniero più in alto vedrà 9 cappelli, quello sotto di lui 8 e così via). Il numero dei cappelli bianchi e neri è assolutamente casuale (potrebbero essercene 7 bianchi e 3 neri, come 10 neri e nessun bianco), così come l'ordine nel quale saranno distribuiti. Tutti coloro che indovineranno il colore del proprio cappello verranno rilasciati seduta stante, mentre chiunque non indovini resterà dentro. Le regole da seguire sono semplici:

*il primo ad essere interrogato sarà quello in cima, il secondo quello sotto di lui e così via;
*il prigioniero interrogato può rispondere soltanto "bianco" oppure "nero", non può dire altro;
*sulla gradinata non è concesso di voltarsi né di comunicare tra loro in alcuna maniera;
*ai prigionieri è concesso prima di essere disposti sulla gradinata di organizzarsi su come procedere, da come preferiscono essere disposti lungo la gradinata a come costruire un sistema che permetta loro di aiutarsi nei limiti delle regole, dato che tutti possono ascoltare le risposte degli altri.

I prigionieri si guardano bene dall'infrangere le regole perché le guardie, perfette ed infallibili, giustiziano sul posto eventuali trasgressori. I prigionieri sono molto affiatati tra loro e convengono che il primo interrogato darà come risposta il colore di quello che gli sta subito davanti, in modo che questi sentito il colore risponda correttamente, il terzo poi farà la stessa cosa del primo a favore del quarto e così via, portando alla sicura liberazione 5 detenuti; le posizioni saranno estratte a sorte.

Esiste tuttavia un sistema migliore che permette di scarcerarne con sicurezza ben 9 su 10. Qual è?

[Rigel1]

Diciamo che il decimo prigioniero è sacrificabile e funziona da bit di parità

[nino_12]

E' un quiz piuttosto noto.

Ovviamente occorre mettersi d'accordo sulla strategia.
L'ultimo della fila (il primo che deve parlare) dice ad esempio "nero" se fra tutti gli n-1 cappelli che vede, la somma dei neri è dispari e dice "bianco" se è pari.
Ovviamente, ha solo il 50% di probabilità di indovinare il colore del suo cappello, però questa informazione consente a tutti gli altri di indovinare il colore del loro cappello.
Basta infatti che a loro volta contino i cappelli neri di chi sta loro davanti e confrontino se questo numero è pari o dispari con la risposta precedente di quello che sta loro dietro.

Anziché sulla somma pari o dispari di un colore, ci si può mettere d'accordo anche sul resto della divisione della somma Mod 2.
Ad es., il primo a parlare dice "nero" se il resto Mod 2 è 0 e dice "bianco" se è 1.
Gli altri, facendo la stessa operazione e confrontando con la risposta precedente, si regolano di conseguenza.

Con questa procedura, facendo Mod 3, Mod 4, ecc... è possibile indovinare per tutti i prigionieri meno uno, il colore del loro cappello anche quando si abbiano 3, 4 o più colori.

Ciao
Nino