A proposito di cappelli...
Vi propongo un problema molto interessante che forse molti di voi già conoscono (date tempo a chi non lo sa di pensarci)
C'è un principe un po' fuori di testa che decide di mettere alla prova il suo consiglio formato da n saggi.
Va da loro e dice: "Vi metterò in testa cappelli di m colori differenti e vi disporrò in fila in modo che possiate vedere solo i cappelli delle persone che vi precedono, quindi il primo della fila non vedrà nessun cappello e l'ultimo vedrà tutti tranne il suo. Potrò scegliere i colori a mio piacimento, vi dico solo quali saranno gli m colori. Chiederò a ognuno di voi, dall'ultimo al primo, di che colore è il suo cappello e se non indovinerà gli sarà tagliata la testa. Domani mattina alle sei ci sarà questa prova per voi. Buonanotte."
I saggi ovviamente non chiudono occhio per tutta la notte...
L'indomani mattina n-1 saggi avranno salva la vita. E l'altro? Cosa ne sarà di lui?
Ma soprattutto, come hanno fatto a salvarsi gli n-1?
(N.B.:Il principe dice ai saggi esclusivamente quanti sono i colori e quali sono, ma poi l'indomani mattina può anche decidere di mettere a tutti un cappello di un solo colore tra quelli elencati la sera precedente!!!)
C'è un principe un po' fuori di testa che decide di mettere alla prova il suo consiglio formato da n saggi.
Va da loro e dice: "Vi metterò in testa cappelli di m colori differenti e vi disporrò in fila in modo che possiate vedere solo i cappelli delle persone che vi precedono, quindi il primo della fila non vedrà nessun cappello e l'ultimo vedrà tutti tranne il suo. Potrò scegliere i colori a mio piacimento, vi dico solo quali saranno gli m colori. Chiederò a ognuno di voi, dall'ultimo al primo, di che colore è il suo cappello e se non indovinerà gli sarà tagliata la testa. Domani mattina alle sei ci sarà questa prova per voi. Buonanotte."
I saggi ovviamente non chiudono occhio per tutta la notte...
L'indomani mattina n-1 saggi avranno salva la vita. E l'altro? Cosa ne sarà di lui?
Ma soprattutto, come hanno fatto a salvarsi gli n-1?
(N.B.:Il principe dice ai saggi esclusivamente quanti sono i colori e quali sono, ma poi l'indomani mattina può anche decidere di mettere a tutti un cappello di un solo colore tra quelli elencati la sera precedente!!!)
Risposte
Sei sicuro che quelli che si salvano sono $n-1$? Se i saggi sono $n$ vuol dire che tutti tranne $1$ al più si salvano di sicuro? Le cose non tornano...
Sicurissimo!!! 
Allora ti porto un controesempio:
Ipotizziamo che i colori sono $3$: blu, bianco, giallo. Ipotizziamo inoltre che il re mette a tutti un cappello blu.
Il saggio dietro a tutti vede che quelli che lo precedono hanno il cappello blu... ma come fa a essere sicuro che anche il proprio sia blu? E così anche il penultimo...
Ipotizziamo che i colori sono $3$: blu, bianco, giallo. Ipotizziamo inoltre che il re mette a tutti un cappello blu.
Il saggio dietro a tutti vede che quelli che lo precedono hanno il cappello blu... ma come fa a essere sicuro che anche il proprio sia blu? E così anche il penultimo...
Ora devo andare, pensateci... E domattina alle sei ci sarà il verdetto. Se ci tenete alla vostra testa, risolvete il problema. 
No, sto scherzando... Vado a dormire, è meglio!
No, sto scherzando... Vado a dormire, è meglio!
Kroldar i saggi hanno tutta la notte per pensare e possono pensare INSIEME. Ora vado sul serio.
Basta che l'ultimo dica il colore del cappello di quello che lo precede. In questo modo n-1 si salvano mentre l'ultimo può salvarsi o non salvarsi.
Cubalibre in questo modo si salvano solo n/2 saggi. Infatti se l'ultimo dice il colore del cappello del penultimo, il penultimo dice il suo colore, ma siamo punto e a capo con il terzultimo, che non sa il colore del suo cappello quindi, se iteri questo metodo... n/2.
E' chiaro che ognuno dei saggi ha una sola possibilità, cioè ognuno deve dire un solo colore, altrimenti l'ultimo potrebbe dire tutti i colori di quelli che lo precedono (prima di essere linciato dalle guardie del principe!!!).
Continua a pensare.
Miles Davis.
E' chiaro che ognuno dei saggi ha una sola possibilità, cioè ognuno deve dire un solo colore, altrimenti l'ultimo potrebbe dire tutti i colori di quelli che lo precedono (prima di essere linciato dalle guardie del principe!!!).
Continua a pensare.
Miles Davis.
"miles_davis":
Kroldar i saggi hanno tutta la notte per pensare e possono pensare INSIEME. Ora vado sul serio.
Ok non avevo capito il fatto che potessero accordarsi
Il primo saggio a essere interpellato dice il colore che è maggiormente presente tra quelli che ha davanti... i saggi si accordano su un ordine preciso da seguire qualora ci fosse un pari merito. Così tutti quanti dal secondo in poi si salvano. Il primo potrebbe salvarsi qualora gli capitasse il cappello del colore che ha detto, ma potrebbe anche finire male, l'esito è del tutto casuale...
Ma è un dato di fatto che l'indomani n-1 saggi si salvano... SEMPRE. E' evidente che la casualità non c'entra!!! Non sei su una strada sbagliatissima, è solo che devi pensare ancora. Ciao.
Scusa eh... ma dalla soluzione che ho proposto io $n-1$ si salvano di sicuro. Eventualmente potrebbero anche salvarsi tutti, ma questa evenienza dipende da una casualità. Ciò non toglie però che, a parte il primo, tutti gli altri a essere interpellati, dal secondo in poi, si salvano di sicuro.
Sì ma mi devi dire COME si sono messi d'accordo, e soprattutto il tuo metodo non fornisce una soluzione sicura. Come fai a essere sicuro che n-1 si salvano?
E soprattutto se quello che vede tutti dice il colore più frequente, aumenta solo la probabilità che gli altri si salvino. Immagina che sono 30 saggi e quello che vede tutti dice che il più presente è il blu, cioè dice blu. Potrebbe anche darsi che ci sono 2 blu e gli altri 27 (oltre a quello di colui che parla per primo) sono tutti di colori diversi. Come fai a salvare con certezza 29 saggi?
Sì hai ragione, la mia soluzione non sempre va bene...
Ogni saggio dovrebbe sommare l'informazione di tutte le risposte e di chi ha perduto la testa fino a quel punto per poter trarre una soluzione riguardo al suo cappello...
Però la strategia che hanno pianifikato la notte prima a naso sembra piuttosto complessa, o no?
Qualche caso da considerare c'è...
Ma sbaglio se considero che l'unico che puo lasciarci le penne è il primo?
Però la strategia che hanno pianifikato la notte prima a naso sembra piuttosto complessa, o no?
Qualche caso da considerare c'è...
Ma sbaglio se considero che l'unico che puo lasciarci le penne è il primo?
mettiamoci d'accordo su una numerazione in base m e associamo ogni cifra a un colore diverso. L'ultimo pronuncia il numero in tale base che rappresenta la codifica dei colori che vede davanti a se.
Per quanto riguarda la sua sorte, penso che possa contare su una probabilità su m di sopravvivere dopo aver fatto tutta quella fatica.
ciao
Per quanto riguarda la sua sorte, penso che possa contare su una probabilità su m di sopravvivere dopo aver fatto tutta quella fatica.
ciao
Leev hai ragione... Questi saggi sono molto saggi. Però non credo che le penne le lasci il primo.
mirco59 sei sulla buona strada (buonissima!!!), ma cosa intendi per "codifica dei colori"? Ricorda che ognuno può parlare solo in termini di colori, quindi l'ultimo può dire solo un colore (numero) tra quelli detti dal principe (quindi minore o uguale a m).
Credo che devi solo formalizzare meglio la tua soluzione.
mirco59 sei sulla buona strada (buonissima!!!), ma cosa intendi per "codifica dei colori"? Ricorda che ognuno può parlare solo in termini di colori, quindi l'ultimo può dire solo un colore (numero) tra quelli detti dal principe (quindi minore o uguale a m).
Credo che devi solo formalizzare meglio la tua soluzione.
ma quindi la disposizone con cui vengono messi i cappelli ai saggi è completamente a random, giusto?
Si può utilizzare il concetto di parità.
Supponiamo di avere solo 2 colori bianco (1) e nero (0)
Una qualunque sequenza di cappelli sarà del tipo X100101101.
La parità si calcola sommando tutti i bit e restituendo l'ultima cifra. Ad esempio nel caso precedente la somma è 5 ovvero 101 e dunque la parità è 1.
Basterà che il primo della fila (X) si calcoli la parità dell'intera sequenza meno il suo, di modo che gli altri calcolando la parità della propria sequenza possano ricostruire di volta in volta il proprio colore. Ad esempio nel caso precedente se il primo dice di vedere un numero dispari di bianchi (dunque parità=1) basterà che il secondo noti di vederne un numero pari per dedurre che ha in testa un bianco.
Lo stesso ragionamento si può fare con m simboli piuttosto che con 2.
Saluti.
Supponiamo di avere solo 2 colori bianco (1) e nero (0)
Una qualunque sequenza di cappelli sarà del tipo X100101101.
La parità si calcola sommando tutti i bit e restituendo l'ultima cifra. Ad esempio nel caso precedente la somma è 5 ovvero 101 e dunque la parità è 1.
Basterà che il primo della fila (X) si calcoli la parità dell'intera sequenza meno il suo, di modo che gli altri calcolando la parità della propria sequenza possano ricostruire di volta in volta il proprio colore. Ad esempio nel caso precedente se il primo dice di vedere un numero dispari di bianchi (dunque parità=1) basterà che il secondo noti di vederne un numero pari per dedurre che ha in testa un bianco.
Lo stesso ragionamento si può fare con m simboli piuttosto che con 2.
Saluti.
Hai ragione pachito, ma il tuo metodo deve essere generalizzato. Se m è maggiore o uguale a tre? Ci sei quasi...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo