La tana del Beholder

Una strega malvagia e sadica ha rapito 10 piccoli elfi, minacciando di ucciderli tutti se non sono in grado di superare una prova di intelligenza.

La prova consiste in questo:
La strega metterà in fila dal più basso al più alto gli elfi; ogni elfo guarderà solo davanti a se, in modo tale da vedere solamente gli altri elfi più bassi di lui. Dopodiché la strega piazzerà, sulla testa di ciascun elfo, un berretto, di colore o bianco o nero (potrebbero essere 9 bianchi e 1 nero, 9 neri e 1 bianco o qualsiasi combinazione intermedia, o anche tutti bianchi o tutti neri).
Va da sè che ogni elfo vedrà quindi i soli berretti degli elfi davanti a lui, ma non il proprio.
La strega a questo punto interrogherà gli elfi, uno alla volta, partendo dal più alto (ossia quello che vede gli altri 9 davanti a sè) e chiedendo loro qual'è il colore del berretto che ciascuno ha in testa. Chi dà la risposta giusta ha salva la vita, gli altri invece periranno.

A questo punto la strega dà agli elfi una decina di minuti per decidere una strategia comune da seguire, dopodiché il perfido gioco inizia.

Voi, con il vostro acume, potete consigliare gli elfi sulla strategia da seguire e contribuire quindi ad evitare lo sterminio di 10 innocenti.

Che suggerimento dareste? Quanti elfi riuscirete a salvare, e perché?

Tanto per evitarvi inutili "pippe mentali", il gioco non prevede giochi di parole, calembour, doppi sensi o roba analoga.
E' un puro quesito di logica matematica, e come tale va risolto

Galahad ha scritto: (potrebbero essere 10 bianchi e 1 nero, 10 neri e 1 bianco o qualsiasi combinazione intermedia).

Ma se gli elfi sono 10, perchè i berretti sono 11? :p

penso sia un errore...

confermo quanto detto da nardone 9+1 o 1+9 o qualsiasi combinazione che sommata dia 10 totale

quindi si esclude che siano tutti bianchi o tutti neri?

no, ho aggiunto la precisazione, possono essere anche tutti bianchi o tutti neri. In pratica il colore di ogni cappello che la strga pone in testa ad un elfo è casuale

Qualcosa ho pensato, ma ne salvo sicuri solo 5

Alone ha scritto:Qualcosa ho pensato, ma ne salvo sicuri solo 5

descrivici come
(premetto comunque che si può fare di meglio)

Io e Pardo abbiamo pensato ad un metodo per salvarne 9, con il primo che schiatta al 50%.

Il primo dice il colore dell'elfo davanti a sè.

Il secondo dice il colore detto in precedenza, immediatamente dopo la domanda della strega se direttamente davanti a sè ha un bianco, con un ritardo di qualche secondo se davanti ha un nero.

Il terzo sfrutta l'informazione data dal secondo e, ritardando o meno la propria risposta, fornisce l'informazione al seguente.

Questo fino all'ultimo, il più basso, che probabilmente è un nano e non un elfo...

A) Il primo elfo (il piu' alto) dira' il colore del berretto di quello davanti a se'. Se il suo e' dello stesso colore, sopravvivera', altrimenti morira'.
B) Il secondo elfo dira' il colore che ha sentito dire al primo, urlandolo se quello successivo lo ha uguale al suo, altrimenti bisbigliandolo.
C) Ogni elfo successivo:
- se il precedente ha urlato, dira' il colore che ha detto il precedente, urlandolo a sua volta se il suo successivo lo ha uguale, altrimenti bisbigliandolo;
- se il precedente ha bisbigliato, dira' il colore che non ha detto il precedente, urlandolo a sua volta se il suo successivo lo ha uguale, altrimenti bisbigliandolo.
Nota 1 - Se il primo elfo urla (puo' comunque farlo), si puo' eliminare il passo B, perche' anche il secondo elfo puo' genericamente applicare il passo C.
Nota 2 - L'ultimo elfo puo' dire il colore con qualunque tono di voce; ma siccome sara' felice, direi che probabilmente urlera'.

Se ne salvano almeno nove, a patto che:
- nessuno sia afono o muto;
- nessuno sia sordo;
- nessuno sia Shardan (non puo' bisbigliare). Ma se i cappelli sono tutti uguali, anche con Shardan si salvano tutti lo stesso.

...all'atto pratico abbiamo trovato la stessa soluzione, ma la tua perde di generalità non potendola applicare al caso di Shardan (che come elfo, tra l'altro, farebbe una magra figura).

Il primo si potrebbe salvare specchiandosi negli occhi della strega, ma se lo potesse fare lui perché non lo potrebbero fare gli altri??

E se la strega invece che dare cappelli in grayscale (anzi... black and white) li fornisse agli elfi in RGB o peggio in CMYK?????

detto che chiaramente do per scontato che la strega non permetta di gridare
grazie diego avevo un mucchio di cose da fare, nelle ultime ore non ho fatto altro....
non so se questa soluzione vale sempre ... comunque

Ipotizziamo una situazione di questo tipo
10 = N
9 = N
8 = B
7 = N
S = B
5 = N
4 = N
3 = N
2 = N
1 = N

decidono questa strategia, ovvero mantenere pari il numero di cappelli il primo crepa al 50%
quindi
10 conta: 7 neri e 2 bianchi ... i neri sono dispari, quindi lui dichiara di avere un cappello nero
9 conta: Sei cappelli neri + 2 cappelli bianchi, più 1 nero dichiarato prima. quindi Sette neri e 2 bianchi, se avesse un cappello bianco non ci sarebbe parità e il primo avrebbe sbagliato, quindi sa che il suo cappello è nero e dice NERO
8 conta: Sei neri + 2 precedenti, 1 bianco, se avesse un cappello nero allora rimarrebbe un solo cappello bianco, quindi il suo cappello e bianco
7 conta 5 neri + 2 precedenti, 1 bianco + 1 precendente, totale 7 neri + 2 bianchi... per la parità lui ha il cappello nero

e così fino all'ultimo
ne salvi comunque 9

comunque sia... da bravo drow io non ne salvo nessuno di elfo ...

mi spiace per la soluzione fantasiosa di Tam e Milo (ma un elfo che urla dove si è mai visto...), ma la strada corretta è quelle di Elfoscuro.
Se ne possono salvare deterministicamente al massimo 9 (il primo per forza di cose, visto che non può vedere il proprio berretto, si salva la 50%).

Il primo deve passare un informazione di parità e gli altri lavorano per differenze.

Domandona: e se gli elfi fossero 11? il primo ne vedrebbe 10, dei quali ce ne potrebbero essere 5 con cappello bianco e 5 con cappello nero...

Per quanto riguarda l'impossibilità a gridare, invero sarebbero disponibili un infinità di altri segnali: per esempio, potrebbero decidere di usare come segnale il tempo che si impiega a rispondere alla strega. In questo caso,se si risponde immediatamente, per esempio, vuol dire che l'elfo succesivo ha un cappello del mio stesso colore, mentre se aspetto qualche istante il colore è diverso. Poi e ovvio che gli elfi dovrebbero ruolare bene...

se gli elfi fossero stati 11, allora probabilmente diego avrebbe cominciato con lo scrivere:
" ci sono 11 elfi ..."

se gli elfi fossero stati 11, allora probabilmente diego avrebbe cominciato con lo scrivere:
" ci sono 11 elfi ..."

e poi così a occhio, credo che la soluzione sia la stessa solo che il nr 11 e il nr 10 si salvano al 50% poi è uguale

Ma se i cappelli fossero così:
10 -> bianco
09 -> bianco
08 -> nero
07 -> nero
06 -> nero
05 -> nero
04 -> nero
03 -> nero
02 -> nero
01 -> nero

il 10 direbbe nero, ed il 9 direbbe pure nero, o no?

il 10 direbbe bianco, perchè vede un solo bianco e quindi deve ottenere la parità
9 dirà bianco perchè vede davanti a sè 8 neri e se dicesse nero renderebbe dispari i neri

Capito

Elfo ne hai tempo libero