Indice del forum Olimpo Informatico
I Forum di Zeus News
Leggi la newsletter gratuita - Attiva il Menu compatto
 
 FAQFAQ   CercaCerca   Lista utentiLista utenti   GruppiGruppi   RegistratiRegistrati 
 ProfiloProfilo   Messaggi privatiMessaggi privati   Log inLog in 

    Newsletter RSS Facebook Twitter Contatti Ricerca
* QUIZ: Il problema piu` difficile del mondo
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici
Precedente :: Successivo  
Autore Messaggio
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 12 Dic 2006 16:24    Oggetto: Rispondi citando

axlman ha scritto:
CI SONO ARRIVATOOOOOOOOOOO!!!!

Evvai Evvai Evvai

Bèh, quasi, mi manca la prima domanda ma so che tipo di risposte deve dare e conto di arrivarci in giornata. Devo comunque ammettere che mi hanno aiutato i tre sottoproblemi postati da Taifu per riordinare le idee, almeno nella cronologia delle domande. Grazie
Visto che Ulisse ha remore a postare la risposta, aspetto anche io, ma ormai ci sono. Evvai!

CinCin


Evvai Evvai Evvai
Grande axlman!

Come ho remore? una delle 300 e rotti soluzioni che ho trovato (scusa ma il divario temporale tra la mia soluzione e la tua non è sufficiente e devo rimarcare con la quantità... Very Happy ) è spoilerata nella pagina precedente.

Dieci parole, apparentemente senza sottodomande.

Che dire.... ho il modello, più di 300 soluzioni, il set completo di matrici di risposta, domande corte ed eleganti...
Sono un figo!
Grazie Grazie Grazie
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 12 Dic 2006 16:46    Oggetto: Rispondi citando

Taifu ha scritto:
1) Una mia curiosità
2) E infine un'altra domanda
3) Comunque spero che alla fine, nonostante la mia imprecisione iniziale, il problema vi sia piaciuto.


1) vedi mio post precedente
2) non ho con me un libercolo di algebra booleana dove mi sembra di ricordare fossero definiti tutti gli operatori logici elementari.

A memoria mi sembra che la doppia implicazione non venga considerata elementare.
Su un testo di matematica per i licei la doppia implicazione viene definita come l'intersezione delle due implicazioni semplici.

Se lavori con le matrici di risposta anziché con le domande ti accorgerai che di operatori booleani ne serve uno solo per costruire la quinta matrice 3x2.
Tutte le altre combinazioni conducono a uno dei quattro casi semplici già considerati.
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 12 Dic 2006 17:11    Oggetto: Rispondi citando

Taifu ha scritto:
In realtà sono vietate le imposizioni di contenuto, non di forma. Altrimenti anche l'AND sarebbe una forma di imposizione, non trovi?


Vero. La doppia implicazione è a tutti gli effetti un operatore booleano e può essere utilizzata per costruire domande composte.
Top
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 12 Dic 2006 17:16    Oggetto: Rispondi citando

ulisse ha scritto:
Ma secondo me la cosa più interessante non è la soluzione bensì il modello.
E soprattutto, da dove sono piovute le domande?
A qualcuno interessa? 8)


Sì, a me interessa parecchio: da dove sono piovute le domande?

P.S. Se te lo chiedi, la risposta è sì, il messaggio privato che ti ho spedito è partito prima che leggessi con attenzione questo tuo post... Wink
Top
Profilo Invia messaggio privato
axlman
Dio minore
Dio minore


Registrato: 19/10/06 16:58
Messaggi: 582
Residenza: l'Universo più scalcinato del Multiverso

MessaggioInviato: 12 Dic 2006 18:00    Oggetto: Rispondi citando

Taifu ha scritto:
Ullallà... questa mi ha sorpreso... sei proprio sicuro?
Non capisco proprio come 3 domande binarie possano discernere tra 12 combinazioni.
A meno che tu non rischi, in certi casi, di metterci 4 domande non credo sia possibile.
Dai, illuminami d'immenso! (ma davvero, senza ironia)
Smile

Dietrofront, avevo fatto una piccola confusione in un caso. Ho controllato meglio e confermo che le mie tre domande funzionano ma DA e MA non si possono distinguere.
Scusate... Embarassed
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 12 Dic 2006 18:13    Oggetto: Rispondi citando

axlman ha scritto:
P.S. Scusa Ulisse ho fatto un doppio post nel thread QUIZZIES-Enigmi non matematici. Puoi eliminarlo? Grazie.

Non l'ho trovato. Mi sa che ha già provveduto qualcunaltro!
Top
Profilo Invia messaggio privato HomePage
axlman
Dio minore
Dio minore


Registrato: 19/10/06 16:58
Messaggi: 582
Residenza: l'Universo più scalcinato del Multiverso

MessaggioInviato: 12 Dic 2006 18:24    Oggetto: Rispondi citando

ulisse ha scritto:
Dieci parole, apparentemente senza sottodomande.

Che dire.... ho il modello, più di 300 soluzioni, il set completo di matrici di risposta, domande corte ed eleganti...
Sono un figo!
Grazie Grazie Grazie

Certo che ne hai di fantasia, a me è venuta in mente solo una domanda, o meglio ci sono inciampato facendo una piccola variante su una classica doppia. Tra l'altro l'avevo trovata come terza e solo dopo mi sono accorto che funzionava anche come prima.

Sono curioso, postacene qualcuna (ho guardato il tuo spoil: la prima è simile alla mia, tranne che per una negazione, la seconda è identica ma d'altro canto è dall'inizio che la meno con quella, la terza manca proprio).

8)
Top
Profilo Invia messaggio privato
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19228
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 12 Dic 2006 21:39    Oggetto: Rispondi citando

ulisse ha scritto:
Non l'ho trovato. Mi sa che ha già provveduto qualcunaltro!

oh, yes.
io sono molto buona !
tolgo i doppioni, spoilero i post venuti male...

Innocente Innocente Innocente
Top
Profilo Invia messaggio privato Invia e-mail HomePage
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19228
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 12 Dic 2006 21:59    Oggetto: Rispondi citando

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.
Top
Profilo Invia messaggio privato Invia e-mail HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 12 Dic 2006 23:14    Oggetto: Rispondi citando

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!

Phew Phew
Top
Profilo Invia messaggio privato HomePage
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 15 Dic 2006 13:12    Oggetto: il quesito +... Rispondi citando

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
Top
Profilo Invia messaggio privato AIM Yahoo MSN
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 15 Dic 2006 20:02    Oggetto: Re: il quesito +... Rispondi citando

salmastro ha scritto:
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.


La premessa è sbagliata in questo punto.
Il casuale getta la moneta e in base al risultato non si comporta come V o F ma risponde DA o MA.
In realtà la formulazione su Repubblica non era così ma è evidente (e in altri siti è chiaramente specificato) che se vogliamo pensare ad un indovinello veramente difficile, il casuale deve essere totalmente casuale e non sincero o bugiardo a caso. Il nostro primo compito è quello di individuare un non casuale e a quello fare le nostre domande con doppia negazione.

E` ben diverso! Wink

Ciao.
Marco.
Top
Profilo Invia messaggio privato
axlman
Dio minore
Dio minore


Registrato: 19/10/06 16:58
Messaggi: 582
Residenza: l'Universo più scalcinato del Multiverso

MessaggioInviato: 15 Dic 2006 20:17    Oggetto: Re: il quesito +... Rispondi citando

salmastro ha scritto:
Scusate l?intrusione, sono un absolute beginner e mi scuserete anche se ripeterò cose già dette, essendomi perso nei labirinto dei post.

Ciao salmastro e benvenuto!!! Ciao
Non ti preoccupare, qui chiunque sia interessato è il benvenuto.

Riguardo la tua soluzione, come ha già detto Taifu, in realtà il casuale non si comporta in modo "onesto", dice DA o MA appunto a caso, senza nemmeno ascoltare la domanda.

Poi tu dici che se X risponde MA allora sicuramente Y è il caotico. In realtà, qualsiasi cosa risponda, il caotico potrebbe benissimo essere X.

Il tuo approccio va leggermente riveduto ma sei sulla strada giusta, hai già in mano il tipo di domanda che io invece ho impiegato giorni a trovare (tra l'altro per caso).

Ricorda che puoi fare tre domande in tutto e a chi vuoi, ma una domanda ripetuta due volte vale per due.

8)
Top
Profilo Invia messaggio privato
axlman
Dio minore
Dio minore


Registrato: 19/10/06 16:58
Messaggi: 582
Residenza: l'Universo più scalcinato del Multiverso

MessaggioInviato: 15 Dic 2006 22:27    Oggetto: Rispondi citando

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

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

Citazione:
Considerando solo il sincero e il bugiardo, che tanto il caotico è totalmente inaffidabile, le risposte possono essere catalogate in 4 categorie, in dipendenza anche delle incogite DA e MA.

Indico le risposte come doppie, con la prima risposta che vale per DA=sì e la seconda per DA=no.

Le domande più semplici sono quelle a cui il sincero da risposte diverse a seconda del significato di DA e il bugiardo risponde l'opposto, del tipo:
"Io sono io?"
S: DA/MA
B: MA/DA

Al secondo posto abbiamo le domande a cui sincero e bugiardo rispondono la stessa cosa, restando la dipendenza dal significato.
"Tu sei sempre sincero?"
S: DA/MA
B: DA/MA

Poi ci sono le domande a cui il sincero risponde comunque DA (o MA) e il bugiardo comunque l'opposto
"DA significa sì?"
S: DA/DA
B: MA/MA
"DA significa no?"
S: MA/MA
B: DA/DA

Infine ci sono le domande a cui sia sincero sia bugiardo rispondono la stessa cosa indipendentemente dal significato e per ottenerle bisogna comporre due domande semplici:
"Se ti chiedessi: ? E' vero che io sono io?? tu risponderesti DA?"
S: DA/DA
B: DA/DA

La prima cosa da fare è individuare qualcuno che sicuramente non sia il caotico, e mi serve una domanda del quarto tipo.
Chiedo al primo indigeno:
"Se ti chiedessi: ? E' vero che l'indigeno alla tua destra è il caotico? tu risponderesti DA?"
se l'indigeno indicato è il caotico S: DA/DA B: DA/DA
se l'indigeno indicato non è il caotico S: MA/MA B: MA/MA
Quindi se la risposta è DA mi rivolgo al terzo indigeno, se è MA mi rivolgo all'indigeno indicato.
La regola precedente va bene anche se il primo indigeno è il caotico, tanto in questo caso scelgo comunque un non caotico.
ATTENZIONE: proprio per il fatto che il primo potrebbe essere il caotico, la risposta DA non mi dà la certezza che l'indigeno indicato sia sicuramente il caotico.

All'indigeno che so sicuramente non essere il caotico, rivolgo ancora una domanda del quarto tipo:
"Se ti chiedessi: ? E' vero che l'indigeno alla tua destra è il caotico?? tu risponderesti DA?"
Se la risposta è DA l'indigeno indicato è il caotico, se la risposta è MA il caotico è l'altro.

A questo punto posso fare a uno qualsiasi dei non?caotici una domanda del terzo tipo.
"Da significa sì?"
Se la risposta è DA l'indigeno interrogato è il sincero e il rimanente è il bugiardo, viceversa se la risposta è MA.

Volendo si possono invertire la seconda e la terza domanda così da individuare subito il secondo indigeno che interrogo; naturalmente in questo caso la terza domanda devo farla ancora allo stesso indigeno, quello che so già essere sincero (o bugiardo).


Et voilà?Grazie

8)
Top
Profilo Invia messaggio privato
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19228
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 15 Dic 2006 23:51    Oggetto: Rispondi citando

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 !!!
Top
Profilo Invia messaggio privato Invia e-mail HomePage
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 16 Dic 2006 18:37    Oggetto: il problema sempre più difficile Rispondi citando

...è 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
Top
Profilo Invia messaggio privato AIM Yahoo MSN
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 17 Dic 2006 11:35    Oggetto: Re: il quesito +... Rispondi citando

Ciao salmastro e benvenuto tra noi!

Ebbene, ammetto. I miei post sono peggio dei mattoni... Lo so... Embarassed
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... Incupito
Top
Profilo Invia messaggio privato HomePage
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19228
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 17 Dic 2006 15:26    Oggetto: Rispondi citando

trovato niente in italiano?
perchè a questo punto preferisco le matrici (che un po' me le ricordo).
Top
Profilo Invia messaggio privato Invia e-mail HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 17 Dic 2006 16:43    Oggetto: Rispondi citando

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


Tra tutto ciò che ho trovato in rete, le migliori spiegazioni in italiano, modestamente, sono qui grazie ai contributi di tutti noi (compresa la tua idea di usare 1 e 0 al posto di DA e MA).
Top
Profilo Invia messaggio privato HomePage
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19228
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 18 Dic 2006 16:01    Oggetto: Rispondi

ok.
vorrà dire che tradurrò i pezzi salienti e li posterò.
Top
Profilo Invia messaggio privato Invia e-mail HomePage
Mostra prima i messaggi di:   
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici Tutti i fusi orari sono GMT + 1 ora
Vai a Precedente  1, 2, 3, 4, 5, 6  Successivo
Pagina 5 di 6

 
Vai a:  
Non puoi inserire nuovi argomenti
Non puoi rispondere a nessun argomento
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi votare nei sondaggi