Newsgroup: it.hobby.enigmi
Titolo: (LO) Nani e Cannibali

Dal bellissimo sito di Gianfranco Bo , Base 5
http://digilander.iol.it/basecinque/
incollo questo problema di logica che mi pare, pur vertendo su un tema non
proprio originale, molto stimolante per l' ingegno
222. L'enigma dei nani
di Paolino89 e Gonario Nieddu
Questo problema č stato posto da Paolino89 al Forum ma una versione molto simile
mi era stata inviata in precedenza da Gonario Nieddu, assieme alla soluzione.
Per questo motivo ho riportato due autori.
Dieci nani vengono catturati da una tribu di feroci cannibali che decidono di
mangiarli per il pranzo del giorno successivo.
Il capotribu decide tuttavia di lasciare ai nani una chance per salvarsi.
Il giorno seguente alla loro cattura, i nani verranno messi in fila indiana e
sul capo di ciascuno verrŕ messo un cappello di colore bianco o nero.
Ogni nano, ovviamente, puň vedere il colore dei cappelli dei nani che si trovano
davanti a lui ma non il proprio né quelli dietro.
I nani avranno salva la vita se (a cominciare dall'ultimo della fila, cioč
quello che vede davanti a sé nove cappelli, fino al primo della fila, che
davanti a sé non ha nessuno) indovineranno il colore del cappello che hanno
sulla testa.
Durante la notte i nani studiano uno stratagemma affinché si salvino piů nani
possibile.
La domanda č: qual č il migliore stratagemma e quanti nani si possono salvare
con certezza?
Ricordate che i cappelli non devono essere necessariamente 5 bianchi e 5 neri:
la loro distribuzione e proporzione č assolutamente casuale. Inoltre, durante la
cerimonia, i nani non possono comunicare fra loro. Possono pronunciare, uno dopo
l' altro, solo il colore del proprio cappello. Dopo che ciascun nano ha
pronunciato il presunto colore del cappello, quelli successivi (sapendo se č
stato ucciso o no) sono al corrente della esattezza o meno della risposta
(quindi del colore effettivo del cappello di quel nano).
ciao
fulvio

con certezza?
ci provo anche se la logica non e' il mio
forte :-)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
i nani decidono
che si salveranno almeno in 5. Hanno deciso che quelli che sono in fila in
posizione dispari dicano semplicemente il colore del cappello del compagno
che hanno davanti. I nani in posizione pari si salvano tutti gli altri
hanno comunque un 50% di probabilita' di indovinare anche il colore del
loro cappello.
ciao
raffa
--------------------------------
Inviato via 
http://usenet.iol.it
 

 loro cappello.
Seguendo il tuo ragionamento, credo che la strategia migliore sia invece
diversa. TUTTI i nani, a partire dall'ulltimo della fila (che è il primo ad
affrontare la prova),
dovranno pronunciare il colore del cappello del nano che li precede: in
questo modo il 1° (l'ultimo della fila), avrà il 50% di indovinare e
salvarsi; gli altri 9 si salvano sicuramente!
Senza il tuo aiuto però, mi stavo muovendo in tutt'altra direzione e se ne
sarebbero salvati con certezza solo 5.


A me sembra che invece con il tuo ragionamento si salvi solo il primo nano
della fila mentre gli altri ,non dicendo il colore del proprio cappello ma
di quello del nano che gli sta davanti, avranno tutti il 50% di possibilità
di salvarsi.
Io avevo invece pensato allo stesso metodo di Raffaella che mi sembra il
migliore

 sarebbero salvati con certezza solo 5.
Sembra l' uovo di Colombo , vista cosi', pero' c' e' un piccolo particolare:
si deve dire il colore proprio per salvarsi  ;-)
ciao
fulvio

"raffaella" <raffaell...@virgilioNOSPAM.it> ha scritto nel messaggio
news:212Z48Z14Z92Y1...@usenet.iol.it...

e' un buon inizio... naturalmente pero' c' e' il modo di migliorare, si deve
sfruttare un semplice principio matematico comune a parecchi giochi...
Ah! Cosi' lavori eh! Poi c' e' la partita...   Licenziata!!!
:-)
ciao
fulvio

(quindi del colore effettivo del cappello di quel nano).
Altra idea

.
..
I nani (ma perche' sono nani?) 4, 7, 10 dicono nero se vedono due
cappelli di uguale colore, e bianco se ne vedono due di colore
diverso. Cosi' facendo consentono di aver salva la vita, con un
semplice raginamento, ai nani 2, 3, 5, 6, 8, 9.
Per gli altri, lo stellone.
saluti,
margravio.

Avete assolutamente ragione!
esordio sul newsgroup con figuraccia, lol!

 ha scritto nel messaggio
news:ae9ujk$52jho$1...@ID-106287.news.dfncis.de...

E' l'uovo di colombo, in effetti. La strategia i nani l'hanno concordata
tutti assieme la sera prima, vero? Allora fanno così:
il decimo dice il colore del cappello che vede davanti a se: lui ha il 50%
di possibilità si salvarsi e dà al nono l'indicazione certa del colore del
suo cappello (facciamo che sia BIANCO). A questo punto il nono per salvarsi
deve dire per forza bianco, come evidenziao da *Il Polle*. Però i furbi nani
la sera prima si erano messi d'accordo che se il colore del proprio cappello
fosse stato uguale al colore del cappello successivo il possessore l'avrebbe
gridato, mentre se il colore fosse stato diverso l'avrebbe semplicemente
sussurrato. Per cui il nono nano (scusate, non ho resistito ;-) )  se vede
un cappello bianco grida forte BIANCO, mentre se vede un cappello nero
sussurra piano bianco. a questo punto l'ottavo nano sa anche lui il colore
del suo cappello e a sua volta lo pronuncia più o meno ad alta voce a
seconda del colore del cappello successivo.  In questo modo 9 nani si
salvano e uno ha il 50% di salvarsi, proprio come diceva *Moonlight Shadow*.
O no?
Ciao,
Luca

 la loro distribuzione e proporzione è assolutamente casuale.
Mi pare da questa asserzione che non v'è alcuna certezza per alcun nano di
salvarsi.
Se il numero dei cappelli bianchi ( o neri ) è casuale ed è incidentale
anche la
loro assegnazione, non mi spiego la certezza da parte loro a rispondere
esattamente sul colore del proprio cappello.
O.K., qui si chiede il miglior stratagemma possibile, ma francamente ed a
rigor
di logica non ne vedo nessuno.
Qualcuno m' illumini!
--
Saluti by Lvdwig.

 salvarsi.
Ricorda che i nani (ma perche' poi nani ? andava bene anche palombari
o dattilografe)
1) vedono i cappelli di quelli che non sono ancora stati interrogati
2) sentono le risposte dei nani interrogati prima (e che quindi quando
parlavano hanno visto il cappello dell'interrogando attuale).
3) hanno avuto tempo per studiare la strategia.
Per esempio,  banalmente, il k-esimo nano ad essere interrogato
puo' essere salvato dal (k+1)-esimo che vede il cappello del k-esimo
e puo' accordarsi per dire come proprio colore quello del
(k+1)-esimo: il k-esimo ha 50% di beccarci, ma il (k+1) dando la
stessa risposta del k-esimo, e' sicuro di sfangarla.
Comunque nelle risposte gia' date questo meccanismo
e' stato gia' usato: ma si puo' fare molto meglio...
diciamo che in media ogni nano ha probabilita' 1/20 di schiattare...
ciao,
giovanni.

 salvare con certezza?
.
.
.
.
ora ci provo anch'io
.
.
.
.
.
.
.
.
.
.
.
.
.
.
il primo nano dice bianco se vede davanti e se' un numero dispari di 
cappelli bianchi, altrimenti dice nero (o viceversa, non cambia niente)
il secondo conta i cappelli bianchi davanti a lui, capisce il colore del suo 
e lo dice, il terzo vede i cappelli davanti e conosce il colore di quello 
dietro (che lo ha detto), capisce il colore del suo e lo dice... insomma 
avete capito....
cosi' il primo vive al 50% (e non si puo' far meglio) e tutti gli altri 
sopravvivono alla faccia sua.
Un saluto a tutti gli abitanti di questo ng che ho scoperto da poco, ora 
cerchero' di allenarmi un po' sull'enigmistica classica dove sono una 
frana!  
ciao
-- 
Greg
g.guidi at 
sns.it

 diciamo che in media ogni nano ha probabilita' 1/20 di schiattare...
Be', diciamo che il primo a parlare non e' stato scelto casualmente... ma
attraverso una scelta molto democratica a botte e spintoni... lui
rischia, ma quello dopo di lui la paghera' cara... :-)
Con queste condizioni vendicative saliamo a 3/20.
Ciao ciao
Claudio [e finalmente un *grazie* interista a dipiero! ;-)]
-- 
"Non si puo' far la frittata senza rompere le uova.
 Purtroppo, da un secolo si son rotte molte uova, e
 siam sempre senza frittata." (Isaiah Berlin)

 3) hanno avuto tempo per studiare la strategia.
Probabilmente, anzi sicuramente c' è qualcosa che mi sfugge.
Non comprendo infatti l' aiuto che ciascun nano possa
ricevere dal fatto di vedere i cappelli degli altri davanti a se,
nè come possa trarre vantaggio dal sentire le risposte precedenti alla sua.
Se il secondo (penultimo della fila) vede avanti a se
8 cappelli neri (o bianchi) oppure 2 N e 6 B o ancora 5 N e 3 B,
come può con certezza definire il colore del prorpio?
Bah...
--
Saluti by Lvdwig

 come può con certezza definire il colore del prorpio?
Scusa, forse non riesco a essere chiaro: semplifichiamo al massimo:
siamo due nani: io sono il nano Bombolo (peso circa 115Kg...) e tu sei
il nano Bandolo (quello che si perde sempre).
Siamo in fila, con te davanti:
Io vedo il tuo cappello, supponiamo w.l.o.g. che sia BIANCO, ma non il 
mio, il cui colore e' ininfluente.
Tu non vedi nulla.
Siccome sono molto generoso, ci siamo messi daccordo cosi':
io, invece di usare le mie capacita' extrasensoriali per indovinare il
mio cappello, dico il colore del tuo (che vedo): BIANCO !
Ora, a me puo' andare bene o male, a seconda del colore del mio cappello.
Tu, pero', che pure non vedi una mazza, hai sentito che io dicevo 
BIANCO!. Questo in base agli accordi che abbiamo preso, e' il colore del
tuo cappello: quindi tu dicendo BIANCO! ti salvi.
(Se il tuo cappello fosse stato nero avrei detto NERO!, incrociato le 
dita come sopra, ma tu a colpo sicuro avresti detto NERO! e ti saresti
salvato.)
Piu' di cosi' non riesco a essere chiaro,
ciao,
Giovanni.

 ha scritto nel messaggio
news:3D08BACE.6040502@-nospam-iit.cnr.it...

Capito!!! Non mi ero soffermato, anzi non avevo proprio considerato
lo stratagemma da te spiegato.
--
Saluti by Lvdwig

 Dieci nani vengono catturati da una tribu di feroci cannibali
Vi propongo la soluzione inviata dal Vecio Gi , non so se il regolamento dei
cannibali lo consenta, ma mi pare molto ingegnosa :-)
spoiler
spoiler
Ciao, Fulvio, spero di trovarti bene.
secondo me, se ne salvano 9 e il 10°
ha 50% di possibilità di salvezza.
Ti dico il mio pensiero:
I dieci studiano questo stratagemma, il 1°
risponde dicendo il colore di quello che lo precede
''sperando bene che il suo sia uguale''
il 2° se il colore detto dal primo, che sarebbe il colore del suo cappello,
corrisponde al terzo, dice immediatamente il colore
sentito, se invece il terzo ha un altro colore, lascia
passare un attimo di tempo prima di rispondere
così il terzo si rende conto che il suo colore non è uguale a quello che
sente,
e così fino alla fine.
Spero di essere stato chiaro .
Ciao
stammi bene,
il vecio Gi.

spoiler
spoiler
spoiler
spoiler
spoiler
Si tratta di un gioco di "parità": l'ultimo nano, considerando ad esempio
"bianco"=1 e "nero"=0, trova il numero binario rappresentato dai cappelli
davanti a lui. Dice poi "bianco" se il numero è pari, "nero" se il numero è
dispari (ha 50% di possibilità di salvarsi). Il penultimo nano sa il proprio
colore, perchè può calcolare il numero binario dei cappelli davanti a sè e
confrontare il risultato con il colore affermato dal suo compagno. Dice
perciò il colore giusto. E così via tutti gli altri: si salvano tutti al
100% eccetto l'ultimo al 50%.
Nano-nano!

 222. L'enigma dei nani
In effetti la soluzione corretta e' quella proposta da Gianfranco e Greg,
ingenose pure le soluzioni di redluck e del Vecio che con un abile trucco
permettono di giungere agli stessi esiti. Vi comunico ufficialmente che il primo
nano ha avuto la fortuna di vincere il "testa o croce" a cui si sottoponeva, per
cui rientreranno tutti a casa sani e salvi. I cannibali si son dati all'
agricoltura ed all ' allevamento, tutto e' bene quel che finisce bene e.... l'
ultimo chiuda la porta!
:-)
ciao
fulvio

 trova il numero binario rappresentato dai cappelli davanti a lui.
Esatto. E la stessa tecnica vale pure con più di due colori. Infatti
era proprio con tre colori, e mi sembra cento condannati, che lo
risolvemmo qualche mese fa qui nel ng.
Si parte dalla dichiarazione del primo nano che dice, ad esempio,
"bianco" (che per convenzione vuole dire che la somma dei valori dei
cappelli è 1, ovvero ci sono un numero dispari di bianchi). Se ha
fortuna sopravvive, non ce importa molto della sua sorte ;)
Il secondo vede davanti a se un numero pari di bianchi e capisce che
era lui a rendere la somma dispari, quindi si salva dichiarandosi
bianco, il terzo sa che dopo la dichiarazione del secondo i bianchi
restanti sono dispari, e si regola guardando quanti ne vede davanti a
se e così via.
Con tre colori è la stessa cosa. Solo che i colori varranno 0,1,2 e
bisognerà calcolare la parità modulo tre, ovvero pari, pari- e pari+.
Esempio: nero=0, bianco=1, rosso=2. I dici cappelli sono distribuiti
così:
B,R,B,N,N,R,N,B,R
Il primo a parlare, il Rosso di destra, calcola la parità dei nove che
vede. Usando tre dita di una mano come contatore ciclico ci si riesce
in un attimo senza neanche stare a calcolare la somma (che qui vale 7
== 1 in modulo 3). Quindi il povero nano dice bianco e non vorremmo
essere nei suoi panni. Però il suo sacrificio non è stato vano. Il
secondo nano vede davanti a sè una somma 0, e quindi il suo cappello
deve essere bianco per giustificare la dichiarazione del martire. Mano
a mano che si succedono le dichiarazioni, tutti i nani aggiornano la
parità parziale, sclando dalla dichiarazione iniziale le dichiarazioni
di quelli che si sono salvati. Di nuovo bastano tre dita per tenere
agevolmente il conto, stavolta scalando anziché aggiungendo 0,1 o 2.
Dato che stiamo usando la mani, la cosa più comoda per noi sarebbero
cinque o dieci colori, solo che aumenterebbero le difficoltà di
memorizzare al tabellina dei colori e diminuirebbero le possibilità di
salvezza del primo nano. In caso di errore di uno dei nani, con due
colori si può correggere per esclusione, con più di due colori se i
cannibali ci fanno la cortesia di farcelo vedere prima di metterlo in
forno, si può ricominciare il meccanismo, altrimenti il prossimo a
parlare avrà da scegliere a caso tra n-1 valori possibili, o,
rischiando un po' di più ma restando fedeli al principio di
solidarietà, si comporterà come se fosse il primo della fila.
--
Ciao, Silv:o)