Occhi blu e marroni

[3m0o]

Un gruppo di persone con occhi di colori diversi vive su un'isola. Sono tutti logici perfetti: se una conclusione può essere dedotta logicamente, lo faranno immediatamente. Nessuno conosce il colore dei loro occhi. Ogni notte, a mezzanotte e un minuto, un traghetto si ferma sull'isola. Gli isolani che hanno scoperto il colore dei propri occhi lasciano l'isola, mentre gli altri restano. Tutti possono vedere gli altri in ogni momento e tengono il conto del numero di persone che vedono con ciascun colore degli occhi (esclusi loro stessi), ma non possono comunicare in altro modo. Tutti gli abitanti dell'isola conoscono tutte le regole di questo paragrafo.

Sull'isola ci sono $100$ persone con gli occhi blu, $100$ persone con gli occhi marroni e il Guru (che ha gli occhi verdi). Quindi una persona con gli occhi blu può vedere $100$ persone con gli occhi marroni e $99$ con gli occhi azzurri (e una con gli occhi verdi), ma questo non gli dice il suo colore degli occhi; per quanto ne sa, il totale potrebbe essere $101$ marroni e $99$ blu. Oppure $100$ marroni, $99$ blu e lui potrebbe avere gli occhi rossi.

Al Guru è concesso di parlare una sola volta (diciamo a mezzogiorno), in un solo giorno di tutti gli interminabili anni trascorsi sull'isola. In piedi davanti agli isolani, dice quanto segue:

“Vedo qualcuno che ha gli occhi blu”.

Chi lascia l'isola e in quale notte?

Già tutti sapevano che c'era almeno una persona con gli occhi blu. Quindi qual è esattamente l'informazione che il Guru fornisce e che ogni persona non aveva già?

[gabriella127]

Ma il Guru cerca di favorire più che può gli isolani o parla a casaccio?

[3m0o]

Devi chiederlo al Guru . A parte gli scherzi, direi nessuno dei due, ma non è rilevante.

[axpgn]

Deve essere una cosa simile alla Grande Strage ma meno cruenta

[3m0o]

"axpgn":

Deve essere una cosa simile alla Grande Strage ma meno cruenta

E cosa sarebbe?

[axpgn]

È un enigma classico e famoso proposto da un matematico negli anni '50, mi pare, ma non riesco a trovarlo ...
Qualcosa di simile è questo ma l'originale è migliore

[Faussone]

In effetti, come ha detto axpgn, è una variante di un enigma abbastanza classico riproposto in vari modi (io lo avevo sentito coi cornuti e con i frati di un convento).
Qui se capisco bene è molto importante l'informazione del guru perché in principio il colore degli occhi può essere qualsiasi. Dal momento che si ha la certezza che esiste almeno qualcuno con gli occhi blu ci si ricongiunge al quesito classico menzionato sopra: se esistesse solo una persona con gli occhi blu allora questa non vedendo nessun altro con gli occhi blu se ne andrebbe subito; se le persone fossero due ciascuno di loro vedrebbe solo una altra persona con gli occhi blu e vedendo che questa non è andata via il primo giorno capirebbe che la sola altra persona con gli occhi blu è lui, quindi entrambi andrebbero via il secondo giorno; e così via.
Quindi dopo che il guru fa l'annuncio i 100 con gli occhi blu (e solo loro) andrebbero via al centesimo giorno.
Questo stesso ragionamento non può farlo chi ha gli occhi marroni, quindi in realtà l'informazione del guru, pur conosciuta da tutti, è importante. ...sempre che non mi stia perdendo qualche altra considerazione.

[3m0o]

Esatto, ma più precisamente per il guru

L'informazione del guru non è importante perché il colore degli occhi può essere qualsiasi. L'informazione del guru è essenziale poiché rende pubblica l' informazione che ci sia almeno uno con gli occhi blu. Più nello specifico non solo tutti sanno che c'è almeno uno con gli occhi blu, ma sanno anche tutti gli altri sono a conoscenza di questo fatto. Senza l'affermazione del guru non potevano essere certi che anche gli altri isolani fossero a conoscenza di questo fatto. Dalla loro prospettiva poteva essere che uno di loro non era a conoscenza di questo fatto.
Faccio l'esempio con 4 isolani + il guru che è più facile. Supponiamo che ci siano 2 di occhi blu e 2 di occhi marroni. Tutti sanno che c'è almeno uno con gli occhi blu. Ma per uno con gli occhi blu non sa di averli blu e quindi potrebbe essere che l'altro con gli occhi blu veda 3 occhi marroni e in qual caso non sarebbe a conoscenza dell'informazione che c'è almeno uno con gli occhi blu. Quindi senza l'affermazione del guru potrebbe essere che per uno con gli occhi blu un altro con gli occhi blu non sappia che ci sia almeno uno con gli occhi blu. E quindi l'induzione non può partire senza l'affermazione del guru.

[Faussone]

In realtà non sono così sicuro di aver capito il discorso del guru.

Alla fine il guru dice un qualcosa che già tutti sanno, quindi mi verrebbe da dire che la sua informazione non occorra realmente. Ok capisco il discorso che può servire a far partire il ragionamento induttivo, ma non riesco a cogliere bene il motivo per cui sia davvero necessario se ci sono tanti con gli occhi blu.
Alla fine se io vedo 100 con gli occhi marroni e 99 con gli occhi blu e vedo che a 99 giorni i blu non se ne sono andati, deduco che anche io ho gli occhi blu e il giorno successivo andrei via, certo insieme a tutti gli altri blu e pure a tutti i 100 occhi marroni. Perché non funzionerebbe senza il guru?

[3m0o]

Eh... invece no

Quando mi proietto nel ragionamento di un'altra persona, non posso usare la conoscenza che ho del suo colore degli occhi.

Diciamo che $B_1,B_2,\ldots,B_{100}$ hanno gli occhi blu. Prima che il guru parli, per $B_1$ è possibile che $B_1$ abbia gli occhi marroni. Quindi sotto questa credenza (assunzione) se $B_1$ si proietta nel pensiero di $B_2$ abbiamo che $B_2$ vede 98 persone con gli occhi blu ($B_3,\ldots,B_{100}$).
Ora $B_2$ potrebbe credere di avere gli occhi marroni, ovviamente $B_1$ sa che non è così, ma appunto non può usare la sua conoscenza in questo ragionamento, può usare solo l'informazione che $B_2$ possiede (intersecata alla sua ovviamente). Quindi $B_1$ crede che $B_2$ crede che $B_3$ vede 97 persone con gli occhi blu ($B_4,B_5, \ldots, B_{100}$).

Continuando in questo modo a proiettarci nel pensiero di quello successivo abbiamo che è possibile che $B_1$ creda che $B_2$ creda che $B_3$ creda che ... $B_{99}$ creda che $B_{100}$ non veda nessuno con gli occhi blu! E dunque c'è un solo insieme di credenze per le persone con gli occhi blu che permetterebbe loro di stare sul isola all'infinito (senza l'intervento del guru). Cioè se ogni persona con gli occhi blu credesse non solo di avere gli occhi marroni, ma credesse anche che ogni altra persona con gli occhi blu creda, erroneamente, di avere gli occhi marroni. In modo equivalente se tutte le persone con gli occhi blu credono che tutte le persone con gli occhi blu abbiano gli occhi marroni.

L'affermazione del guru elimina questa possibilità poiché adesso tutti sanno, non solo che c'è uno con gli occhi blu, ma anche che tutti gli altri sanno che uno con gli occhi blu c'è.

Forse questo può essere d'aiuto: Se il guru andasse individualmente da tutti a dire in segreto "Vedo qualcuno che ha gli occhi blu" allora nessuno sarebbe mai uscito poiché non sta aggiungendo informazione a nessuno. Ma il guru dice a tutti che vede qualcuno con gli occhi blu, e dicendolo pubblicamente, allora tutti scoprono qualcosa sullo stato di conoscenza degli altri, un informazione che prima non avevano.

[Faussone]

Grazie 3m0o, ma ancora non ho afferrato bene.

Nel caso in oggetto io vedendo N persone con gli occhi blu so con certezza che anche qualunque mio vicino con gli occhi blu vede o lo stesso mio numero N di persone con gli occhi blu, se anche io avessi gli occhi blu, o una persona in meno con gli occhi blu se io non avessi gli occhi blu, d'altra parte so che un mio vicino che non ha gli occhi blu vederebbe o il mio stesso numero di persone con gli occhi blu, se io non avessi gli occhi blu, o una persona in più di me con gli occhi blu. Quindi, se N è almeno pari a due, so che tutti sanno che esiste almeno qualcuno con gli occhi blu. Quindi non capisco ancora a cosa serva l'intervento del guru.

[3m0o]

Certo che sei confuso, non sono stato sufficientemente preciso nel spiegarmi. Vediamo se così provo a convincerti

"Faussone":vedendo N persone con gli occhi blu [...] Quindi, se N è almeno pari a due, so che tutti sanno che esiste almeno qualcuno con gli occhi blu. Quindi non capisco ancora a cosa serva l'intervento del guru

Prendiamo l'esempio con $N=2$, $B_1,B_2,B_3$. Mettiamoci nei panni di $B_1$:

E' vero che $B_1$ sa che $B_2$ sa che c'è almeno una persona con gli occhi blu. Allo stesso modo è vero che $B_1$ sa che $B_3$ sa che c'è almeno una persona con gli occhi blu.
Ma $B_1$ non sa che $B_2$ sa che $B_3$ sa che c'è almeno una persona con gli occhi blu. Infatti $B_1$ potrebbe pensare quanto segue:

"Se ho gli occhi marroni allora $B_2$ potrebbe pensare a sua volta: 'se i miei occhi fossero marroni allora $B_3$ potrebbe non vedere una persona con gli occhi blu', dunque $B_2$ potrebbe non sapere che $B_3$ sa che qualcuno ha gli occhi blu."

E' vero che "tutti sanno che tutti sanno che c'è almeno una persona con gli occhi blu". Ma non tutti sanno questo fatto, ovvero non tutti sanno che tutti sanno che tutti sanno che c'è almeno una persona con gli occhi blu.

Come @Faussone o @3m0o sai che tutti sanno che tutti sanno che c'è almeno una persona con gli occhi blu perché vedi il colore degli occhi di tutti. Nei panni di $B_1$ invece non sai che $B_2$ sa che $B_3$ sa che c'è almeno una persona con gli occhi blu perché non sai il colore dei tuoi occhi.

Puoi continuare così aggiungendo un livello alla volta con $B_4$ e via dicendo eliminando sempre una persona con gli occhi blu fino ad arrivare a dire che $B_1$ non sa che $B_2$ sa che $B_3$ sa che ... $B_{99}$ sa che $B_{100}$ vede almeno una persona con gli occhi blu.

Per approfondire è molto bella la risposta di Marc van Leeuwen qui https://math.stackexchange.com/questions/489308/100-blue-eyed-islanders-puzzle-3-questions/490546#490546
Scrivo comunque un riassunto di ciò che dice:

Dobbiamo distinguere la verità di una affermazione dal fatto che una persona sappia che questa proposizione sia vera. Definiamo il concetto di conoscenza. Se $P$ è una qualunque proposizione allora indichiamo con $E^1(P)$ la proposizione che tutti (le persone con gli occhi blu) sanno che $P$ è vera. E' facile vedere che $E^1(P) \Rightarrow P$. Ma chiaramente abbiamo che l'altra direzione è falsa. Ad esempio è vero $B_1$ ha gli occhi blu, ma $B_1$ non lo sa. Data una proposizione $P$ e un intero $k >0$, definiamo $E^k(P)=E(E^{k-1}(P))$, dove $E^0(P)=P$. Infine scriviamo $C(P)$ per indicare che per ogni $k \geq 0$ abbiamo $E^k(P)$.

Sia $n$ il numero di persone con gli occhi blu. Nel problema abbiamo che $n=100$ è vero, ma $E^1(n=100)$ è falso. Invece come affermi correttamente te abbiamo che $E^1(n \geq 99)$. Ma $E^2(n \geq 99)$ è falso per esempio, è vero invece $E^2(n \geq 98)$. In generale per ogni $k$ abbiamo che $E^k(n \geq 100-k)$ è vero ma è falso $E^k(n > 100-k)$. Senza l'affermazione del guru abbiamo quindi che $E^{99}(n>0)$ ma non $E^{100}(n>0)$. Il fatto è che non è sufficiente $E^{99}(n>0)$. Infatti è vero che è sufficiente un certo tipo di conoscenza generale del fatto che $n >0$ a qualche livello \(\ell+k\) (una sufficiente potenza di $E$), e dopo $k$ notti successive in cui nessuno uscirà allora tutti capiranno che $n>k$ ad un livello \(\ell\) e quindi perdendo $k$ livelli di conoscenza. Questa cosa è espressa dal seguente risultato

Sia $L(i)$ la proposizione che durante la notte $i$ qualcuno lascia l'isola. Per ogni \(\ell, k \in \mathbb{N}\) abbiamo che \(E^{\ell +k}(n>0)\) e $C(\forall i \leq k : \neg L(i) ) $ allora risulta che \(E^{\ell}(n>k)\)

Quindi se vogliamo avere $E^{1}(n>99)$ abbiamo che $E^{99}(n>0)$ non è sufficiente mentre $E^{100}(n>0)$ si. Ora il guru fornisce $C(n>0)$ e dunque $E^{100}(n>0)$ pertanto possono uscire dopo 99 notti alla 100esima.

[Faussone]

@3m0o
Grazie per la pazienza, qualcosa sto forse iniziando a capire, non posso dire di aver afferrato tutto, ma ho capito la linea di ragionamento. Ci penserò ancora da me. Da solo non ci sarei mai arrivato comunque, quindi se fossi stato un isolano sarebbe stato un problema per gli altri!

[Faussone]

Su Geopop lo stesso quesito e la soluzione (qualcuno di loro legge qui? )

[3m0o]

"Faussone":Su Geopop lo stesso quesito e la soluzione (qualcuno di loro legge qui? )

Possibile, ma la loro soluzione del guru è sbagliata

"Geopop":
Dopo la dichiarazione del viaggiatore, tutti sanno che tutti sanno dell’esistenza degli occhi blu.

anche prima del guru tutti sanno che tutti sanno! Quello che invece succede grazie al guru è che: "tutti sanno che tutti sanno che tutti sanno che tutti sanno che .... che tutti sanno dell'esistenza di uno con gli occhi blu

[Faussone]

@3m0o

Sì avevo notato che quel dettaglio non era accurato, quindi forse qualcosa sto comprendendo