Su un’isola nessuno possiede uno specchio. Gli abitanti possono vedere il colore degli occhi degli altri, ma non il proprio. Sembrerebbe sufficiente chiedere: «Qualcuno ha gli occhi azzurri?». Eppure, in questo rompicapo, ciò che tutti possono già vedere non basta.
Un visitatore pronuncia una frase banalissima davanti all’intera comunità. Non rivela il numero degli abitanti dagli occhi azzurri e non indica nessuno. Da quel momento, però, il semplice trascorrere delle notti diventa una fonte di informazione.
La chiave non è un trucco linguistico: è la differenza matematica fra sapere qualcosa, sapere che gli altri lo sanno e sapere che tutti sanno che tutti lo sanno. Qui l’induzione cambia il destino di un’isola.
PROBLEMA 1729 #052
Tempo: 15–20 minuti
Difficoltà: Alto
Categoria: Logica epistemica e induzione
Il problema
Sull’isola vivono 100 persone: esattamente 37 hanno gli occhi azzurri, le altre 63 marroni. Nessuno conosce il proprio colore, ma ciascuno vede perfettamente gli occhi di tutti gli altri. Non esistono specchi, fotografie o superfici riflettenti. È vietato comunicare il colore degli occhi, anche con gesti. Ciascun abitante ragiona senza errori e sa che tutti gli altri sono logici perfetti; tutte queste regole e la loro pubblicità sono conoscenza comune.
Un abitante che deduca con certezza di avere gli occhi azzurri deve partire con la barca alla mezzanotte successiva. Le partenze sono osservabili da tutti; se nessuno parte, anche questo è noto a tutti il mattino seguente. All’inizio nessuno sa quanti occhi azzurri ci siano e non è stato stabilito pubblicamente che debba essercene almeno uno.
Il giorno 0 una visitatrice certamente sincera annuncia, di fronte a tutti: «Vedo almeno una persona con gli occhi azzurri». Ognuno sa che tutti hanno udito l’annuncio. Che cosa accade nelle notti successive? Perché una frase apparentemente superflua cambia il risultato?
Prima di aprire la soluzione, riduci il problema. Immagina un’isola di una, poi due, poi tre persone con occhi azzurri. Non cercare subito la risposta per 37: segui ciò che ognuno può dedurre dalle partenze che non avvengono.
💡 Mostra un indizio
Se ci fosse una sola persona con gli occhi azzurri, che cosa vedrebbe? E quando potrebbe riconoscere il proprio colore?
L’unica persona dagli occhi azzurri non vedrebbe nessun altro con quel colore. Dopo l’annuncio pubblico e veritiero, concluderebbe immediatamente che l’azzurro deve appartenere a lei.
💡 Mostra un indizio
Con due persone dagli occhi azzurri, che cosa pensa ciascuna della prima notte, se immagina di avere gli occhi marroni?
Ognuna vede un solo azzurro e ragiona: «Se io fossi marrone, l’altra persona sarebbe l’unica azzurra e partirebbe la prima notte». Quando nessuno parte, quella possibilità viene esclusa. Il silenzio della prima notte è una nuova informazione pubblica.
✅ Mostra la soluzione
Una persona: la prima notte
Se c’è esattamente un abitante dagli occhi azzurri, egli non vede alcun azzurro. L’annuncio «ne esiste almeno uno» è vero soltanto se è lui stesso ad averli azzurri. Lo deduce il giorno 0 e parte alla prima mezzanotte.
Due persone: la seconda notte
Siano A e B gli unici azzurri. A vede B e considera la possibilità di essere marrone. In quel caso B vedrebbe zero azzurri, riconoscerebbe i propri occhi dopo l’annuncio e partirebbe la prima notte. B ragiona simmetricamente. Poiché alla prima mezzanotte non parte nessuno, A e B scartano l’ipotesi di essere marroni. Entrambi partono alla seconda mezzanotte.
Tre persone: la terza notte
Con tre azzurri, ciascuno ne vede due e si dice: «Se io fossi marrone, quegli altri due sarebbero gli unici azzurri; per il caso appena dimostrato partirebbero la seconda notte». Non accade. Solo dopo la seconda notte senza partenze tutti e tre scoprono il proprio colore e partono insieme alla terza.
La dimostrazione per induzione
Proposizione. Se vi sono esattamente k abitanti dagli occhi azzurri, con k ≥ 1, e valgono tutte le regole pubbliche enunciate, nessuno parte nelle prime k − 1 notti e gli k azzurri partono insieme alla notte k.
Base k = 1. È il primo caso. Passo induttivo. Assumiamo la proposizione vera quando gli azzurri sono k. Consideriamo un’isola con k + 1 azzurri. Ognuno di essi ne vede esattamente k e, non conoscendo il proprio colore, ammette due possibilità: se fosse marrone, vi sarebbero k azzurri; se fosse azzurro, ve ne sarebbero k + 1. Nel primo scenario, per ipotesi induttiva, quei k partirebbero alla mezzanotte k. Non potendo dedurre prima di quella scadenza che il primo scenario è falso, non parte nessuno nelle prime k notti. Quando anche la notte k passa senza partenze, ciascun azzurro esclude di avere gli occhi marroni; tutti partono alla notte k + 1. Il passo è dimostrato.
L’induzione vale per ogni intero positivo. Con 37 persone dagli occhi azzurri, dunque, nessuno parte nelle prime 36 notti e tutte e 37 partono insieme alla 37ª mezzanotte. I 63 abitanti dagli occhi marroni non sono tenuti a partire, perché la regola riguarda soltanto chi scopre di essere azzurro.
Perché l’annuncio non è inutile
Con 37 azzurri, ognuno di essi ne vede altri 36: la frase della visitatrice non comunica un fatto nuovo al singolo. Ma l’annuncio pubblico rende il fatto «esiste almeno un azzurro» conoscenza comune: ciascuno sa che ciascuno l’ha udito, sa che ciascuno sa che gli altri l’hanno udito, e così via. In tal modo diventa legittimo applicare indefinitamente il ragionamento induttivo dal caso base.
Il punto è distinguere il contenuto informativo per una persona dall’effetto collettivo di una dichiarazione pubblica. Se mancasse la garanzia che tutti abbiano sentito la stessa frase, l’argomento induttivo non sarebbe automaticamente valido.
La matematica dentro al gioco
Questo rompicapo appartiene alla logica epistemica, che studia gli stati di conoscenza degli agenti. Indichiamo con E la proposizione «esiste almeno un abitante con occhi azzurri». Dire che tutti sanno E è diverso da dire che E è conoscenza comune: occorre anche che tutti sappiano che tutti sanno E, che tutti sappiano che tutti sanno che tutti sanno E, e così via.
L’annuncio pubblico introduce questa struttura gerarchica. Ogni notte senza partenze elimina uno scenario: dopo la notte 1 non può esservi esattamente un azzurro; dopo la notte 2 non possono esservene esattamente due; e così via. Questo processo è un esempio elementare di logica degli annunci pubblici, studiata anche nella logica dinamica epistemica.
Una buona fonte introduttiva è la Stanford Encyclopedia of Philosophy, «Common Knowledge»; per il ruolo formale degli annunci si veda «Dynamic Epistemic Logic».
Una variante per te
Variante A: cinque azzurri. Sono presenti anche molte persone con gli occhi marroni. Le prime quattro notti trascorrono senza partenze; alla quinta partono esattamente i cinque azzurri. Il numero dei marroni non sposta la conclusione.
Variante B: annuncio privato. La visitatrice sussurra a ciascuno separatamente «vedo almeno un azzurro», senza che nessuno sappia se la frase sia stata detta anche agli altri. Puoi ancora usare la stessa induzione? Non direttamente: la conoscenza comune dell’annuncio non è assicurata.
Variante C: nessuna partenza visibile. Se non è possibile osservare chi parte o non parte, il passare delle notti non fornisce l’informazione richiesta per il passo induttivo. La pubblicità delle azioni è essenziale quanto la veridicità della frase.
Lo sapevi?
Una variante molto nota presenta bambini con la fronte sporca di fango: l’insegnante dice pubblicamente che almeno uno di loro è sporco e chiede chi lo sa. La struttura è la stessa, benché spariscano l’isola, la barca e gli occhi azzurri. Nel linguaggio della logica il punto non è la storia, ma come un annuncio pubblico modifica l’insieme degli scenari considerati possibili.
La situazione è diversa dal semplice «tutti hanno visto un azzurro»: una proprietà che tutti conoscono può non essere conosciuta da tutti come universalmente conosciuta. È questa distinzione a far avanzare l’induzione una notte alla volta.
Problema 1729
#052 — L’isola degli occhi azzurri e la conoscenza comune
Giochi, enigmi e idee matematiche per menti curiose.