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
Taifu
Semidio
Semidio


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

MessaggioInviato: 28 Ott 2006 10:46    Oggetto: * QUIZ: Il problema piu` difficile del mondo Rispondi citando

Tantissimi anni fa ricordo di aver letto su Repubblica questo problema che era definito come il piu` difficile del mondo.
Dico subito che non lessi la soluzione per tentare di risolverlo da solo, senza ovviamente riuscirci.
Ora che ho conosciuto questo forum lo posto qui e, se troviamo la soluzione giusta, lo capiremo da soli (ovviamente non ho cercato su Google e non intendo farlo).

La formulazione e` semplice.
Solita isola con tre gruppi di persone: V, F, C che rispettivamente dicono sempre il Vero, il Falso o rispondono assolutamente a Caso.
Purtroppo parlano una lingua a noi sconosciuta e alle nostre domande rispondono con un DA e MA che sappiamo voler dire Si` e No ma non sappiamo in che ordine.
Incontriamo tre persone, una per gruppo, e abbiamo tre domande per individuare la loro appartenenza a V, F e C.

Nota postuma: il problema non chiede la decodifica di DA e MA (per ora, non si sa se sia necessario o meno decodificarli per risolvere il problema)

Tosto, vero? Wink

Ciao.
Marco.
P.S. Perdonatemi se e` roba vecchia e nota (cosa possibile visto che l'ho letto piu` o meno 15 anni fa).
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 30 Ott 2006 12:45    Oggetto: Rispondi citando

Ah, ecco!
Una versione più complessa del classico bidimensionale (due persone, due domande, due risposte).

Di sicuro per me è non banale ovvero non mi arriva la risposta al volo ma mi servono carta, penna e tempo per pensarci...

[thinking]...
clicco su <Invia> con un tremito... sto entrando in un loop infinito?
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 31 Ott 2006 20:10    Oggetto: Rispondi citando

Non sono ancora arrivato alla soluzione (e non so se mai ci arriverò) ma una cosa l'ho capita:
di certo gli abitanti di quell'isola sono più colti di noi (infatti loro capiscono noi ma noi loro no) e sono anche un pochetto stronzi (perché volendo potrebbero farsi capire)...
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 31 Ott 2006 23:53    Oggetto: Rispondi citando

[/thinking] Yuppi

Come codificare il problema:
Citazione:
Ogni affermazione può essere o vera o falsa.
Chiamiamo stato di una affermazione il suo essere vera o falsa.

Rappresentiamo lo stato di una affermazione con un vettore colonna:
v=[1/0] se l'affermazione è vera
f=[0/1] se è falsa.

Quando un'affermazione passa per la bocca di qualcuno il suo stato viene modificato in funzione del comportamento tenuto da quel qualcuno.

I comportamenti qui codificati sono: sincero, menzognero e casuale.

Ogni affermazione può essere messa sotto forma di domanda (basta aggiungere un punto interrogativo in fondo!).
La risposta alla domanda dipende dallo stato dell'affermazione e dal comportamento della persona alla quale domandiamo.
Qualunque sia lo stato di una affermazione, un comportamento sincero lo lascerà inalterato, uno menzognero lo invertirà e uno casuale lo metterà in sovrapposizione.

Dunque un comportamento può essere rappresentato da una matrice 2x2 e la risposta ad una domanda sarà data dal prodotto (matriciale) del vettore di stato per la matrice di comportamento.

Il comportamento sincero sarà rappresentato dalla matrice identità: I=[1,0/0,1].
Infatti Iv=v e If=f

Il comportamento menzognero sarà rappresentato dalla matrice not: X=[0,1/1,0].
Infatti Xv=f e Xf=v

Il comportamento casuale sarà rappresentato dalla matrice U=[1,1/1,1]
Infatti Uv=Uf=[1/1] (che equivale tanto a VERO che a FALSO e che di seguito, per semplicità, indicheremo con BOH).

Ora occupiamoci dei comportamenti composti (di ordine 2) ovvero delle domande del tipo:
chiedo ad A cosa risponderebbe B se gli ponessi la domanda s
Le risposte si codificano così:
ABs
dove A è la matrice del comportamento del signor A, B quella del comportamento del signor B ed s è lo stato della affermazione usata nella nostra domanda
Il prodotto (matriciale) tra A e B è ancora una matrice di comportamento.

Osserviamo che, per come sono fatte le matrici I, X e U, il prodotto è simmetrico ovvero AB=BA qualunque siano le matrici A e B.

Questa simmetria suggerisce la seguente, curiosa quanto inutile, osservazione:
il comportamento di gruppo è frutto di un mix dei comportamenti dei singoli e basta un bugiardo perché la sincerità del gruppo sia minata dunque la sincerità è come un gene recessivo (questo spiegherebbe perché al mondo ci sono più bugiardi che sinceri).

Le possibili formulazioni della domanda sono 9 (tante quanti i possibili prodotti AB) ma, per la simmetria di cui sopra, si riducono a 6.
Tre di queste coinvolgono due persone:
IX=X (chiedo a un sincero cosa risponderebbe un bugiardo o viceversa che è come chiedere direttamente ad un bugiardo)
IU=U (chiedo a un sincero cosa risponderebbe un casuale o viceversa che è come chiedere direttamente a un casuale)
XU=U (chiedo a un bugiardo cosa risponderebbe un casuale o viceversa che è come chiedere direttamente a un casuale)

Le altre tre coinvolgono una persona e sono le più interessanti:
II=I (chiedo a un sincero cosa risponderebbe se gli ponessi una domanda che è come chiedere direttamente a un sincero)
XX=I (chiedo a un bugiardo cosa risponderebbe se gli ponessi una domanda che è come chiedere direttamente a un sincero)
UU=U (chiedo a un indeciso cosa risponderebbe se gli ponessi una domanda che è come chiedere direttamente a un casuale)

Infine occupiamoci dei comportamenti composti (di ordine 3) ovvero delle domande del tipo:
chiedo ad A cosa risponderebbe B se gli chiedessi cosa risponderebbe C se gli ponessi la domanda s.
Le risposte si codificano così: ABCs
Sempre a causa della simmetria, i comportamenti "tripli" sono tutti equivalenti a IXU=U


Strategia:
Citazione:
Poiché non so chi tra le tre persone sia sincero, chi bugiardo e chi indeciso non ha alcun senso formulare domande diverse.
In altri termini devo fare la stessa domanda a tutti e tre e tirare le conclusioni dalle loro risposte.

Che tipo di domanda porre?
Una domanda semplice, qualunque sia il suo stato, produrrà sempre la terna di risposte SI/NO/BOH e di conclusioni non ne tiro manco mezza.

Una domanda composta di ordine 3 produrrà sempre la terna di risposte BOH/BOH/BOH e di conclusioni ne tiro ancora meno.

Non restano quindi che le domande composte di ordine 2.
Quelle del primo tipo (che coinvolgono due persone) daranno come risposta NO/BOH/BOH se l'affermazione con la quale ho costruito la domanda è vera SI/BOH/BOH altrimenti. In entrambi i casi non riesco a discriminare alcunchè.

Quelle del secondo tipo, invece, daranno come risposta SI/SI/BOH se l'affermazione di base è vera e NO/NO/BOH se l'affermazione di base è falsa.

Con questo ultimo tipo di domande ho almeno due casi su tre in cui lo stato dell'affermazione originale non cambia.
Pertanto mi basterà costruire la domanda con una qualsiasi affermazione che so essere vera per avere certezza che la risposta preponderante corrisponderà al sì.


Ecco la risposta cioè la domanda Shocked :
Citazione:
Cosa risponderesti se ti chiedessi se io sono io?


Spiegazione:
Citazione:
Col sincero il problema non si pone in virtù della sua linearità.
Con l'indeciso il problema non si pone tanto non gli si dà credito.
Consideriamo quindi solo il bugiardo.
La domanda doppia lo costringe a mentire due volte lasciando così inalterato lo stato dell'affermazione (al pari del sincero).
Infatti alla domanda "io sono io?" lui risponderebbe NO quindi per mentire alla domanda "cosa risponderesti se ti chiedessi se io sono io?" lui è costretto a rispondere SI altrimenti direbbe la verità...


Una perplessità:
Citazione:
In questo tipo di problemi l'impostazione è tale da escludere la possibilità di porre domande la cui risposta è nota. Qui tale vincolo non compare quindi la mia proposta dovrebbe essere accettabile eppure mi pare poco elegante proprio perché non rispetta quel vincolo. Esisterà un modo per arrivare al risultato senza far uso di domande con risposta nota a priori?
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: 23 Nov 2006 08:23    Oggetto: Rispondi citando

Ciao a tutti 8)
Prima di tutto i miei complimenti a Ulisse per l'analisi, ma avrei qualche domandina a riguardo.

ulisse ha scritto:

Ecco la risposta cioè la domanda Shocked :
Citazione:
Cosa risponderesti se ti chiedessi se io sono io?

Spiegazione:
Citazione:
Col sincero il problema non si pone in virtù della sua linearità.
Con l'indeciso il problema non si pone tanto non gli si dà credito.
Consideriamo quindi solo il bugiardo.
La domanda doppia lo costringe a mentire due volte lasciando così inalterato lo stato dell'affermazione (al pari del sincero).
Infatti alla domanda "io sono io?" lui risponderebbe NO quindi per mentire alla domanda "cosa risponderesti se ti chiedessi se io sono io?" lui è costretto a rispondere SI altrimenti direbbe la verità...

Non vedo come si riesca a capire chi è chi, nel senso che
Citazione:
facendo la domanda che hai posto si otterrebbero tre sì oppure due sì e un no (quello del casuale) e così saprai cosa vuol dire sì e per esclusione cosa no, ma non puoi distinguere il veritiero dal menzognero dal caotico nel primo caso e il veritiero dal menzognero nel secondo (il caotico è quello che risponde diversamente dagli altri due)


Ulisse ha scritto:

Una perplessità:
Citazione:
In questo tipo di problemi l'impostazione è tale da escludere la possibilità di porre domande la cui risposta è nota. Qui tale vincolo non compare quindi la mia proposta dovrebbe essere accettabile eppure mi pare poco elegante proprio perché non rispetta quel vincolo. Esisterà un modo per arrivare al risultato senza far uso di domande con risposta nota a priori?

Dalla tua analisi manca un caso:
Citazione:
le domande di ordine due riferite a loro stessi cioè del tipo "Se ti facessi una domanda mi risponderesti sinceramente?" che equivale a "Tu dici sempre la verità?" : il sincero e il bugiardo cronico risponderanno entrambi sì, il caotico a caso. Ancora una volta però ponendo la stessa domanda a tutti e tre capirei cosa significa sì e no e al massimo chi è il caotico, sempre che mi risponda in modo diverso dagli altri, altrimenti manco quello.


Io avrei fatto queste considerazioni
Citazione:
I tre tizi possono essere in un ordine qualsiasi e ci sono sei possibilità

Codice:
V-F-C     V-C-F     F-V-C     F-C-V     C-V-F     C-F-V

che rapportati alle risposte diventano 12 casi (con Cv indico il caotico che dice il vero, con Cf il caotico che dice il falso)

Codice:
V-F-Cv    V-F-Cf    V-Cv-F    V-Cf-F    F-V-Cv    F-V-Cf
F-Cv-V    F-Cf-V    Cv-V-F    Cf-V-F    Cv-F-V    Cf-F-V

che però sono indistinguibili a coppie (cioè come posso distinguere V-Cv-F da Cv-V-F o V-Cf-F da V-F-Cf?). Inoltre le risposte possibili sono otto

Codice:
DA-DA-DA  DA-DA-MA  DA-MA-DA  MA-DA-DA  MA-MA-DA  MA-DA-MA  DA-MA-MA  MA-MA-MA

però non sapendo cosa significa sì e cosa no anch'esse sono indistinguibili a coppie (posso ragionare solo considerando che ci sono tre risposte uguali o una diversa al primo posto o una diversa al secondo o una diversa al terzo) e non vedo come ricavare con soli quattro indizi quale sia l'ordine giusto di dodici possibili, tra l'altro, come detto, indistinguibili a coppie. L'unica via d'uscita che vedo, anche se non ho ancora la soluzione, è che le tre domande possano essere fatte a chi si vuole, non necessariamente una ciascuno, e che in più il caotico alterni una verità ad una bugia, anche se non sappiamo come risponderà alla prima domanda. Ad esempio se faccio a uno degli indigeni queste due domande: "DA vuol dire sì?" e "DA vuol dire no?" otterrò come risposte DA-MA dal veritiero, MA-DA dal menzognero, DA-DA dal caotico che prima dice la verità e poi mente e MA-MA dal caotico che prima mente poi dice la verità, il tutto indipendentemente da cosa vuol dire veramente DA. Non mi viene in mente quale domanda fare e a chi per poter in un colpo solo individuare cosa significa DA (o MA) e discriminare chi siano gli altri due.


Saluti a tutti Ciao
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 25 Nov 2006 14:09    Oggetto: Rispondi citando

Furibondo Giovedì non avevi niente di meglio da fare? Furibondo

Very Happy

Hai ragione...
La mia soluzione individua il sì e il no ma non dice chi è chi...

Mi tocca rimettermi in modalità
[thinking]
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: 26 Nov 2006 20:07    Oggetto: Rispondi citando

ulisse ha scritto:
Mi tocca rimettermi in modalità
[thinking]


Avrei pensato quest'altro se può servire.
Citazione:
Come ho detto ci sono otto possibili successioni di risposte. Se noi concentriamo le tre domande su una sola persona e consideriamo i due casi DA=sì e DA=no per ognuno di essi, partendo sempre dall'ipotesi che il caotico alterni verità e bugie, ho quattro possibili persone tra cui posso scegliere cioè il veritiero, il menzognero, il caotico che inizia dicendo la verità e quello che inizia con una bugia: totale 2 x 4 = 8 , come le possibili successioni di risposte. Con le domande giuste potrei distinguere in quale situazione mi trovo (cioè a chi sto facendo le domande e cosa vuol dire DA) ma almeno una delle domande mi dovrebbe permettere anche di individuare uno degli altri due ..... mumble....mumble....Think
Top
Profilo Invia messaggio privato
madvero
Amministratore
Amministratore


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

MessaggioInviato: 27 Nov 2006 23:49    Oggetto: Rispondi citando

non capisco il problema.
Citazione:
prima domanda:
"io sono io?"
ripetuta per due volte, consente di individuare e scartare quello che risponde a casaccio
terza domanda (rivolta agli altri due):
"io sono te?"
e chi risponde il vero, cambierà risposta.
Top
Profilo Invia messaggio privato Invia e-mail HomePage
axlman
Dio minore
Dio minore


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

MessaggioInviato: 28 Nov 2006 00:47    Oggetto: Rispondi citando

madvero ha scritto:
non capisco il problema.

Il problema è che puoi fare tre domande in tutto, non tre domande diverse ognuna ripetuta quanto si vuole e a chi vuole. Shame on you

Ciao, ciao. Ciao
Top
Profilo Invia messaggio privato
madvero
Amministratore
Amministratore


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

MessaggioInviato: 28 Nov 2006 01:32    Oggetto: Rispondi

ok, adesso ho capito.
una domanda al primo, una al secondo e una al terzo, in tempi distinti, non la stessa a tutti e tre (appunto mi sembrava troppo facile)
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 1, 2, 3 ... 10, 11, 12  Successivo
Pagina 1 di 12

 
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