domenica 27 settembre 2015

Gli enigmi di Coelum: "Permette una domanda?"

Tornano gli enigmi matematici pubblicati sulla rivista Coelum Astronomia, nella mia rubrica "Moebius": questa volta ripropongo un problema duplice, di carattere prettamente logico, uscito sul numero 177 della rivista.
In quell'articolo raccontai un mio sogno.
Mi trovavo su un’astronave, in procinto di atterrare su un pianeta misterioso. Il pilota, che proveniva da un lontano sistema solare, mi spiegò che gli abitanti del mondo che dovevamo raggiungere erano tutti bugiardi, senza eccezione.
Precisò poi che, tra gli otto pianeti del sistema solare, alcuni (i cosiddetti pianeti neri) sono proprio così, cioè abitati da bugiardi, mentre gli altri (i pianeti bianchi) sono popolati unicamente da persone sincere.
E quando si parla di sinceri e bugiardi, s’intende una cosa netta: un sincero dice sempre e soltanto cose vere, e un bugiardo afferma esclusivamente e costantemente il falso. Dopo una fugace visita al pianeta, ci ritrovammo sull'astronave, e il comandante mi pose due enigmi: se non li avessi risolti entrambi, sarei stato ucciso.

I problemi erano i seguenti:
1) Un preziosissimo tesoro è conservato in uno degli otto pianeti, e per determinare quale fosse questo pianeta potevo soltanto porre tre domande (la cui risposta poteva essere soltanto sì o no). Su ogni pianeta era pronto a rispondere un rappresentante della popolazione, e io dovevo scegliere a quali di questi delegati rivolgere ogni domanda. 
2) Sul pianeta del tesoro vi erano due cavità, una delle quali conteneva l’incalcolabile fortuna. Un indigeno svolgeva la funzione di custode del prezioso scrigno, coadiuvato nella sua funzione da un forestiero. L’unico indizio che avevo per capire a chi dovevo domandare la posizione del tesoro era una frase del forestiero: “Io e il mio capo proveniamo da due pianeti dello stesso colore”. 

Raymond Smullyan
L’enigma proposto s’inquadra, più o meno, in un filone di problemi di logica inventati dal geniale e poliedrico Raymond Smullyan. Nato a New York nel 1919, Smullyan è uno dei logici più famosi del nostro tempo, nonché un brillante inventore di giochi e rompicapi. Si occupa anche di musica (è un valente pianista), di prestidigitazione e di filosofia.
L’ambientazione tipica degli indovinelli di Smullyan è un’isola immaginaria abitata esclusivamente da “cavalieri”, cioè persone sempre sincere, e da “furfanti”, che sono solo capaci di mentire. Di solito il racconto prevede che un visitatore sbarchi sull'isola e s’imbatta in alcuni suoi abitanti: dalle loro affermazioni deve capire se si tratti di cavalieri o furfanti, e ricavare altre informazioni.

Ecco un esempio classico di questo tipo di indovinelli: il visitatore incontra due abitanti dell’isola, Alice e Bob. La prima afferma che sia lei che Bob sono furfanti. Si tratta di capire se i due sono sinceri o bugiardi. Ebbene, per scoprirlo basta un piccolo ragionamento. Supponiamo che l’affermazione di Alice sia vera, cioè che Alice sia una furfante: ma se è così, non può mai dire cose vere, quindi dobbiamo scartare questa ipotesi.
Ne consegue che la frase è falsa, cioè non è vero che sia Alice che Bob sono furfanti. D’altra parte Alice non può essere un cavaliere, perché se così fosse non avrebbe affermato il falso. Quindi l’unica possibilità è che Alice sia una furfante e Bob un cavaliere.

Torniamo al nostro enigma. Anche questo, come il precedente sul “Palomar Cube”, non era di immediata soluzione. Ma come nel caso precedente non occorrevano particolari conoscenze logiche o matematiche per risolverlo: bastava un po’ di ragionamento logico e un pizzico di pazienza. Vediamo come poteva essere risolto il problema, iniziando dal primo quesito, quello della determinazione del pianeta del tesoro.
I pianeti possibili sono 8, da Mercurio a Nettuno, e le domande a disposizione sono 3, per ciascuna delle quali vi sono 2 possibili risposte (sì o no). Non a caso, 2 elevato alla 3 è proprio uguale a 8. La serie di domande deve essere quindi organizzata in modo che a ogni risposta il numero di pianeti candidati si dimezzi: dopo la prima risposta avremo 4 pianeti ancora in lizza, dopo la seconda risposta questi si saranno ridotti a 2, e finalmente la terza risposta ci fornirà l’indicazione risolutiva. Il grosso guaio è che quando rivolgiamo una domanda al rappresentante di un pianeta, non possiamo sapere a priori se quel pianeta sia bianco o nero, cioè se il nostro interlocutore sia sincero o bugiardo.
Come fare, allora? Il trucco consiste nel formulare le domande in un modo un po’ particolare. Supponiamo che io chieda di parlare con il rappresentante di un pianeta qualsiasi, diciamo Giove, e gli rivolga la seguente domanda:

«Se tu fossi il rappresentante di un pianeta di colore opposto al tuo, e ti venisse rivolta la domanda “Il pianeta col tesoro è uno dei primi quattro del sistema solare?”, come risponderesti?» 

Fateci caso: indipendentemente dal fatto che il nostro interlocutore gioviano sia sincero o no, la sua risposta sarà, per così dire, la combinazione tra la risposta di un sincero e quella di un mentitore, per cui sarà sicuramente il contrario della verità.

Vediamo la cosa più in dettaglio: se Giove è pianeta di galantuomini, il nostro interlocutore è sincero. Ma noi gli chiediamo di immaginare di essere un bugiardo! Quindi, da sincero qual è, il gioviano ci risponderà, candidamente, come farebbe un bugiardo, e noi dovremo assumere come vera la risposta opposta alla sua. Se, ad esempio, lui rispondesse “Sì”, saremmo certi che il tesoro si trova in uno nei pianeti esterni del sistema solare.

Una formulazione leggermente diversa della domanda è la seguente:

«Se tu rivolgessi al rappresentante di un pianeta di colore opposto al tuo la domanda “Il pianeta col tesoro è uno dei primi quattro del sistema solare?”, come risponderebbe?» 

Anche in questo caso la risposta risulterà dalla concatenazione tra la risposta di un sincero e quella di un mentitore, e dovremo considerare l’opposto per arrivare alla verità.
Invece, consideriamo la seguente formulazione alternativa:

«Se tu chiedessi a un tuo concittadino: “Il pianeta col tesoro è uno dei primi quattro del sistema solare?”, lui come risponderebbe?» 

Questa volta vengono combinate insieme le risposte fornite da abitanti dello stesso pianeta, quindi entrambi sinceri o entrambi bugiardi. Nel primo caso la risposta sarà evidentemente sincera. Nel secondo la risposta sarà l’opposto dell’opposto della verità, quindi ancora sincera. In definitiva, a differenza delle due precedenti, questa nuova formulazione fornirà direttamente la risposta che cerchiamo. In tutti i casi, abbiamo trovato alcune possibili domande che, indipendentemente dalla natura (sincera o meno) degli interlocutori, ci permettono di dimezzare (da 8 a 4) il ventaglio dei pianeti candidati: a seconda della risposta, scopriremo in quale parte del sistema solare si trovi il tesoro. Se il tesoro si trova in uno dei pianeti interni del sistema solare, rivolgeremo di nuovo la stessa domanda, modificata soltanto nella parte in cui ci si riferisce all’insieme dei pianeti candidati. Utilizzando la prima delle formulazioni proposte:

«Se tu fossi il rappresentante di un pianeta di colore opposto al tuo, e ti venisse rivolta la domanda “Il pianeta col tesoro è tra il primo e il secondo del sistema solare?”, come risponderesti?» 

Se invece apprendiamo che il tesoro si trova tra i pianeti esterni:

«Se tu fossi il rappresentante di un pianeta di colore opposto al tuo, e ti venisse rivolta la domanda “Il pianeta col tesoro è tra il quinto e il sesto del sistema solare?”, come risponderesti?» 

La risposta ci permetterà di ridurre a due l’insieme dei pianeti possibili. A questo punto ci basterà ripetere per la terza volta la stessa domanda, opportunamente modificata (ormai avete capito come fare), per arrivare all'individuazione finale del pianeta del tesoro.

Il secondo enigma era un po’ più facile. Supponiamo che l’affermazione del forestiero, “Io e il mio capo proveniamo da due pianeti dello stesso colore”, sia vera. Ciò implica che forestiero e custode siano entrambi sinceri o entrambi bugiardi. Ma se sono entrambi bugiardi, l’affermazione del forestiero non può essere vera, e cadiamo in una contraddizione. Se invece sono entrambi sinceri, contraddizioni non ce ne sono.
Se invece l’affermazione iniziale è falsa, il forestiero e il custode sono l’uno sincero e l’altro bugiardo: e avendo ipotizzato che il forestiero ha mentito, rimane la possibilità che il forestiero sia bugiardo e il custode sia sincero.
Guardate bene: in entrambi i casi, abbiamo dedotto che il custode dev’essere sincero. Questo significa che il pianeta del tesoro è un pianeta bianco, e quindi per scoprire quale sia la caverna del tesoro dobbiamo chiedere al custode, e credere alla sua risposta.
Rivolgendo la domanda al forestiero, invece, non potremmo avere certezze, dato che è impossibile determinare se egli sia sincero o mentitore.
Notate infine che la certezza della sincerità del custode ci rassicura anche sulla verità della sua affermazione iniziale: “Il tesoro si trova in una delle due. Nell’altra c’è un baratro: chi vi entra cade e muore.”
Quell'affermazione rappresentava, in un certo senso, la premessa dell’enigma: se fosse risultata falsa, o indecidibile, avremmo potuto dubitare sulla fondatezza stessa del problema, e sarebbe stato un bel guaio.

Un lettore di Coelum è riuscito a sbrogliare l'intricata matassa, utilizzando la “prima” formulazione per le domande necessarie a individuare il pianeta del tesoro.
Ha anche osservato, correttamente, che le tre domande possono essere indifferentemente poste allo stesso interlocutore, a tre interlocutori diversi su diversi pianeti, o a un “mix” dei due.
Sempre con riferimento al primo dei due enigmi, il lettore ha fatto notare che la struttura delle domande da rivolgere agli abitanti è un albero binario, come quello indicato nella figura a fianco, in cui i nodi interni rappresentano le domande, gli archi le risposte, e i nodi “foglia” indicano i pianeti possibili sedi del tesoro.

giovedì 10 settembre 2015

Il ritorno di Mr. Palomar

Tranquilli, Mr. Palomar è tornato. Non che se ne fosse andato, ma in effetti erano passati quasi due mesi dall'ultimo post, e questo non è molto bello in un blog che si rispetti. Non accadrà più, almeno spero.
In queste ultime settimane sono successe un po' di cose che mi hanno impedito di aggiornare questo spazio con la consueta frequenza. Soprattutto ho cambiato lavoro: sono diventato uno che oltre a raccontare la matematica attraverso libri, articoli e post, da quest'anno cercherà di insegnarla anche a scuola.
Parte una nuova avventura, insomma. Ma intanto Mr. Palomar torna a funzionare come si deve.
Buona lettura a tutti.

La top ten dei miei video su YouTube (1° posto)

Rullo di tamburi! Eccoci finalmente in vetta! E, devo dire, la vetta della classifica dei miei video su YouTube appare per il momento davver...