enigma dei 10 condannati a morte

[jitter]

Anni fa mi ero scervellata diversi giorni su questo problema divertente che ho ritrovato in internet. Non mi ricordo la soluzione e sto cercando di ricostruirla...
Ecco l'enigma:

Ci sono 10 condannati a morte in fila uno dietro l'altro su una gradinata.
Ognuno ha un cappello, bianco o nero.
I condannati non possono girarsi e quindi ognuno può vedere soltanto quelli che ha davanti (quindi quello più in alto sulla scalinata vedrà 9 persone davanti, il secondo 8 e così via).
A ognuno, partendo da quello più in alto, verrà chiesto: "Di che colore hai il cappello?".
Chi indovina avrà salva la vita, altrimenti... caput!
Tutti possono sentire le risposte degli altri, ma non possono parlare tra loro.
I condannati possono però organizzarsi prima dell'inizio del gioco, per studiare un sistema che permetta loro di aiutarsi a vicenda.
Così i 10 decidono dopo vari ragionamenti che il primo di tutti a rispondere, quello che sarà in alto, darà come risposta il colore di quello che gli sta davanti, così il secondo saprà la risposta giusta e si salverà di sicuro. Il terzo poi farà la stessa cosa del primo per salvare il quarto. In questo modo tutti quelli in posizione pari si salveranno certamente, mentre lo stesso non si può dire di quelli in posizione dispari.
Il boia, sentendo la loro idea, suggerisce che esiste un altro sistema, migliore, che permetterebbe di salvareDANNATI con sicurezza, invece che 5, ben 9 condannati
Qual è questo sistema?

Mettete testo nascosto nè!

[Palliit]

Ciao. Ci provo:

Testo nascosto, fai click qui per vederlo

il primo in alto dice "bianco" se il numero dei 9 cappelli che vede è pari, "nero" se è dispari. A seconda del destino di questo condannato, il secondo saprà qual è la risposta giusta: contando i cappelli bianchi che restano davanti a lui, sa di che colore dev'essere il suo, e via di seguito i successivi (che dovranno tener conto ovviamente del colore dichiarato da ciascuno dei condannati che stavano alle loro spalle). Così l'unico che rischia è il primo.

[Gaussman]

e se avessimo i cappelli di n possibili colori??

[jitter]

Bravo Palliit!!!

Quello che mi avevano fatto anni fa, allora, era un altro, simile ma la soluzione era diversa e più complessa, ci avevamo pensato diversi giorni. Mi piacerebbe ritrovarlo, adesso chiedo al mio amico se se lo ricorda e ve lo propongo.

@Gaussman: con n colori dici che è possibile una strategia, dato che la "logica" è binaria (vero/falso - bianco/nero, MA vero/falso - bianco/nero/rosso)?

[UmbertoM]

E' per caso il primo dei problemi a questo link, quello che avevi fatto anni fa?
http://www.liceodaponte.com/public/Lanc ... 478030.pdf

[jitter]

Non mi sembra. Mi ricordo che i colori dei cappelli erano bianco/nero e l'idea generale del ragionamento, ma questa non la dico perché se lo trovo ve lo propongo!

[Gaussman]

@Gaussman: con n colori dici che è possibile una strategia, dato che la "logica" è binaria (vero/falso - bianco/nero, MA vero/falso - bianco/nero/rosso)?

in realtà noi non usiamo tanto la logica, quanto il fatto che il numero sia pari/dispari... una strategia esiste e non è troppo dissimile dal caso n=2 come idea, provate a trovarla

[milizia96]

Per $n>5$ penso vada bene la strategia pensata dai condannati, che salva comunque almeno $5$ persone.

Per $n<=5$ si potrebbe fare così:
$C_1,..C_n$ sono gli $n$ colori.
Il primo condannato conta quanti sono i cappelli di colore $C_1$ davanti a lui: se sono in numero pari pronuncia "$C_1$!", altrimenti dice "$C_n$!". Da questo momento tutti conoscono la parità del numero di cappelli di colore $C_1$.
Dal secondo condannato in poi si procede così: se il condannato di turno conosce il colore del proprio cappello, tanto vale dire proprio quello e salvarsi la vita: i condannati successivi si accorgeranno comunque che la sua affermazione non aveva come obiettivo quello di informare della parità di un certo colore, poiché questa era già nota.
Se invece le informazioni a disposizione non sono sufficienti per determinare il colore del proprio cappello, il condannato dovrà comunicare agli altri, così come aveva fatto il primo condannato, la parità del colore $C_i$, con $i$ minimo possibile, di cui non si conosce ancora la parità.
Ah, ovviamente il modo per risalire al colore del proprio cappello è come quello proposto da Palliit: contando i colori davanti a sé si stabilisce quale delle parità note non è soddisfatta, che corrisponde al colore del proprio cappello.
Se tutte le parità coincidono, e si conoscono le parità dei primi $n-1$ colori, allora il proprio cappello ha colore $C_n$.
Se tutte le parità coincidono, ma si conoscono meno di $n-1$ parità, non è possibile risalire al colore del proprio cappello.

In pratica, con $n<=5$ colori, vengono uccisi al massimo $n-1$ condannati.

Ma chissà, ci potrebbe essere una strategia più efficace (e magari più semplice )

[jitter]

Procedendo analogamente al Palliit's method:

Il primo condannato dice:
- $C_1$ se il numero dei cappelli bianchi è 3k
- $C_2$ se il numero dei cappelli bianchi è 3k + 1
- $C_3$ se il numero dei cappelli bianchi è 3k + (i - 1).

Funziona? Mi sembra che in questo modo si salvino 11 - n condannati, a meno che non ho sbagliato tutto perché mi incarto continuamente su questo groviglio di "se" e ho stracciato un sacco di fogli .

@Milizia: complimenti, è una strategia bella e complessa. La cosa che mi incuriosisce è che alla fine anche con il tuo metodo il risultato è: "uccisi n - 1", ovvero "salvi 11 - n": eppure le strategie sono diverse! Che storia. E se alla fine le due strategie coincidessero? O forse è una casualità?

[kira9921]

parto dal presupposto che in base all'idea avuta dai condannati si può perfettamente capire l'ordine in cui sono disposti i cappelli,ovvero 1 bianco,1nero,1bianco e così via fino a dieci(funziona anche se si inizia col.nero poi bianco via dicendo)e dico qst semplicemente perchè i condannati avevano intenzione di dire il colore del cappello di quello che segue,così facendo si sarebbero salvati solo quelli in posizione pari ovvero 2 4 6 8 10 e posso affermare che i colori fossero alternati perchè se ci fossero stati due cappelli dello stesso colore vicini questo nn si sarebbe potuto verificare,ora abbiamo il nostro boia buono che vedendo la situazione può semplicemente consigliare a quellinin posizione dispari di dire lo stesso colore (nel nostro primo caso bianco)e lo stesso per i pari (in qst caso nero)e vi dirò che così non salverebbero in 9 ma si salverebbero tutti e visto che il nostro boia ha detto che sicuramente 9 si salveranno ma non ha detto la fine del decimo questa soluzione può essere valida allegherei uno schema se ci riuscissi xD