Ma... dov'è finito il messaggio di Piera, quello su Edipo e la Sfinge?? Era qui da qualche parte, ne sono certo...
Boh, lo riscrivo io:
Edipo deve indovinare un numero che la Sfinge ha pensato, da 1 a 2006. Può porre 15 domande alla Sfinge, che ammettano come risposte solo "Sì" o "No". La Sfinge mente al massimo una volta.
Edipo è in grado di salvarsi? E come?
Ok. Generalizziamo un po'.
La Sfinge chiede di indovinare un numero da 1 a $ 2^n $, con $ d $ domande. Dimostrare che, se $ 2^k $ è la minima potenza di 2 maggiore di $ d $, e
$ n + k \leqslant d $,
allora Edipo può salvarsi.
Descrivere una strategia di salvataggio.
M.
L'enigma della Sfinge
L'enigma della Sfinge
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
Non saprei formalizzarlo e ho anche poco tempo(questi esami 
).
Credo che l'individuazione del numero vada fatta con un metodo dicotomico.
Dato il numero n lo divido per due e continuo così con il risultato di tale divisione(se mi trovo dinanzi ad un numero dispari considero il suo antecedente). Chiedo alla sfinge se il numero pensato è maggiore del quoziente. Così facendo ottero prima o poi una contraddizione(e questa è la bugia) e un restringimento dell'intervallo in cui cade il numero pensato.
Non so se è corretto ma potrebbe funzionare.
).Credo che l'individuazione del numero vada fatta con un metodo dicotomico.
Dato il numero n lo divido per due e continuo così con il risultato di tale divisione(se mi trovo dinanzi ad un numero dispari considero il suo antecedente). Chiedo alla sfinge se il numero pensato è maggiore del quoziente. Così facendo ottero prima o poi una contraddizione(e questa è la bugia) e un restringimento dell'intervallo in cui cade il numero pensato.
Non so se è corretto ma potrebbe funzionare.
Stabiliamo che:
-Domanda Buona= si sa che la sfinge è sincera
-Domanda Cattiva= non si sa se la sfinge è sincera
Per trovare il numero da 1 a 2006 servono 11 domande buone (chiedendo ogni volta se il numero che si cerca è maggiore della metà dei numeri tra cui si è indecisi)
La prima domanda è se la sfinge mente in una domanda dispari: se dice di sì, allora sicuramente non mentirà in una domanda pari (sennò mentirebbe 2 volte), se dice di no allora sicuramente non mentirà in una domanda dispari (in quel caso mentirebbe 2 volte).
Ci sono quindi 7 domande buone. Ne servono altre 4.
Al solito si dividono le domande cattive in 2 gruppi uguali, e si chiede alla sfinge se ha mentito nel gruppo che comprende la domanda che le si sta facendo. Anche in questo caso otteniamo 3 domande buone e 3 cattive. Con lo stesso sistema possiamo determinare un'altra domanda buona, arrivando così alle 11 necessarie.
Generalizzando, da d domande se ne ottengono d-k buone dove k è l'esponente della minore potenza di 2 superiore a d. Cioè si perdono in sostanza le domande in cui le si chiede dove mentirà, e ne bastano esattamente k per avere un quadro preciso.
-Domanda Buona= si sa che la sfinge è sincera
-Domanda Cattiva= non si sa se la sfinge è sincera
Per trovare il numero da 1 a 2006 servono 11 domande buone (chiedendo ogni volta se il numero che si cerca è maggiore della metà dei numeri tra cui si è indecisi)
La prima domanda è se la sfinge mente in una domanda dispari: se dice di sì, allora sicuramente non mentirà in una domanda pari (sennò mentirebbe 2 volte), se dice di no allora sicuramente non mentirà in una domanda dispari (in quel caso mentirebbe 2 volte).
Ci sono quindi 7 domande buone. Ne servono altre 4.
Al solito si dividono le domande cattive in 2 gruppi uguali, e si chiede alla sfinge se ha mentito nel gruppo che comprende la domanda che le si sta facendo. Anche in questo caso otteniamo 3 domande buone e 3 cattive. Con lo stesso sistema possiamo determinare un'altra domanda buona, arrivando così alle 11 necessarie.
Generalizzando, da d domande se ne ottengono d-k buone dove k è l'esponente della minore potenza di 2 superiore a d. Cioè si perdono in sostanza le domande in cui le si chiede dove mentirà, e ne bastano esattamente k per avere un quadro preciso.
"Sei la Barbara della situazione!" (Tap)
Ok. A meno di permutazioni, è sostanzialmente la strategia che avevo in mente anch'io:
Domande 1-7: La i-esima cifra binaria è un 1?
Domanda 8: Hai mentito nelle prime 7 domande?
Se 8:"sì": sicuramente ha mentito in una delle prime 8. A quel punto la Sfinge diventa un Oracolo che dice sempre il vero. Basta con 4 domande chiedere le cifre binarie che mancano. Con le 3 domande restanti si individua con bisezioni successive la menzogna.
Se 8:"no": allora le prime 7 sono buone. Ripeto la strategia:
Domande 9-10-11: la 8a/9a/10a cifra binaria è un 1?
Domanda 12: Hai mentito nelle domande 9-11?
Se 12:"sì": allora la Sfinge ha mentito in una domanda da individuare su 4. Con la risposta 13 indovino l'ultima cifra binaria e con le 14-15 individuo la menzogna.
Se 12:"no": le prime 11 sono buone. Ripeto la strtegia:
Domanda 13: l'ultima cifra binaria è un 1?
Domanda 14: Hai mentito nella domanda 13?
Se 14:"sì", allora devo individuare una menzogna tra le risposte 13 e 14, che risolvo con la risposta 15.
Se 14:"no", allora la 13 è buona e indovino il numero con una risposta d'avanzo. []
Vi lascio scrivere per bene la formalizzazione con d e n generici.
-------------------------------
A questo punto la domanda è: Edipo riesce a fare di meglio? Ossia se n + k > d, allora è possibile che la Sfinge riesca a papparsi Edipo?
Un conteggio naif direbbe: le configurazioni di gioco sono troppe: devo indovinare n cifre binare, e le configurazioni di verità/menzogna sono d+1 (tutte verità, oppure la bugia dislocata in d posizioni possibili). Le configurazioni totali (numero pensato, configurazione v/f) sono
$ 2^n (d+1) \geqslant 2^n \cdot 2^k > 2^d $.
Ma $ 2^d $sono esattamente le possibili configurazioni di risposta, quindi non ho abbastanza risposte per individuare esattamente tutte le configurazioni di gioco. Fine della storia... o no?...
In fin dei conti, Edipo deve solo indovinare il numero, non indovinare la coppia (numero pensato, domanda mentita), che è senz'altro una richiesta più difficile. E' possibile concepire un insieme di domande per cui Edipo riesce ad indovinare il numero, senza tuttavia riuscire ad affermare con certezza quale sia la domanda mentita?
Boh, pensateci...
Domande 1-7: La i-esima cifra binaria è un 1?
Domanda 8: Hai mentito nelle prime 7 domande?
Se 8:"sì": sicuramente ha mentito in una delle prime 8. A quel punto la Sfinge diventa un Oracolo che dice sempre il vero. Basta con 4 domande chiedere le cifre binarie che mancano. Con le 3 domande restanti si individua con bisezioni successive la menzogna.
Se 8:"no": allora le prime 7 sono buone. Ripeto la strategia:
Domande 9-10-11: la 8a/9a/10a cifra binaria è un 1?
Domanda 12: Hai mentito nelle domande 9-11?
Se 12:"sì": allora la Sfinge ha mentito in una domanda da individuare su 4. Con la risposta 13 indovino l'ultima cifra binaria e con le 14-15 individuo la menzogna.
Se 12:"no": le prime 11 sono buone. Ripeto la strtegia:
Domanda 13: l'ultima cifra binaria è un 1?
Domanda 14: Hai mentito nella domanda 13?
Se 14:"sì", allora devo individuare una menzogna tra le risposte 13 e 14, che risolvo con la risposta 15.
Se 14:"no", allora la 13 è buona e indovino il numero con una risposta d'avanzo. []
Vi lascio scrivere per bene la formalizzazione con d e n generici.
-------------------------------
A questo punto la domanda è: Edipo riesce a fare di meglio? Ossia se n + k > d, allora è possibile che la Sfinge riesca a papparsi Edipo?
Un conteggio naif direbbe: le configurazioni di gioco sono troppe: devo indovinare n cifre binare, e le configurazioni di verità/menzogna sono d+1 (tutte verità, oppure la bugia dislocata in d posizioni possibili). Le configurazioni totali (numero pensato, configurazione v/f) sono
$ 2^n (d+1) \geqslant 2^n \cdot 2^k > 2^d $.
Ma $ 2^d $sono esattamente le possibili configurazioni di risposta, quindi non ho abbastanza risposte per individuare esattamente tutte le configurazioni di gioco. Fine della storia... o no?...
In fin dei conti, Edipo deve solo indovinare il numero, non indovinare la coppia (numero pensato, domanda mentita), che è senz'altro una richiesta più difficile. E' possibile concepire un insieme di domande per cui Edipo riesce ad indovinare il numero, senza tuttavia riuscire ad affermare con certezza quale sia la domanda mentita?
Boh, pensateci...
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
Ma se ha individuato il numero e ripensa alle domande, non deduce anche qual era la domanda mentita?Marco ha scritto: In fin dei conti, Edipo deve solo indovinare il numero, non indovinare la coppia (numero pensato, domanda mentita), che è senz'altro una richiesta più difficile. E' possibile concepire un insieme di domande per cui Edipo riesce ad indovinare il numero, senza tuttavia riuscire ad affermare con certezza quale sia la domanda mentita?
Io non credo che si possa fare meglio della tua soluzione.
Tra parentesi, per chi vuole approfondire, prendere una stringa di 11 bit e codificarla in una di 15 in modo tale da risalire a quella di partenza anche se uno dei 15 bit è stato invertito, è quel che si dice un codice di correzione degli errori. Anzi, per essere precisi è un codice perfetto equivalente a un codice di Hamming.
I codici di Hamming sono parametrizzati dai $ k\geq2 $, e il codice $ k $-esimo codifica una stringa di $ m=2^k-k-1 $ bit in una stringa di $ n=2^k-1 $ bit. Questo può sempre essere realizzato (ed è molto conveniente scegliere questa strada) con una opportuna funzione lineare da $ \mathbb Z_2^m $ in $ \mathbb Z_2^n $.
Per chi fosse curioso o interessato, vi è un bellissimo libro (Coding Theory, di Hoffman e altri), che è veramente semplice da leggere, e anche se è pensato per l'università non ha nessun prerequisito. Contiene tutto quello che c'è da sapere sui codici usati fino a pochi anni fa, e ad esempio arriva a spiegare nel dettaglio quelli impiegati per recuperare i dati dei CD nonostante i graffi.
....mmmmhhhh.... quindi, se ho ben capito, il problema generalizzato della sfinge è già stato affrontato e risolto dai codici di Hamming?
Mah, non so se ha senso o meno, ma stavo pensando al "rettangolo delle fasi" di questo gioco. Siamo in un caso in cui le configurazioni sono più di 2^d (che sono i diversi set di risposte ottenibili). Se pongo le domande unicamente in termini di "Dato un certo sottinsieme S di configurazioni possibili, la configurazione finale cade in S?", è sempre possibile dividere a metà lo spazio delle configurazioni che non possiamo escludere in zone sempre più piccole. Ma se riesco a ritagliare le zone S in modo che mi lascino l'incertezza sulla domanda mentita, ma non sul numero pensato.
Quindi, probabilmente, la vera verità è che non è possibile esprimere tutti i sottoinsiemi S per benino a piacimento.... forse è meglio che mi legga il libro di Hoffman....
Mah, non so se ha senso o meno, ma stavo pensando al "rettangolo delle fasi" di questo gioco. Siamo in un caso in cui le configurazioni sono più di 2^d (che sono i diversi set di risposte ottenibili). Se pongo le domande unicamente in termini di "Dato un certo sottinsieme S di configurazioni possibili, la configurazione finale cade in S?", è sempre possibile dividere a metà lo spazio delle configurazioni che non possiamo escludere in zone sempre più piccole. Ma se riesco a ritagliare le zone S in modo che mi lascino l'incertezza sulla domanda mentita, ma non sul numero pensato.
Quindi, probabilmente, la vera verità è che non è possibile esprimere tutti i sottoinsiemi S per benino a piacimento.... forse è meglio che mi legga il libro di Hoffman....
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
Boh, Teppic, senti questa e dimmi se ti convince:
Voglio indovinare una cifra con due domande. [k=2, n=1, d=2; k+n>d]. Le configurazioni sono 6: {0, 1} x {VV, FV, VF}.
Domande:
1. "La cifra è 0?"
2. "Il numero totale di bugie è 1?"
1. sì: (0,VV) (0,VF) (1,FV)
1. no: (1,VV) (1,VF) (0,FV)
2. sì: (?, FV)
2. no: (?, VV) (?, VF)
Quindi:
1.sì/2.sì --> (1,FV)
1.sì/2.no --> (0,VV) oppure (0,VF).
[le risposte 1.no sono simmetriche scambiando 0 con 1.]
Nel caso sì/no, il numero pensato è comunque 0, ma non so se la terza domanda è mentita oppure no.
Ho preso un granchio? Non mi pare...
La domanda che sorge spontanea è: o i codici perfetti sono subottimali, oppure il gioco della Sfinge non equivale esattamente ad una trasmissione con 1 errore. Ma perché mai? Sembrerebbero a tutti gli effetti la stessa identica cosa.
L'unica cosa che mi viene in mente è che questo controesempio contiene in maniera nemmeno troppo velata l'antinomia del Mentitore, avendo reso la risposta 2. autoreferenziale, ma ciononostante sembrerebbe reggere.
Any idea?
Voglio indovinare una cifra con due domande. [k=2, n=1, d=2; k+n>d]. Le configurazioni sono 6: {0, 1} x {VV, FV, VF}.
Domande:
1. "La cifra è 0?"
2. "Il numero totale di bugie è 1?"
1. sì: (0,VV) (0,VF) (1,FV)
1. no: (1,VV) (1,VF) (0,FV)
2. sì: (?, FV)
2. no: (?, VV) (?, VF)
Quindi:
1.sì/2.sì --> (1,FV)
1.sì/2.no --> (0,VV) oppure (0,VF).
[le risposte 1.no sono simmetriche scambiando 0 con 1.]
Nel caso sì/no, il numero pensato è comunque 0, ma non so se la terza domanda è mentita oppure no.
Ho preso un granchio? Non mi pare...
La domanda che sorge spontanea è: o i codici perfetti sono subottimali, oppure il gioco della Sfinge non equivale esattamente ad una trasmissione con 1 errore. Ma perché mai? Sembrerebbero a tutti gli effetti la stessa identica cosa.
L'unica cosa che mi viene in mente è che questo controesempio contiene in maniera nemmeno troppo velata l'antinomia del Mentitore, avendo reso la risposta 2. autoreferenziale, ma ciononostante sembrerebbe reggere.
Any idea?
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
Nonno Bassotto
- Site Admin
- Messaggi: 970
- Iscritto il: 14 mag 2006, 17:51
- Località: Paris
- Contatta:
Beh, non mi sembra che la sfinge equivalga esattamente al problema del codice a correzione d'errore, anche se in effetti sono molto simili.
Nel caso del codice a correzione d'errore si inserisce un po' di informazione ridondante, in modo appunto da correggere un eventuale errore su un bit. E' come se avessimo a disposizione più domande alla sfinge sulla sequenza di bit.
Nel caso della sfinge possiamo fare domande sul momento in cui mente (ovvero sul punto in cui si è verificato l'errore). Questo non è possibile con un codice, per il semplice motivo che la codifica deve incorporare l'informazione ridondante prima che la trsmissione (e quindi l'eventuale corruzione del dato) si verifichi, dunque non può "dare risposte" su quale bit è errato.
Dunque mi sembra che in linea di principio la sfinge sia un po' più efficiente di un codice.
Nel caso del codice a correzione d'errore si inserisce un po' di informazione ridondante, in modo appunto da correggere un eventuale errore su un bit. E' come se avessimo a disposizione più domande alla sfinge sulla sequenza di bit.
Nel caso della sfinge possiamo fare domande sul momento in cui mente (ovvero sul punto in cui si è verificato l'errore). Questo non è possibile con un codice, per il semplice motivo che la codifica deve incorporare l'informazione ridondante prima che la trsmissione (e quindi l'eventuale corruzione del dato) si verifichi, dunque non può "dare risposte" su quale bit è errato.
Dunque mi sembra che in linea di principio la sfinge sia un po' più efficiente di un codice.
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill