Nani numerabili e cappelli

[Vincent46]

Un'infinità numerabile di nani è disposta in fila indiana, di modo che ognuno abbia di fronte la schiena del successivo. Quindi, ogni nano ne ha un altro sia di fronte che dietro di sé, eccetto il primo, che non ha nessuno dietro di sé. Ogni nano ha in testa un cappello, che può essere bianco o nero. Ognuno può vedere i cappelli dei nani di fronte a sé, ma non il proprio, né quello di chi gli sta dietro.
Ogni nano viene interrogato sul colore del proprio cappello, a partire da quello che sta dietro a tutti, e procedendo uno per volta, verso la testa della fila infinita. Chi indovina si salva, chi sbaglia muore. È noto che i nani hanno udito perfetto, e possono sentire le risposte di chiunque li abbia preceduti, non importa quanto indietro nella fila. Le risposte possibili sono solo "bianco" o "nero".
Prima di essere messi in fila, i nani hanno avuto possibilità di parlare fra loro e di elaborare una strategia.
Se voi foste uno di loro, che strategia proporreste per minimizzare le perdite?

Nota per i pignoli: I nani sono esseri superiori e trascendono le limitazioni fisiche degli umani. Possono, ad esempio, memorizzare una quantità infinita di informazioni e svolgere conti dalla complessità computazionale infinita.

[axpgn]

Hai detto che hanno un udito finissimo ma quant'è lunga la loro vista?

Penso che possa funzionare una variante della strategia con un numero finito di nani (o prigionieri)
I nani suddividono la fila in blocchi da $n+1$ con $n$ dispari.
Il primo di ogni blocco dice il colore che risulta dispari tra gli $n$ cappelli che ha davanti, in tal modo chi gli sta davanti può capire di che colore è il suo cappello così come gli altri dello stesso blocco ricostruendo ogni volta la situazione.
In tal modo le perdite (eventuali) sono una ogni $n+1$ nani

Cordialmente, Alex

[Vincent46]

"axpgn":Hai detto che hanno un udito finissimo ma quant'è lunga la loro vista?

Penso che possa funzionare una variante della strategia con un numero finito di nani (o prigionieri)
I nani suddividono la fila in blocchi da $n+1$ con $n$ dispari.
Il primo di ogni blocco dice il colore che risulta dispari tra gli $n$ cappelli che ha davanti, in tal modo chi gli sta davanti può capire di che colore è il suo cappello così come gli altri dello stesso blocco ricostruendo ogni volta la situazione.
In tal modo le perdite (eventuali) sono una ogni $n+1$ nani

Cordialmente, Alex

Non sai che i nani hanno risoluzione infinita?

Questa è ok, ma... si può fare di meglio?

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Certo che si può fare di meglio...

Solo il primo nanetto ha una probabilità di $ \frac{1}{2} $ di morire dopodiché tutti gli altri hanno la certezza di indovinare il colore del proprio cappello!

[Vincent46]

"3m0o":Certo che si può fare di meglio...

Solo il primo nanetto ha una probabilità di $ \frac{1}{2} $ di morire dopodiché tutti gli altri hanno la certezza di indovinare il colore del proprio cappello!

Con quale strategia?

[thedarkhero]

La mia proposta dovrebbe funzionare per un insieme finito di nani.

L'ultimo nano della fila (cioe' il primo che viene interrogato) rispondera' 'bianco' se il numero di cappelli bianchi che vede davanti a se' e' pari, rispondera' 'nero' altrimenti: cosi' facendo avra' probabilita' pari a $1/2$ di morire ma avra' messo in salvo tutti gli altri nani.
Infatti, il penultimo nano potra' dedurre con certezza il colore del suo cappello vedendo tutti i cappelli davanti a se' e sapendo se i cappelli bianchi che possiedono lui e tutti i nani che ha davanti sono pari o dispari (grazie alla risposta data in precedenza dall'ultimo nano).
Lo stesso fara' ciascun altro nano.

Sono pero' curioso di sapere come ci si potrebbe comportare nel caso proposto da Vincent, ovvero quando i nani sono un'infinita' numerabile...

[Vincent46]

Hint per il caso numerabile:

Utilizzare l'assioma della scelta!

[Drazen77]

Io arrivo a salvarne il 75%.
Si può fare di meglio? Come?

[crisz96]

Considerando che i nani sono infiniti numerabili, possiamo considerare che i cappelli neri abbiano valore 1 e i cappelli bianchi abbiano valore 0.

Il primo nano fa lo XOR di tutti i cappelli che ha di fronte, dice "bianco" se lo XOR ha come risultato 0 e "nero" se ha come risultato 1. In questo modo, ha il 50% di probabilità di sopravvivere in quanto il colore del suo cappello è indipendente dal colore dei cappelli tutti gli altri.

Il secondo nano, fa lo XOR di tutti i cappelli che ha di fronte, con il risultato ottenuto fa lo XOR con la risposta del nano che lo precedeva, in questo modo può dire con certezza il colore del proprio cappello.

Così via per tutti i nani! Considerando che sono infiniti e che ne perdiamo solo mezzo (infilandoci un po' di logica fuzzy), alla fine ne avremo salvato il 100%.

Chiedo scusa a tutti i matematici che non sanno cos'è lo XOR è un operatore binario molto caro a noi informatici.
Qua riporto una tabella:

Op. 1	Op. 2	Risultato
0	0	0
1	1	0

Se ho tempo dopo lo riporto sotto formalismo matematico

[axpgn]

... mmm ... so cos'è l'XOR ma come funziona su un numero infinito di istanze? (se funziona ...)

[crisz96]

"axpgn":... mmm ... so cos'è l'XOR ma come funziona su un numero infinito di istanze? (se funziona ...)

Lo XOR tra un numero infinito di operandi è tale e quale ad una somma tra un numero infinito di addendi. Ho fatto leva sul fatto che i nani abbiano potenza di calcolo infinita.

Comunque ho commesso un errore, il nano non deve effettuare lo XOR tra tutti i successivi e il precedente, ma tra tutti i successivi (che vede) e tutti i precedenti (che ha udito) ad eccezione del primo nano.

Se lo XOR tra un numero infinito di operandi sembra impossibile, allora al fine di minimizzare le vittime, i nani potrebbero organizzarsi in insiemi di n elementi ed applicare il suddetto strataggemma su un insieme finito. In questo modo avremmo n primi nani e dunque n possibili morti.

[crisz96]

Faccio un esempio su un sottoinsieme n=11. Al solito 0 vuol dire bianco e 1 vuol dire nero.

->
0 0 1 0 1 0 1 0 1 1 1

Il nano in grassetto è il primo, quindi effettua lo XOR tra i successivi, e nota che il risultato è 0, quindi urla "Bianco". Per pura coincidenza è anche il colore del suo cappello, quindi si salva.


->
0 0 1 0 1 0 1 0 1 1 1
Il secondo nano prende la parola, anche in questo caso lo XOR tra tutti i cappelli di fronte a lui ha come risultato 0, il nano prende questo valore ed effettua lo XOR con la risposta del nano precedente, dunque
0 XOR 0 = 0.
Quindi può dire con certezza che il suo cappello è bianco. E' salvo.


->
0 0 1 0 1 0 1 0 1 1 1

Terzo nano, lo XOR tra tutti i cappelli che ha di fronte in questo caso ha come risultato 1.
Lo confronta con il secondo cappello:
1 XOR 0 = 1.
E con il primo:
1 XOR 0 = 1.
Urla "nero" e anche lui è salvo.

->
0 0 1 0 1 0 1 0 1 1 1

Quarto nano, lo XOR tra tutti i cappelli che ha di fronte ha come risultato 1.
Lo XOR tra tutti i cappelli che ha udito ha come risultato 1.
1 XOR 1 = 0. Anche lui è salvo.


->
0 0 1 0 1 0 1 0 1 1 1

Quinto nano, lo XOR tra tutti i cappelli che ha di fronte ha come risultato 0.
Lo XOR tra tutti i cappelli che ha dietro ha come risultato 1.
0 XOR 1 = 1. Anche lui è salvo.


->
0 0 1 0 1 0 1 0 1 1 1

Sesto nano, lo XOR tra tutti i cappelli che ha di fronte ha come risultato 0.
Lo XOR tra tutti i cappelli che ha dietro ha come risultato 0.
0 XOR 0 = 0. Anche lui è salvo.


->
0 0 1 0 1 0 1 0 1 1 1

Settimo nano, lo XOR tra tutti i cappelli che ha di fronte ha come risultato 1.
Lo XOR tra tutti i cappelli che ha dietro ha come risultato 0.
1 XOR 0 = 1. Anche lui è salvo.


->
0 0 1 0 1 0 1 0 1 1 1

Ottavo nano, lo XOR tra tutti i cappelli che ha di fronte ha come risultato 1.
Lo XOR tra tutti i cappelli che ha dietro ha come risultato 1.
1 XOR 1 = 0. Anche lui è salvo.


->
0 0 1 0 1 0 1 0 1 1 1

Nono nano, lo XOR tra tutti i cappelli che ha di fronte ha come risultato 0.
Lo XOR tra tutti i cappelli che ha dietro ha come risultato 1.
0 XOR 1 = 1. Anche lui è salvo.


->
0 0 1 0 1 0 1 0 1 1 1

Decimo nano, lo XOR tra tutti i cappelli che ha di fronte ha come risultato 1.
Lo XOR tra tutti i cappelli che ha dietro ha come risultato 0.
1 XOR 0 = 1. Anche lui è salvo.


->
0 0 1 0 1 0 1 0 1 1 1

Undecismo e ultimo nano, non ha nessun nano di fronte, ma lo XOR tra tutti i cappelli che ha sentito ha come risultato 1. Quindi può gridare felicemente "Nero" e salvarsi.

[Drazen77]

Mi spiegate cosa significhi calcolare lo XOR tra più di due dati?
Cioè, cosa vuol dire che il risultato dello XOR di questi 11 dati
0 0 1 0 1 0 1 0 1 1 1 sia 0? Come si ottiene 0?

[axpgn]

Una soluzione per il caso "finito" è già stata data; è "l'infinito" il problema ...
Io resto dubbioso che l'XOR si possa usare in tal caso (proficuamente intendo) ... vediamo cosa ne pensa l'autore ...

@Drazen77
Penso che lo esegua "uno alla volta", il risultato che si ottiene da due termini consecutivi con il successivo e cosi via ...

[Drazen77]

"axpgn":@Drazen77
Penso che lo esegua "uno alla volta", il risultato che si ottiene da due termini consecutivi con il successivo e cosi via ...

Anche così non riesco a capire: perché in questo esempio il primo nano risponde 0 e il terzo nano risponde 1?

[axpgn]

Prendi quello che hai scritto ... $00101010111$

$0x0=0\ x1=1\ x0=1\ x1=0\ x0=0\ x1=1\ x0=1\ x1=0\ x1=1\ x1=0$

Ok?

[Drazen77]

Sì, ok, adesso ho capito, grazie
Però non dovevi partire $0x0$, ma dal successivo

[axpgn]

Pignolo ...

[veciorik]

Il quiz langue, l'autore latita; tento una provocazione.
L'infinito non appartiene alla scienza ma alla filosofia, alla poesia, alla religione.
Credo sia impossibile progettare una strategia praticabile.
Non basta affermare "esiste una funzione ...", bisogna costruirla.

NB: non sono un matematico, ma un ex informatico in pensione.

Quanto all'operatore XOR, simbolo $ \ \oplus \ $, è commutativo e associativo quindi non sono necessarie parentesi.
Si può usare per calcolare rapidamente la parità di una sequenza di bit, sfruttando il fatto che $ \ 0 \oplus a = a \ $ e $ \ 1 \oplus a= \not a \ \ $: si ignorano gli $ \ 0 \ $ e basta tenere in memoria un bit ad ogni passo del calcolo; non serve contare.
Se $ \ S \ $ è una sequenza di bit e $ \ S - x \ $ la sequenza escluso il bit $ \ x \ $ incognito, $ \ x \ $ è lo XOR delle parità delle due sequenze.

Non riesco ad immaginare altre funzioni, tranne XOR e la sua negazione XNOR, definite sul dominio delle sequenze di bit e con codominio un singolo bit, candidate per risolvere il quiz.

Naturalmente XOR e XNOR non sono applicabili a sequenze infinite perché ogni nuovo bit $ \ 1 \ $ alterna il valore della funzione.

[Vincent46]

Chiedo scusa per l'estremo ritardo. Lo xor non è applicabile nel caso infinito; il fulcro del problema è proprio la difficoltà di generalizzare le strategie che sono applicabili al caso finito. Bisogna trovare nuove strade. Posto la soluzione a cui ero giunto, che è anche quella che si trova online:

Ragioniamo con gli zeri e gli uni. Partizioniamo l'insieme di tutte le sequenze nel seguente modo: diremo che due sequenze appartengono alla stessa classe se e solo se differiscono per un numero finito di zeri e di uni. Ad esempio, $0000...$ e $1000...$ stanno nella stessa classe, a cui invece non appartiene la sequenza $101010...$ (cioé quella formata da uni e zeri che si alternano all'infinito). Osserviamo che, quando vengono messi in fila, tutti i nani sanno precisamente a quale classe appartenga la sequenza effettiva di cappelli; infatti, ogni nano vede tutta la sequenza eccetto un numero finito di elementi (e cioé quelli dietro di sè).
Adesso c'è il passaggio delicato. Sfruttando l'assioma della scelta, si seleziona un rappresentante canonico per ogni classe, noto a tutti i nani. La strategia del primo nano, su cui la notte prima si saranno messi d'accordo, è la seguente: egli confronta la sequenza che si ritrova davanti con quella canonica, pure nota a tutti. Se esse differiscono per un numero pari di cappelli, dirà, ad esempio, "bianco"; altrimenti, dirà "nero". (Questo ha senso perché, per costruzione, le due sequenze differiscono per un numero finito di elementi). Quindi ha il 50% di possibilità di salvarsi. Ora, il secondo nano, sfruttando l'informazione ricevuta dal primo, saprà esattamente il colore del cappello sulla propria testa, e similmente anche tutti i successivi, ascoltando le risposte di chi ha parlato prima di loro...

Concordo con veciorik che è un indovinello un po' al limite dell'inganno, perché supporre che gli infiniti esistano porta ovviamente a qualche conflitto con la realtà. Ad esempio, anche se supponiamo l'esistenza di una funzione di scelta che permetta ai nani di scegliere una sequenza canonica da ognuna delle classi, dobbiamo anche supporre che ogni nano abbia a disposizione i mezzi per computare effettivamente tale funzione, una volta che sia stata formata la fila; cioé si suppone che i nani abbiano a disposizione un oracolo. Questo era il significato della mia "nota per i pignoli". Però, insomma, siamo matematici e quindi ragioniamo matematicamente, no?

[veciorik]

Obietto: le classi così costruite sono infinite e, quindi, anche i loro esemplari.
Tecnicamente parlando, non si possono memorizzare infinite sequenze esemplari né confrontarle con la sequenza data.

Con molte riserve, che chiarirò più avanti, si potrebbe fare qualcosa se fosse finito uno dei sottoinsiemi, i bianchi o i neri: si opera sulla parità del sottoinsieme finito.
Ciò equivale a memorizzare due esemplari: tutti bianchi e tutti neri.
Non serve una memoria infinita per memorizzare le due sequenze infinite, ma basta memorizzare due "regole".
Secondo questa logica si possono memorizzare un numero finito di "regole di composizione" delle sequenze sperando che la sequenza data differisca dalle "sequenze regolari" in un numero limitato di bit.
Ma questi casi sono una goccia nel mare in un mare infinito e indigeribile.

Infine, IMHO, è comunque tecnicamente impraticabile confrontare tra loro due sequenze infinite, oppure una sequenza casuale con una "regola", con l'obiettivo di determinare se sono uguali o quasi uguali; si può verificare soltanto che sono diverse: basta una differenza e ci si ferma.