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: 19129
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: 19129
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

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
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 ... 9, 10, 11, 12  Successivo
Pagina 10 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