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: 06 Dic 2006 16:16    Oggetto: Rispondi citando

Ciao Taifu!
In effetti ero preoccupato. Con solo 2 post al tuo attivo, la probabilità che fossi solo di passaggio e che non avresti più dato notizie era, a mio avviso, alta!

E a causa del teorema di Godel (il quale, applicato al nostro caso, afferma che esistono problemi irrisolubili che non è possibile dimostrare siano tali) sarei potuto morire senza nè trovare la soluzione nè dimostrare che la soluzione non esiste.

Ora sappiamo che questo problema ha soluzione e che quindi ha senso (almeno per me) continuare a cercarla!

Ti chiederei o di spedire privatamente la soluzione a qualcuno di noi (in modo che, eventualmente calate le braghe, quel qualcuno possa fornirla) o di essere tu a pubblicarla quando (e se) le braghe saranno calate!
Top
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


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

MessaggioInviato: 06 Dic 2006 16:50    Oggetto: Rispondi citando

ulisse ha scritto:
Ciao Taifu!
In effetti ero preoccupato. Con solo 2 post al tuo attivo, la probabilità che fossi solo di passaggio e che non avresti più dato notizie era, a mio avviso, alta!

E a causa del teorema di Godel (il quale, applicato al nostro caso, afferma che esistono problemi irrisolubili che non è possibile dimostrare siano tali) sarei potuto morire senza nè trovare la soluzione nè dimostrare che la soluzione non esiste.

Ora sappiamo che questo problema ha soluzione e che quindi ha senso (almeno per me) continuare a cercarla!

Ti chiederei o di spedire privatamente la soluzione a qualcuno di noi (in modo che, eventualmente calate le braghe, quel qualcuno possa fornirla) o di essere tu a pubblicarla quando (e se) le braghe saranno calate!


Tranquilli tutti: non ho intenzione di morire nei prossimi mesi (e se capita, peggio per voi). Se non mi faccio sentire per un po' mandatemi un messaggio privato.

Quello che suggerirei io, pero`, e` di vedere il primo sotto-indovinello se rinunciamo a risolvere il quesito principale. Certo che 15 anni sono tanti... Se non erro Wiles ce ne ha messi solo 7 per l'ultimo teorema di Fermat.
Quasi quasi vado a leggere la soluzione... Smile

Ciao.
Marco.
P.S. A proposito di problemi che non si sa se terminano, questa funzione (scritta in Python ma comprensibilissima) e` intrigante. Termina per qualsiasi N oppure no?

Codice:

def barbarossa(N):
    print N
    if not N==1:
        if (N % 2) == 0:
            barbarossa(N/2)
        else:
            barbarossa(N*3+1)
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 06 Dic 2006 17:28    Oggetto: Rispondi citando

axlman ha scritto:
Ma siamo sicuri sulla formalizzazione del comportamento del casuale? Lui non dice contemporaneamente il vero e il falso, ma solo il vero oppure il falso, siamo noi che non lo sappiamo distinguere.

Volendo sottilizzare, il casuale non risponde mai nè con la verità nè con la menzogna.
Forse la rappresentazione migliore è che lui non sta nemmeno ad ascoltare la domanda. Risponde a casaccio e basta.
Con "il casuale dice contemporaneamente il vero e il falso" intendevo dire che le sue risposte sono inutilizzabili per ogni speculazione perché non siamo in grado di distinguere il suo SI dato a caso da quello dato con logica dagli altri.
Tale fatto si riflette sull'impossibilità di ricavare informazioni dalla prima domanda se non dopo averne fatta almeno un'altra.

Citazione:
Se noi facciamo domande a cui un menzognero risponde allo stesso modo di un sincero, allo stesso identico modo dovrebbe rispondere anche un casuale, sia che decida di mentire che di dire la verità. O no?

No. Per quel che ne sappiamo, il casuale non sente nemmeno la domanda che gli poniamo tanto risponde a caso, purtroppo.

Sottolineo quel purtroppo perché stamattina credevo di aver individuato una domanda che forza il casuale a rispondere in un modo ben preciso ma temo di dovermi ricredere.

Poiché un casuale risponde a caso, su una serie infinita di ripetizioni della stessa domanda non può dare tutte le risposte 1. Quindi mettendo in AND tra loro le infinite risposte il risultato deve essere per forza 0.
Peccato però che prima di passarmi il risultato del calcolo lui modifichi a casaccio la risposta!
Top
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


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

MessaggioInviato: 06 Dic 2006 17:41    Oggetto: Rispondi citando

ulisse ha scritto:

Forse la rappresentazione migliore è che lui non sta nemmeno ad ascoltare la domanda. Risponde a casaccio e basta.


Nell'articolo il "casuale" risponde solo dopo aver gettato una moneta per aria (presumo lo faccia nella mente per cui non possiamo dire che il "casuale" e` quello che si gira buttando un euro per aria prima di risponderci).

ulisse ha scritto:

Poiché un casuale risponde a caso, su una serie infinita di ripetizioni della stessa domanda non può dare tutte le risposte 1. Quindi mettendo in AND tra loro le infinite risposte il risultato deve essere per forza 0.
Peccato però che prima di passarmi il risultato del calcolo lui modifichi a casaccio la risposta!


Esatto. E comunque non credo che la risposta contempli una domanda infinita (anche perche` le facciate di giornale usate sono un numero finito: 2).

Ciao.
Marco.
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 06 Dic 2006 19:22    Oggetto: Rispondi citando

Dopo aver risposto ai nuovi post, ecco un aggiornamento.
In questi giorni mi sono concentrato sulla classificazione delle domande e sulla modalità di rappresentazione delle risposte.
I nomi usati nella classificazione sono inventati al momento solo per avere un riferimento.

Ci sono domande utili e inutili, dirette e indirette, semplici e composte, del primo e del secondo ordine.
Forse ce ne sono anche di altri tipi ma io non ne ho trovate...

Le domande sono semplici se chiedono una sola cosa, sono composte (con operatori booleani) se chiedono più cose contemporaneamente.

Escludendo le domande inutili ai fini del problema del tipo "va bene risotto per cena?", le domande dirette possono essere:
- chiuse (la risposta è nota a tutti): "io sono io?"
- aperte (la risposta è nota solo all'interrogato): "SI=1?" oppure "sei sincero?"
Le domande indirette sono del tipo: "lui è sincero?"
Le domande del primo ordine sono le domande poste direttamente a qualcuno, quelle del secondo ordine sono del tipo chiedo al signor x cosa risponderebbe il signor y se gli ponessi la domanda A

Poiché abbiamo 3 interrogati (dei quali uno inattendibile) e 2 possibili traduzioni di SI e NO, le domande possono essere rappresentate da matrici 3x2 i cui elementi sono 0 e 1 (usando la convenzione adottata da Mad) tranne quando è coinvolto il casuale, nel qual caso avremo un 1/0 per intendere che posso aspettarmi come risposta sia un 1 che uno 0.
Per avere un più chiaro quadro di insieme, le domande del secondo ordine possono essere raccolte in una sola matrice 3x6 anziché in tre matrici 3x2.

Quante sono le domande semplici?
Permutare tra loro due righe o due colonne conduce a domande equivalenti (ad esempio permutando le colonne si ottiene una matrice di risposta corrispondente alla stessa domanda nella quale sono stati scambiati tra loro il SI e il NO).

Lo stesso dicasi per il complemento che consiste nello scambiare tra loro 0 e 1.

Le possibili matrici distinte tra loro a meno di permutazioni e complementi sono 5.
Di queste cinque, però, una non corrisponde a nessun tipo di risposta lecita perché viola un "vincolo strutturale".
Qualunque sia la domanda posta, infatti, scambiando il SI col NO, sincero e bugiardo devono reagire allo stesso modo: se il sincero continua a rispondere allo stesso modo altrettanto deve fare il bugiardo e se il sincero modifica la sua risposta altrettanto deve fare il bugiardo.
In altri termini le prime due righe della matrice di risposta non possono contenere solo un 1.

Dunque le possibili domande sono solo 4.


Ecco un elenco di domande associate a queste quattro matrici di risposta:
1)
Io sono io?
Se ti chiedessi se sei sincero cosa mi risponderesti?

2)
SI=1?
Se ti chiedessi se sei sincero mi risponderesti 1?

3)
Se ti chiedessi se io sono io cosa mi risponderesti?
Sei sincero?
Se ti chiedessi se SI=1 mi risponderesti 1?

4)
Se ti chiedessi se 1 vuol dire SI cosa mi risponderesti?
Se ti chiedessi se io sono io mi risponderesti 1?

Ecco qualche matrice che raggruppa le risposte alle domande di ordine 2 (la terza riga, tutta di 1/0, non compare per ragioni di spazio):



3b) Se gli chiedessi se io sono io cosa risponderebbe?
3c) è sincero?
3d) è caotico?
3e) se ti chiedessi se è caotico cosa risponderesti?
4b) Se gli chiedessi se 1 vuol dire SI cosa risponderebbe?
1b) Se gli chiedessi se è sincero cosa risponderebbe?

Dopo aver analizzato senza successo una grande quantità di combinazioni di domande sono giunto ad una conclusione.
Le domande vengono poste per ottenere informazioni (ovviamente vere).

Quante informazioni posso ottenere con una domanda?
Fissiamo il metro di misura.
1=SI (il verso codificato con 1 corrisponde a SI) è un'informazione. Altrettanto dicasi per x=s (il signor x è sincero).
Poiché NO è complementare a SI, per scoprire cosa è SI e cosa è NO, basta 1 informazione.
Invece per scoprire chi è chi servono 2 informazioni (perché, ad esempio, solo da x=s e y=b posso dedurre z=c).
Quindi mi servono 3 informazioni per risolvere il problema.

Torniamo al problema di prima: quante informazioni posso ottenere con una domanda?
Sinora ho concluso che non con tutte le domande ottengo la stessa quantità di informazioni e addirittura essa può variare a seconda della risposta e a seconda delle informazioni già in possesso.
Ad esempio ci sono domande che in caso consentono di discriminare tra SI e NO e nell'altro dicono solo che l'interlocutore non è il casuale.

Se fosse possibile classificare le domande in base alle quantità di informazioni che possono fornire forse si potrebbe restringere il campo di ricerca.

Inoltre ho notato che domande a risposta sbilanciata cessano di essere tali se precedute da altre.
In altri termini la quantità di informazioni che è possibile ottenere da un gruppo di domande varia a seconda dell'ordine con cui le domande vengono poste!

Ecco tutto quello che ho ricavato...
Pochino eh? Embarassed
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 06 Dic 2006 21:02    Oggetto: Rispondi citando

Taifu ha scritto:
E comunque non credo che la risposta contempli una domanda infinita (anche perche` le facciate di giornale usate sono un numero finito: 2).

Magari fosse quello il problema!
Non solo è possibile scrivere una serie infinita in poco spazio ma, grazie all'analisi infinitesimale, è anche possibile calcolare il risultato di una serie infinita con un numero finito di calcoli e, conseguentemente, in un tempo finito.
Quindi l'interrogatore può declamare la sua domanda in un tempo finito e l'interrogato può calcolare il risultato in un tempo finito.
Il problema è che dopo aver trovato la risposta lui tira la moneta e anziché comunicare la risposta, risponde in base all'esito del tiro.
Quindi quella che stamattina mi sembrava una grande trovata, in realtà, non vale nulla! Grrr
Top
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


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

MessaggioInviato: 07 Dic 2006 13:47    Oggetto: Rispondi citando

ulisse ha scritto:
Taifu ha scritto:
E comunque non credo che la risposta contempli una domanda infinita (anche perche` le facciate di giornale usate sono un numero finito: 2).

Magari fosse quello il problema!
Non solo è possibile scrivere una serie infinita in poco spazio ma, grazie all'analisi infinitesimale, è anche possibile calcolare il risultato di una serie infinita con un numero finito di calcoli e, conseguentemente, in un tempo finito.
Quindi l'interrogatore può declamare la sua domanda in un tempo finito e l'interrogato può calcolare il risultato in un tempo finito.


Chiaramente la mia era un battuta: sono passati quindici anni ma qualche rimasuglio di analisi 1 e analisi 2 mi e` rimasto tra le sinapsi... Smile
Eh si`, ho 42 anni (un numero che dice qualcosa agli amanti di Douglas Adams).

Ieri sera ho buttato un occhio (senza leggere) al resto dell'articolo. Posso garantire che le risposte non contengono simboli matematici o altro e il virgolettato della prima domanda e` poche righe, diciamo una quindicina di parole piu` o meno. Quindi dobbiamo limitarci alla pura logica senza tirare in ballo calcoli infinitesimali (che comunque non servirebbero con il "casuale").
Ciao.
Marco.
Top
Profilo Invia messaggio privato
Taifu
Semidio
Semidio


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

MessaggioInviato: 07 Dic 2006 14:22    Oggetto: Rispondi citando

ulisse ha scritto:

Ad esempio ci sono domande che in caso consentono di discriminare tra SI e NO e nell'altro dicono solo che l'interlocutore non è il casuale.


Come puo` una domanda dire che l'interlocutore non e` il casuale visto che quest'ultimo puo` anche rispondere sempre (anche se per caso) come un sincero o un bugiardo? Secondo me il casuale viene individuato per forza solo coniugando le risposte fatte a tutte e tre le persone, non potrebbe essere altrimenti.

ulisse ha scritto:

Se fosse possibile classificare le domande in base alle quantità di informazioni che possono fornire forse si potrebbe restringere il campo di ricerca.


Una risposta "dicotomica" al meglio puo` solo togliere meta` delle possibilita`.

Unendo le combinazioni di personalita` e significato delle risposte in apparenza le possibilita` sono 12 ma e` evidente che se cosi` fosse non ci sarebbe soluzione con solo tre domande "dicotomiche".

Dobbiamo quindi considare disgiunti i due ambiti ("chi e` chi" e "cosa vuol dire cosa") e trovare domande che ci diano risposte in entrambi.
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 07 Dic 2006 16:55    Oggetto: Rispondi citando

Taifu ha scritto:
Chiaramente la mia era un battuta: sono passati quindici anni ma qualche rimasuglio di analisi 1 e analisi 2 mi e` rimasto tra le sinapsi... Smile
Eh si`, ho 42 anni (un numero che dice qualcosa agli amanti di Douglas Adams).

Ieri sera ho buttato un occhio (senza leggere) al resto dell'articolo. Posso garantire che le risposte non contengono simboli matematici o altro e il virgolettato della prima domanda e` poche righe, diciamo una quindicina di parole piu` o meno. Quindi dobbiamo limitarci alla pura logica senza tirare in ballo calcoli infinitesimali (che comunque non servirebbero con il "casuale").
Ciao.
Marco.

Avevo capito che era una battuta ma la pignoleria è più forte di me. Non ho potuto fare a meno di puntualizzare! Embarassed

Una quindicina di parole?!? Shocked
La domanda più lunga e contorta che sono riuscito a immaginare ne conta solo 10! Porc... mi sa che sono proprio fuori strada.... Weeps
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 07 Dic 2006 17:49    Oggetto: Rispondi citando

Taifu ha scritto:
Come puo` una domanda dire che l'interlocutore non e` il casuale visto che quest'ultimo puo` anche rispondere sempre (anche se per caso) come un sincero o un bugiardo? Secondo me il casuale viene individuato per forza solo coniugando le risposte fatte a tutte e tre le persone, non potrebbe essere altrimenti.

Come sempre sono stato impreciso...
C'è una domanda (la numero 3) che, posta due volte, conduce a 2 casi:
1) deduco il significato di DA e MA senza però ricavare un briciolo di informazioni su chi è chi
2) deduco solo che il terzo tizio non è il casuale (più una frazione di informazione spendibile solo dopo la terza e ultima domanda)

Citazione:
Una risposta "dicotomica" al meglio puo` solo togliere meta` delle possibilita`.

Per la precisione, le domande semplici tolgono 1/3 delle possibilità (tranne quelle "sbilanciate" che arrivano a escludere 8 possibilità su 12 in un caso e 0 nell'altro).
La somma dei casi esclusi dalle due possibili risposte è invece sempre costante e pari a 8/24 (cioè ancora 1/3 dei casi possibili).

Ovviamente questa pesatura
1) vale solo se la domanda è posta come prima
2) vale con beneficio di inventario (ovvero solo se non ho commesso errori)
3) è limitata, ripeto, alle domande semplici cioè del tipo "DA vuol dire SI?" o "sei sincero?".

La pesatura delle domande composte ("(DA vuol dire SI) AND (Sei sincero)?") è il prossimo passo (e potrei scoprire che effettivamente ci sono domande che escludono esattamente metà dei casi).
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 08 Dic 2006 12:09    Oggetto: Rispondi citando

Un dubbio amletico mi assale:
il bugiardo è bugiardo solo con gli altri o anche con sè stesso?

Ovvero.

Se ho due domande A e B e pongo la domanda A OR B, il bugiardo come calcola la risposta?
Prima risponde sinceramente ad A e a B, compone con l'OR le risposte sincere e poi nega la risposta prima di fornirmela:
A OR B = NOT(A OR B)

oppure risponde mentendo ad A e a B, compone l'OR con le risposte insincere e poi nega nuovamente la risposta?
A OR B = NOT[NOT(A) OR NOT(B)]

?

E' NOTo che il dubbio di Amleto fosse OR B OR NOT (OR B)
Top
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


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

MessaggioInviato: 08 Dic 2006 14:53    Oggetto: Rispondi citando

ulisse ha scritto:

Una quindicina di parole?!? Shocked
La domanda più lunga e contorta che sono riuscito a immaginare ne conta solo 10! Porc... mi sa che sono proprio fuori strada.... Weeps


Le ho contate meglio (sono riuscito a contare le parole senza "leggerle"): sono 25 parole esatte (articoli e congiunzioni comprese).

ulisse ha scritto:

Se ho due domande A e B e pongo la domanda A OR B, il bugiardo come calcola la risposta?
Prima risponde sinceramente ad A e a B, compone con l'OR le risposte sincere e poi nega la risposta prima di fornirmela:
A OR B = NOT(A OR B)

oppure risponde mentendo ad A e a B, compone l'OR con le risposte insincere e poi nega nuovamente la risposta?
A OR B = NOT[NOT(A) OR NOT(B)]?



Ho verificato anche questo, la risposta giusta e` la prima:
NOT (A OR B)

L'oracolo bugiardo risponde sinceramente a tutte le sotto-domande, calcola la risposta sincera finale e infine la inverte.
Top
Profilo Invia messaggio privato
Taifu
Semidio
Semidio


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

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

Una considerazione interessante (non mi illudo: e` chiaramente derivata da qualche parola che mi e` rimasta nell'inconscio mentre leggevo parte dell'articolo).

Se facciamo la domanda al primo indigeno A possiamo interrogare il casuale, oppure interrogare il sincero o il bugiardo. Se con questa prima domanda ad A cerchiamo di individuare chi non e` il casuale tra B e C possiamo ottenere con certezza questa risposta.

Infatti se interroghiamo il casuale siamo certi che sia B che C non lo siano. Se invece interroghiamo il sincero o il bugiardo possiamo formulare la domanda in modo da avere sempre una risposta indicativa (ricordiamo che il bugiardo risponde: NOT (A OR B).

In ogni caso dobbiamo essere in grado di capire chi tra B e C non e` il casuale.

A questo punto abbiamo due domande che possiamo porre a un indigeno sicuramente non casuale per risolvere il problema. Ma ci bastano? Se si`, quali sono? E qual'e` la prima domanda?
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 08 Dic 2006 20:12    Oggetto: Rispondi citando

Taifu ha scritto:
Se facciamo la domanda al primo indigeno A possiamo interrogare il casuale, oppure interrogare il sincero o il bugiardo. Se con questa prima domanda ad A cerchiamo di individuare chi non e` il casuale tra B e C possiamo ottenere con certezza questa risposta.

Infatti se interroghiamo il casuale siamo certi che sia B che C non lo siano. Se invece interroghiamo il sincero o il bugiardo possiamo formulare la domanda in modo da avere sempre una risposta indicativa (ricordiamo che il bugiardo risponde: NOT (A OR B).

Già. Ma come fai a sapere chi stai interrogando?
Se è la prima domanda che poni non sai nulla del trio e quindi non sai nemmeno a che razza appartenga l'interrogato. O sbaglio qualcosa io?
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 08 Dic 2006 20:37    Oggetto: Rispondi citando

Mi sa che sarà necessaria una stretta collaborazione per arrivare al risultato. Ciò implica l'uso di una convenzione comune su lettere, simboli e modello rappresentativo.
Propongo la seguente convenzione.

I tre tizi sono x,y,z.
Le razze di appartenenza sono s,b,c.
x=s significa ovviamente che il signor x è sincero
x<>s significa che il signor x non è sincero

SI e NO sono codificati con 0 e 1 e vige il principio del terzo escluso.

Per la classificazione dei tipi di domande proporrei quella indicata nel mio ultimo aggiornamento.
Per la rappresentazione manterrei quella matriciale 3x2 per le domande dirette e 3x6 per quelle indirette e quelle del 2° ordine.
Le matrici 3x6 sono solo una visualizzazione in forma compatta delle 3 matrici 3x2. Nei calcoli si usano solo matrici 3x2.

Il nostro sistema è rappresentato da 4 variabili (x,y,z,1) e gli stati che il sistema può assumere sono 12.

Per rappresentare le informazioni a noi note sul sistema usiamo una stringa binaria di lunghezza 12.
Ad esempio 111111111111 indica che tutti e 12 gli stati sono possibili.
Questa è la stringa associata al sistema prima di aver posto domande ovvero all'inizio quando ancora tutto è possibile.

Dopo una domanda sensata qualche stato potrà essere escluso per cui la stringa degli stati possibili comincerà a contenere degli zeri.
Ad esempio 111100001111 ci dirà che, in conseguenza delle informazioni acquisite, ci sono quattro stati che non sono più possibili.
Gli stati ancora possibili sono quelli corrispondenti ai bit posti a 1 quelli esclusi corrispondono agli 0.

Ecco la decodifica dei 12 stati rispetto alla posizione del bit nella stringa:

Poiché ad ogni domanda è possibile rispondere in due modi, ad ogni matrice di risposta sono associate 2 stringhe che rappresentano gli stati (possibili) residui dopo aver posto la domanda.

Se prima di una domanda gli stati possibili sono dati dalla stringa A e la stringa associata alla domanda è B, gli stati possibili dopo la domanda sono dati semplicemente da A AND B.

Esempio:
All'inizio lo stato è A=111111111111.
Supponiamo di aver deciso di usare la domanda 1) come prima domanda. La poniamo al signor x che risponde 0.
A questo fatto è associata la stringa di stato 110011001111.

Lo stato del sistema dopo la prima domanda sarà quindi:
(111111111111) AND (110011001111) = (110011001111)

Se ora, come seconda domanda, poniamo la domanda 1) al signor y che mi risponde 0 [ad essa è associata la stringa (110101110101)] lo stato del sistema dopo le due domande risulterà essere:
(110011001111) AND (110101110101) = (110001000101)

Dopo tre domande avremo individuato la soluzione se la nostra stringa conterrà un solo bit pari a 1.

In questo modo il calcolatore è in grado di fare i conti per noi.

Partendo dalle 4 domande del 1° ordine, semplici e dirette già classificate ho innanzi tutto creato tutte le possibili domande composte con AND, OR e XOR.
Ne esce una nuova domanda che è proprio la quinta domanda semplice che avevo escluso per vincoli strutturali (il vincolo è aggirato dalle domande composte)

5 domande
3 interrrogati
2 risposte
Totale 30 stringhe di stato.

Ponendo 3 domande si ottengono 27000 stringhe di stato alla fine delle domande.
Di queste stringhe circa 1300 contengono un solo 1. Le altre si riferiscono a sequenze di domande che non risolvono il problema e devono essere escluse.
Non basta.
Una domanda fa parte della soluzione se risolve il problema indipendentemente dalla risposta data dall'interrogato.
Quindi dalle 1300 circa stringhe rimaste devo escludere tutte le stringhe "disaccoppiate".
Se ad esempio ho una terna di domande che risolve il problema in caso l'interrogato risponda 1 alla terza domanda (troverò nell'elenco tale domanda) ma non lo risolve se l'interrogato risponde 0, quella terna non è la soluzione e la stringa corrispondente andrà cancellata dall'elenco.

Il problema è che "stringi stringi" (per citare Mad) nessuna delle 27000 stringhe porta alla soluzione! Grrr

Proverò ad aggiungere anche le domande indirette e quelle del 2° ordine.
Aggiunta indispensabile visto che solo quelle contano più di venti parole...

Ma a occhio e croce le domande triplicano e le stringhe da analizzare diventeranno più di 800000 !!! Hypno
Excel non ce la farà e mi toccherà scrivere del codice...
Top
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


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

MessaggioInviato: 09 Dic 2006 00:00    Oggetto: Attenzione! Correzione! Rispondi citando

Stasera ho voluto rileggere di nuovo e con estrema calma l'enunciato del problema.
E` "quasi" tutto giusto quello che ho scritto nel mio primo messaggo... si`, ho detto "quasi"...

Ci sono tre tizi X, Y e Z, che appartengono a tre razze S, B e C e che rispondono DA e MA invece che SI` e NO (ovviamente non sappiamo quale significa SI` e quale NO).
Noi abbiamo tre domande da porre loro per capire la loro appartenenza a ciascuna razza.
Non ci sono limitazioni riguardo a chi porre le domande.

Punto, non c'e` altro. E` quindi evidente che, per quanto strano, non dobbiamo capire il significato di DA e MA. Questa quesito l'ha aggiunto la mia memoria perche` probabilmente mi sembrava assurdo poter capire le risposte se non si sa cosa vuol dire DA e MA.

Ma non e` cosi`.

P.S. Ulisse, tu puoi modificare il messaggio iniziale aggiungendo questa postilla? Non vorrei che qualche altro disgraziato fosse tratto in inganno dalla mia demenza senile.
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 09 Dic 2006 00:54    Oggetto: Rispondi citando

Incupito Damn! KO Furibondo TapTap
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: 09 Dic 2006 01:12    Oggetto: Rispondi citando

ulisse ha scritto:
Incupito Damn! KO Furibondo TapTap

Su, su Ulisse, non fare così, dai, non l'ha fatto apposta.
Dopotutto anche se non è richiesto magari si deve accertare lo stesso il significato di DA e MA per trovare le altre risposte.

Comunque se vuoi una mano....TapTap
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 09 Dic 2006 02:07    Oggetto: Rispondi citando

Paradossalmente la richiesta di un minor numero di informazioni non semplifica il problema.
Se per individuare le razze è necessario interpretare DA e MA allora il problema è identico a prima.
Se, invece, l'interpretazione non serve allora mi viene da dire che, non sapendo distinguere tra DA e MA, quello che posso rilevare con le 3 domande sono le 2 variazioni nelle risposte.
Top
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


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

MessaggioInviato: 09 Dic 2006 02:49    Oggetto: Rispondi

ulisse ha scritto:
Paradossalmente la richiesta di un minor numero di informazioni non semplifica il problema.
Se per individuare le razze è necessario interpretare DA e MA allora il problema è identico a prima.
Se, invece, l'interpretazione non serve allora mi viene da dire che, non sapendo distinguere tra DA e MA, quello che posso rilevare con le 3 domande sono le 2 variazioni nelle risposte.


L'unico modo per saperlo con certezza sarebbe andare a leggere la soluzione. Se volete lo faccio... Sad

Comunque una domanda con risposta si` e no puo` dare solo un bit di informazione e quindi tre domande possono discernere solo tra 8 casi distinti. Di conseguenza, date le 12 possibilita` che abbiamo se dovessimo interpretare anche DA e MA e` certo che, perche` il gioco sia risolvibile, non si debba individuare DA e MA.

A questo non dovevamo arrivarci da soli prima?
Top
Profilo Invia messaggio privato
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 3 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