Olimpo Informatico

[ulisse]

[ulisse]

[ulisse]

[Taifu]

[axlman]

[ulisse]

[axlman]

[madvero]

[madvero]

HO la soluzione.
senza matrici e senza impazzire, ma con uno dei miei soliti ragionamenti (campati in aria).
magari è sbagliata, ma mi convince.
datemi solo il tempo di scriverla in modo che si capisca.

[ulisse]

Ecco il modello.
Ripeto cose già scritte sia per evitare di dover scorrere su e giù per tutto il topic a caccia dei vari pezzi sia per annullare tutti gli strafalcioni commessi durante la risoluzione.

Prima parte: come rappresentare il sistema e la sua evoluzione.
Per rappresentare i tre interlocutori usiamo tre variabili che chiamiamo x, y, z.
Ognuna potrà assumere uno dei tre valori s, b, c (corrispondenti a sincero, bugiardo e casuale).
Per rappresentare il significato di DA usiamo una variabile che chiamiamo 1. Essa potrà assumere uno dei due valori SI, NO.

Nel complesso il sistema sarà rappresentato da un vettore a quattro componenti [x, y, z, SI].

Le configurazioni che il sistema può assumere sono 12.
Poiché all'inizio non sappiamo quale sia la reale configurazione del sistema, tutte e dodici le configurazioni sono possibili.
Man mano che otteniamo informazioni, le configurazioni possibili si riducono.
Rappresentiamo le configurazioni possibili con una stringa binaria di 12 bit.
Ogni bit è associato ad una delle 12 configurazioni del sistema.
Se il bit è 1 significa che la corrispondente configurazione è possibile, viceversa che è impossibile (ovvero che tale configurazione è stata scartata perché incompatibile che le informazioni in nostro possesso).
Chiamiamo tale stringa "Stato del problema".



All'inizio lo stato del problema è (111111111111) a significare che, non avendo informazioni a disposizione, tutte configurazioni del sistema sono ancora possibili.
Man mano che acquisiamo informazioni il numero di bit impostati a 1 diminuisce.

Ad esempio lo stato (111111000000) significa che abbiamo scoperto che SI=1 ma nulla sappiamo su chi è chi.

Chiamiamo "lunghezza" della stringa la somma dei suoi bit. Essa è associata alla quantità di informazioni disponibili sul sistema.

All'inizio la lunghezza della stringa è, ovviamente, 12.

Poichè la richiesta del problema è individuare chi è chi ma non il significato di DA e MA, avremo risolto il problema quando arriveremo ad una stringa di lunghezza 2 nella quale i due bit pari a 1 occupano posizioni congrue tra loro modulo 6 come ad esempio (100000100000).
Le stringhe di lunghezza 1 indicano che la configurazione è stata completamente determinata.

Poiché l'acquisizione di informazioni modifica lo stato del problema dobbiamo trovare un modo per rappresentare le informazioni e le relative azioni sullo stato del problema.

Le informazioni saranno rappresentate ancora da una stringa binaria di lunghezza 12 identica in tutto e per tutto alla stringa di stato.
Ad esempio (111111000000) significa che abbiamo scoperto che SI=1.
Chiamiamo tale stringa "azione dell'informazione" (perché dice come l'informazione agisce sul problema).

Per applicare questa informazione al problema causandone un avanzamento verso la soluzione basta comporre la stringa d'azione con quella di stato tramite l'operazione AND.

Ad esempio se lo stato del problema è (101010101010) e l'azione dell'informazione acquisita è (111111000000) il nuovo stato del problema sarà (101010101010) AND (111111000000) = (101010000000).

Ora occupiamoci dell'altro versante.

Seconda parte: come rappresentare le risposte, come costruirle, classificarle e associarle alle azioni.
E' fondamentale constatare che le informazioni che ci consentiranno di avanzare nella risoluzione del problema non sono contenute affatto nelle domande ma solo e unicamente nelle risposte.
Paradossalmente potremmo astenerci dal formulare la domanda e limitarci allo schema di risposta perché è da esso e solo da esso che possiamo dedurre informazioni.

Occupiamoci dunque degli schemi di risposta.
Poiché la risposta ad una domanda dipende dall'interrogato e dal significato attribuito a DA avremo 6 possibili risposte che potremo collocare in una matrice 3x2.



L'ultima riga è sempre pre-compilata con 1/0 a significare che, qualunque domanda venga posta al casuale, potremo aspettarci come risposta tanto un 1 che uno 0.

In quanti modi diversi posso collocare 1 e 0 in una matrice siffatta?
Apparentemente 2^4 ma...
Osserviamo che scambiando tra loro le righe si ottengono matrici di risposta equivalenti e altrettanto scambiando tra loro le colonne. Analoga sorte se complementiamo il contenuto ovvero se scambiamo 0 e 1 tra loro.

Osserviamo anche che, grazie a queste equivalenze, possiamo limitarci a matrici con un solo 1 (ce ne è una sola), con due 1 (ce ne sono tre) e con quattro 1 (ce ne è una sola).
Quindi, a meno di scambi di righe e colonne, le matrici distinte sono solo 5.



ATTENZIONE: la corretta numerazione delle matrici nella figura qui sopra è, da sinistra verso destra: 4 - 2 - 3 - 5 - 1

Fissiamo, tra tutte le domande equivalenti, quella alla quale il sincero risponde SI. Useremo questa convenzione per la costruzione di tutte e cinque le matrici.

La matrice 2 fornisce lo schema di risposta a domande la cui verità non dipende nè dall'interlocutore nè dal significato di DA. Avendo scelto una domanda alla quale il sincero risponde SI, potremo compilare subito la matrice mettendo il segno del SI nella riga del sincero e il suo contrario in quella del bugiardo.
Un esempio di domanda associata a tale matrice di risposta è "1+1=2?"
Ma restando nel generico (ci servirà oltre) indicheremo con "V?" il rappresentante delle domande vere.

La matrice 3 fornisce lo schema di risposta a domande la cui verità dipende dal significato di DA. Ciò significa che messo un 1 nella casella in alto a sinistra (la risposta fornita dal sincero se SI=1) dovremo invertire la risposta cambiando riga e mantenerla cambiando colonna.
Un esempio di tali domande è: "SI=1?"
Il rappresentante di questa famiglia di domande è "V=1?"

La matrice 4 fornisce lo schema di risposta a domande la cui verità dipende dalla sincerità dell'interrogato. Ciò significa che messo un 1 nella prima casella dovremo mantenere la risposta cambiando riga e invertirla cambiando colonna.
Un esempio di tali domande è "Sei sincero?" oppure "Se ti chiedessi se 1+1=2 cosa risponderesti?"
Il rappresentante è "Se ti chiedessi V cosa risponderesti?"

La matrice 5 fornisce lo schema di risposta a domande la cui verità dipende sia dalla sincerità dell'interrogato che dal significato di DA. Ciò significa che messo un 1 nella prima casella dovremo mantenere la risposta cambiando sia riga che colonna.
Un esempio di tali domande è "Se ti chiedessi se 1+1=2 risponderesti 1?"
Il rappresentante è "Se ti chiedessi V risponderesti 1?"

Infine la matrice 1 apparentemente non ricalca alcuno schema di risposta semplice. In realtà può essere facilmente ottenuta con gli operatori booleani dalle precedenti matrici.
Ad esempio "V AND V=1?" che sceglieremo come rappresentante.

Queste sono tutte e sole le matrici 3x2.
Purtroppo non bastano a risolvere il problema e non esauriscono i possibili schemi di risposta.
Quindi dobbiamo generalizzare.
Notiamo che sinora abbiamo pensato a domande che coinvolgono solo un interlocutore.
Cosa succede se ne coinvolgiamo due contemporaneamente?
Succede che abbiamo accesso ad un nuovo set di domande rappresentate da matrici 3x6.

Non solo, come verificheremo tra poco, questo nuovo set di domande contiene anche le precedenti!
Esploriamo un po' il campo.

Innanzi tutto osserviamo che abbiamo due tipi di "contenitori".
Uno per rappresentare le domande del secondo ordine miste (Chiedo a x cosa risponderebbe y se gli ponessi la domanda A).

E l'altro per rappresentare le domande indirette (Chiedo a x i cazzi di y ovvero le tipiche domande alle quali una persona normale risponderebbe "ma vallo a chiedere direttamente a lui!")

Le matrici di risposta a domande del secondo ordine sono fatte così:



Invece quelle a domande indirette sono fatte così:



Poiché nelle domande del secondo ordine il comportamento casuale si trasmette queste sono meno potenti delle domande indirette (ci sono più risposte ambigue) perchè se chiedo al sincero (o indifferentemente al bugiardo) cosa risponderebbe il casuale se ... ottengo una risposta casuale.

Quindi concentriamoci sulle domande indirette.

Quante sono? Ricicliamo il trucchetto usato per costruire le matrici 3x2.
In quel caso si partiva dalla domanda alla quale il sincero risponde SI mettendo un 1 nella prima casella e estendendo tale valore al resto della matrice secondo le regole.



Ora però il caso base (l'1 da mettere nella prima casella) non è più un solo valore di risposta ma una terna di valori di risposta.
Sono le tre risposte date dal sincero nel caso la domanda sia riferita al sincero stesso, al bugiardo o al casuale.



Quante terne base possiamo costruire?
Ancora basta contare gli 1 e ricordare che gli scambi di colonna e le complementazioni conducono a terne equivalenti.
C'è una sola terna con due 1 (possiamo scegliere come rappresentante la terna 110).
C'è una sola terna con tre 1.
Ma la terna 111 significa che la risposta del sincero non dipende dal secondo interlocutore coinvolto.
E' come dire che possiamo fare a meno di coinvolgerlo.
E' come dire che le matrici costruite a partire da tale terna sono del tutto equivalenti alle matrici 3x2.
E' come dire che le matrici 3x6 sono generate (secondo il metodo usato per le 3x2) solo dall'unica terna 110.

Poichè il metodo genera 5 diverse matrici nel caso 3x2, altrettanto capiterà nel caso 3x6.

Ecco ad esempio la matrice 6 ottenuta combinando la stringa 110 con la regola adottata per costruire la matrice 1:



Osserviamo che la matrice si ricava rapidamente partendo dalla matrice 1 e sostituendo in essa la stringa 110 al posto degli 1 e la stringa 001 al posto degli 0.

Osserviamo inoltre che sostituire ad un 1 la terna 110 e ad uno 0 la terna 001 significa mettere al posto di un valore x la terna di valori (110 IIF x) dove IIF è la doppia implicazione.
Quindi la matrice 6 (che indichiamo con [6]) si ottiene semplicemente mettendo la stringa in IIF con la matrice 1 cioè:

[6] = 110 IIF [1]

Procedendo allo stesso identico modo si ricavano immediatamente anche le matrici
[x+5] = 110 IIF [x]

Manca solo un passaggio: attribuire le domande a queste nuove cinque matrici di risposta.

La costruzione è semplicissima.
Innanzi tutto scegliamo una domanda alla quale il sincero risponderebbe SI-SI-NO (che, nel caso SI=1, ci dà proprio la terna 110).
Il più semplice rappresentante di tale domanda è "y<>c?"

Poi, ricordando che [x+5] = 110 IIF [x], non ci resta che mettere la domanda associata a 110 in IIF con la domanda associata a [x] per ottenere la domanda associata a [x+5].
Ad esempio la domanda associata a [7] è "y<>c IIF V=1?"

Una finezza scoperta per caso.
Chiamiamo f(V) una domanda contenente la domanda V (quella che avevamo definito come sempre vera) e sia D un'altra domanda.
Vale la relazione D IIF f(V) = f(D).
Detto a parole: una qualsiasi domanda D composta tramite IIF con una domanda f che dipende da un'affermazione vera equivale alla domanda f in cui al posto dell'affermazione vera si sostituisce la domanda D.

Esempio.
Abbiamo visto che la domanda associata alla matrice 3 è "Se ti chiedessi V cosa risponderesti?"
Allora la domanda associata alla matrice 8 che nella prima forma risulta essere:
"y<>c IIF Se ti chiedessi V cosa risponderesti?"
grazie a questa finezza può essere espressa nella forma ben più chiara ed elegante:
"Se ti chiedessi se y<>c cosa risponderesti?"


Quarta e ultima parte: abbinamento matrici/azioni e ricerca delle soluzioni
Ora non ci resta che associare ad ognuna delle 10 matrici le corrispondenti azioni.

Ogni matrice 3x2 consente di formulare la domanda a 3 interlocutori, con 2 possibili risposte (1 piuttosto che 0).
Quindi ogni matrice 3x2 dà luogo a 3x2=6 azioni diverse.
Ogni matrice 3x6 dà luogo a 3x6=18 azioni diverse.
In totale, il set completo di domande fornisce 120 azioni differenti.

Fatto questo si calcola lo stato finale dopo l'applicazione di 3 domande nei 120^3 modi possibili.
Ricaveremo un elenco di 120^3 stati finali il quale verrà sottoposto a cancellazioni successive.
Innanzi tutto si cancellano tutti gli stati di lunghezza pari a 0 e maggiori di 2.
Poi si cancellano tutti gli stati di lunghezza 2 in cui gli 1 non sono nella posizione congrua modulo 6.
Resteranno così solo con gli stati che risolvono completamente il problema (lunghezza 1) o lo risolvono senza interpretare DA (lunghezza 2).
Poi si nota che affinchè una soluzione sia completa è necessario che accanto allo stato corrispondente alla risposta 1 alla terza domanda ci sia anche la risposta 0 (l'assenza di uno dei due significa che se alla terza domanda l'interrogato risponde in un modo risolvo il problema altrimenti no).
In conseguenza di ciò si cancellano tutti gli stati con terza domanda "disaccoppiata".
Si ripete il procedimento per la seconda domanda e infine per la prima (rigorosamente in quest'ordine!).

Quello che resta è l'insieme delle terne che conducono alla soluzione.
Ce ne sono 1632 che vanno però ancora suddivise e abbinate alle soluzioni complete.
Infatti ogni terna di domande compare più volte perché le domande possono essere rivolte a interlocutori diversi e per ogni combinazione di interlocutori ho anche le combinazioni delle possibili risposte.
Ad esempio la prima domanda (che non ha domande alternative) può essere posta in 12 modi differenti.
A seconda dei casi avrò modo di proseguire con differenti domande (ognuna con le sue rispettive combinazioni interlocutori/risposte).

In estrema sintesi tutto ruota intorno a 4 domande che possono essere combinate tra loro in 18 modi diversi.
Tenendo conto anche delle combinazioni degli interlocutori e del fatto che la scelta dell'interlocutore successivo dipende dalla risposta alla domanda precedente, si arriva a 1152 modi diversi di risolvere il problema.

Ecco l'albero dele soluzioni.
In ogni casella sono indicati a sinistra il numero della domanda e di fianco a destra i possibili modi di porre la domanda.

http://img286.imageshack.us/img286/7/alberosoluzioniky2.jpg

Chi volesse il file excel col programma di ricerca delle soluzioni ancora da eseguire (268KB) o lo stesso file dopo l'esecuzione (quindi con anche le soluzioni e le analisi finali - 341KB) può inviarmi un messaggio!

Ora è proprio tutto!

[Salmastro]

Scusate l?intrusione, sono un absolute beginner e mi scuserete anche se ripeterò cose già dette, essendomi perso nei labirinto dei post. Dico solo che ?il più difficile problema del mondo? era stato riproposto come ?il più difficile del secolo? nel 2001 sul mensile Linus, nella rubrica ?Scherzi da Peres?, dove ha tenuto banco per diversi mesi, fino alla pubblicazione della soluzione data da un lettore, del tipo, però, logico-formale, ineccepibile, in verità, ma poco ?giocosa?. Io non l?ho capita, ma è colpa mia, così come non sono riuscito a comprendere l?ultimo esaustivo intervento di Ulisse, sempre per mia colpa, massima colpa. Credo però di aver ugualmente a suo tempo risolto l?enigma, ma basandomi su quanto riportato nell?indispensabile ?Enigmi e Giochi Matematici? di Martin Gardner. Il problema lì prevedeva il classico bivio, un esploratore, due indigeni (V e F), due modi di dire SI e NO in lingua locale, a noi ignota, (p.es. MA e DA) ed una domanda per scoprire la strada che porta al villaggio. Testualmente Gardner scrive che l?esploratore dovrebbe indicare una delle strade e chiedere: ?Se io chiedessi se la strada che indico è quella per il villaggio, diresti MA??. Se l?indigeno risponde MA si può concludere che è proprio quella, anche non sapendo se ha parlato con un V o un F, né se MA significhi SI o NO, se l?indigeno risponde DA, si può trarre la conclusione opposta. E? facile verificare che è proprio così! Una interessante questione posta era sul concetto di BUGIA: si concludeva che F era sì bugiardo, ma non maligno, anzi onestissimo, tanto quanto V. Sicché il trucco della doppia negazione funziona. Nel nostro problema abbiamo un terzo indigeno C, ma dobbiamo supporre che anch?esso sia onesto, nel senso che è vero che risponde a caso, ma che all?interno di ogni ragionamento, sia pur concatenato, si comporti, casualmente ma onestamente, come se fosse un V o un F: cioè, la sua risposta è la stessa che darebbe V, se in modo casuale decidesse di comportarsi da sincero e viceversa. Ciò detto una possibile soluzione potrebbe essere la seguente, e smentitemi se sbaglio. Posti gli indigeni (chiamiamoli X, Y, Z) ai vertici di un triangolo, chiediamo p.es. a X, indicando quello alla sua destra (Y), ?se io chiedessi se l?indigeno che indico è un C, diresti MA??. Caso 1): dice MA, allora Y è un C! Sono fortunato, perché a questo punto mi basta addirittura una sola domanda per scoprire la tribù degli altri due. Chiedo a Y, indicando Z, ?se io chiedessi se l?indigeno che indico è un F, diresti MA?? Se dice MA lo è, in caso contrario è un V! Per esclusione individuo Y. Caso 2): risponde DA (due volte su tre). So che Y non è C, ma può essere solo V o F: proprio a lui rifaccio la stessa domanda, indicando Z. A seconda dei casi è C (MA + MA) o non lo è (MA + DA), e lo è X! A questo punto sono nella stessa situazione del caso 1) e a Z faccio, negli stessi opportuni termini la domanda finale.
Accetto critiche!!!
Salmastro

[Taifu]

[axlman]

[axlman]

Un applauso sentito a Ulisse per l'egregio lavoro svolto, che però ha la spiacevole caratteristica di causare l'emicrania

Posto quindi la mia soluzione più terra terra per chi non vuole laurearsi in matematica prima di risolvere l'enigma.

[madvero]

praticamente è il ragionamento che ho fatto io.
l'altra sera mi ero messa a scriverlo in maniera comprensibile, ma mentre lo buttavo giù, mi sono accorta che c'era qualcosa che non quadrava, e mi sono arenata.
anche nella tua c'è qualcosa che non mi quadra, ma non riesco a capire che cos'è.

ciao salmastro, benvenuto !!!

[Salmastro]

...è vero, ho introdotto una ulteriore condizione, troppo semplificante: ricordavo male! E solo ora ricordo che, all'epoca di Linus, come giustamente dice Axlman, avevo effettivamente elaborato che bisogna fare ad X una domanda del quarto tipo (che io chiamavo di M. Gardner), dalla quale dedurre il sicuro non-C, laddove C può essere X stesso o quello desunto dalla sua risposta (se X fosse un V o un F). Sia Y, p.es.: a lui rifacciamo la stessa domanda: abbiamo individuato C. Se è X, facciamo una domanda ad hoc a Z (la Gardner o una Alxman)...et voila!
Ma se fosse proprio Z? A questo punto abbiamo una sola domanda a disposizione e la dobbiamo fare per forza a Z!!!
Perchè, non so se è emerso, bisogna fare sì tre domande in tutto, ma solo una a ciascuno dei tre!!!
(almeno così recitava Peres)
ciao ragazzi,
Salmastro

[ulisse]

Ciao salmastro e benvenuto tra noi!

Ebbene, ammetto. I miei post sono peggio dei mattoni... Lo so...
Potevo limitarmi a postare una qualsiasi delle soluzioni che ho trovato e spiegare perché le domande individuate conducono alla soluzione.

Ma non è da me.
Io sono un insegnante sino alla radice del mio callo al mignolo del piede destro e non c'è cosa che possa fare che non sia accompagnata da spiegazioni esaustive e noiose!

Dopo aver risolto il problema ho cominciato a leggere altre soluzioni (individuate anche su indicazione di Taifu) ma ho trovato sempre e solo le risposte senza spiegazioni.
O meglio, senza quelle che io considero delle spiegazioni.

Ad esempio l'articolo originale di Boolos, (The Harvard review of philosophy, 6:62-65, 1996) la cui traduzione è stata pubblicata su la Repubblica, (link indicatomi da Taifu) è certamente comprensibile.
Spiega con linguaggio umano perché le domande funzionano ma nulla dice in merito a come e da dove tali domande siano piovute.

Altro esempio è l'articolo dei fratelli Rabern (per i curiosi: Landon Rabern lavora al dipartimento di matematica dell'Università della California, Santa Barbara).
Rimando ad esso per la bibliografia di riferimento e per una nota storica sull'enigma.
Questo secondo articolo affronta l'enigma non solo nella versione di Raymond Smullyan ma anche in alcune sue varianti.
L'aspetto a mio avviso più carino di tale articolo risiede nell'individuazione di una domanda che, mettendo in conflitto logico gli interlocutori, impedisce loro di rispondere e mandandoli in loop fino a far esplodere loro la testa!
Ma anche in questo caso le embedded questions (quelle che avevo chiamato domande del secondo ordine) vengono definite calandole dall'alto senza spiegazione alcuna.

E un povero mortale come me, scarsamente dotato di fantasia, come fa a inventarsele?

In effetti il mio problema è stato proprio questo: una volta individuate le possibili domande, la seconda parte della risoluzione è certamente meccanica ed eseguibile dal calcolatore ma come faccio a districarmi nella prima parte ovvero a individuare le possibili domande?

Nessuno tra i risolutori dell'enigma, siano essi comuni mortali (vedi qui) come me, siano essi filosofi o logici matematici ha saputo o voluto dichiarare il metodo che li ha condotti alla formulazione della domanda cruciale.

Quello che ho fatto, dunque, è stato riportare tutti i passi che mi hanno condotto alla domanda.
Chiunque sappia cosa sia una matrice e il prodotto righe per colonne, sappia cosa siano gli operatori booleani e li sappia applicare, conosca il significato di "stringa binaria" e abbia un po' di dimestichezza con gli spazi vettoriali e i relativi operatori lineari è in grado di capire come costruire le domande risolutive partendo da zero!
Non una domanda piovuta dall'alto, ma tutte le domande possibili costruite senza un briciolo di quella fantasia che, ahimè, non posseggo!

Certo, le soluzioni trovate in rete sono facili da leggere ma portano tutte a concludere che chi le ha trovate è un genio e che il lettore non sarà mai alla sua altezza.
La mia lunga dissertazione chiede, è vero, un minimo di conoscenze matematiche ma, superato tale scoglio, non mette me sul piano dei geni nè il lettore su quello degli incapaci.

Resta il fatto inequivocabile che io produco mattoni...

[madvero]

trovato niente in italiano?
perchè a questo punto preferisco le matrici (che un po' me le ricordo).

[ulisse]

[madvero]

ok.
vorrà dire che tradurrò i pezzi salienti e li posterò.