Ancora nanetti e cappelli.

[Studente Anonimo]

7 nanetti vengono rapiti. La strega cattiva gli mette in testa dei cappelli neri o bianchi con probabilità 1/2. Ciascun nanetto vede il colore dei cappelli di tutti gli altri ma non il proprio!
I nanetti dopo aver visto i cappelli di tutti, e senza poter comunicare in alcun modo tra loro, dovranno scrivere su un foglietto personale una delle seguenti tre cose: "Nero", "Bianco" oppure "Non lo so".
I nanetti si salvano se: Almeno un nanetto indovina il proprio colore e nessun nanetto sbaglia il proprio colore.
I nanetti muoiono se: Almeno un nanetto sbaglia il proprio colore oppure se scrivono tutti "non lo so".

Trovare una strategia tale per cui i nanetti si salvano a meno che tutti i cappelli non siano bianchi.

[axpgn]

Fanno come gli gnomi miei quando uscirono dalla grotta

Troppo conciso?


Cordialmente, Alex

[Studente Anonimo]

Eh no non possono mica spostarsi

[axpgn]

Mica lo hai scritto

Dai, che è una bella soluzione, ammettilo

Se poi trovo la tua, te lo dico

[Studente Anonimo]

E poi non funziona

[Studente Anonimo]

Nel tuo infatti riescono a separarsi in due gruppi ma nessuno sa con certezza il proprio colore

[Studente Anonimo]

Ci tengo a precisare che evidentemente la strategia è quella ottimale, questo indovinello è risolto solo per alcuni \(n \), come per \(n=7\) ma non si sa se la stessa strategia che funziona per \(7\) e per altri interi, è quella ottimale anche altri \(n\)

[axpgn]

Come non funziona?
Hai detto che basta uno quindi, se non sono tutti dello stesso colore (cosa che hai escluso) uno dei due che sta agli estremi scrive il proprio colore (anzi meglio ancora quelli che stanno al penultimo posto) e gli altri "non so"

[Studente Anonimo]

Edit:

Io ho chiesto una soluzione che funziona sempre tranne nel caso in cui i cappelli siano tutti (wlog) bianchi. In particolare significa che funziona se i cappelli sono tutti neri.
Ovvero la probabilità di successo è di \( \frac{2^7 -1}{2^7} \)

La tua soluzione non funziona perché
Se (wlog) il primo vedesse tutti cappelli bianchi egli non sa di che colore è il suo ma anche se li vedesse tutti neri non sa di che colore è il suo

Mentre con la tua soluzione la probabilità di successo è \( \frac{2^7 -2}{2^7} \)

[axpgn]

La mia soluzione funziona perché se sono tutti neri, il penultimo (da una parte o dall'altra) vede nero sia a destra che a sinistra quindi deduce che il suo sia nero

[axpgn]

"3m0o":Nel tuo infatti riescono a separarsi in due gruppi ma nessuno sa con certezza il proprio colore

Ma non è vero, guarda qui ...



In ogni situazione ce n'è almeno uno (ma anche di più) che sa quale sia il colore del suo cappello, pure se sono tutti bianchi; e pure se sono in numero diverso da sette

Cordialmente, Alex

[Studente Anonimo]

Beh a questo non avevo pensato! Molto bello! Però non va bene comunque perché risolve un altro problema! Perché spostarsi è una forma di comunicazione! Infatti ad esempio il terzo a dipendenza di dove si mette sta comunicando agli altri un informazione! Ovvero "i vostri colori sono differenti" se si mette in mezzo oppure "i vostri colori sono uguali" se si mette a destra. Sta dando bit di informazioni agli altri di ciò che vede.

Nel mio non è ammessa nessuna forma di comunicazione! Di nessun tipo!

[axpgn]

"3m0o":Infatti ad esempio il terzo a dipendenza di dove si mette sta comunicando agli altri un informazione! Ovvero "i vostri colori sono differenti" se si mette in mezzo oppure "i vostri colori sono uguali" se si mette a destra.

No, perché si mette SEMPRE in mezzo (pensaci )
Non sceglie MAI!

[Studente Anonimo]

@axpgn
L'idea del indovinello era proprio il fatto che i nani non possono dedurre nessuna informazioni supplementare dagli altri nani in nessun modo, se non dal colore dei cappelli che vedono, se ottieni una strategia in cui un nano deduce il proprio colore in base al azione, di qualunque tipo esso sia, di un altro nano allora non va bene!

[Studente Anonimo]

"axpgn":

[quote="3m0o"]Infatti ad esempio il terzo a dipendenza di dove si mette sta comunicando agli altri un informazione! Ovvero "i vostri colori sono differenti" se si mette in mezzo oppure "i vostri colori sono uguali" se si mette a destra.

No, perché si mette SEMPRE in mezzo (pensaci )
Non sceglie MAI!

[axpgn]

Ho capito, ho capito fin dall'inizio cosa vuoi dire (e sapere) ma mi è venuta questa soluzione che è troppo carina e che ti ha messo in difficoltà, ammettilo
Ed è pura "pedagogica", perché così la prossima volta ti obbligherà a pensare ancor di piu

Sempre cordialmente, Alex

[axpgn]

"3m0o":Se il terzo nano vede due cappelli neri e si mette in mezzo con il cappello bianco non funziona più la tua strategia.

Ahiahaiai
Si mette sempre in MEZZO: che sia tra due neri e un bianco oppure tra tre neri e ZERO bianchi, sempre in mezzo è
Mi sorprende che tu dimentichi l'insieme vuoto, non è da te (scherzo, eh! )

[Studente Anonimo]

"axpgn":Mamma mia, è incredibile, non ci posso credere!

Il primo esce.
Il secondo esce e si mette accanto al primo.
Il terzo esce e se vede cappelli tutti dello stesso colore si mette accanto agli altri mentre se vede cappelli di colore diverso si mette in mezzo
E così tutti gli altri.

Non ti bastava così?

Cordialmente, Alex

[Studente Anonimo]

Ad ogni modo questa discussione è ot poiché non risolve l'indovinello
Per quanto sia carina e per quanto sia una bella strategia!

[axpgn]

Ma quella che citi era una descrizione informale della strategia, quella formale invece è quella che ho postato poc'anzi

Comunque sì, siamo OT ma è tutta pubblicità, serve a tenere in caldo la discussione

[Studente Anonimo]

[ot]Adesso però spiegami. Tu dici che si mettono sempre in mezzo. Okay! Supponiamo che ci siano 3 cappelli bianchi e 4 neri.
E supponiamo escano in questo ordine

Il primo nero si mette a sinistra
Il secondo nero si mette a destra
Il terzo bianco si mette in mezzo
Il Quarto nero si mette in mezzo (tra il primo ed il secondo)
Il Quinto bianco si mette in mezzo
Il sesto bianco si mette in mezzo (tra il secondo e il terzo)
Il settimo nero si mette in mezzo

Abbiamo quindi da sinistra verso destra
N N B N B B N

Come fa uno di questi a capire il proprio colore se si mettono sempre in mezzo indipendentemente dal colore che vedono?[/ot]