Indovinello: Onesto, Bugiardo, Xor

[Studente Anonimo]

Vi propongo questo indovinello che è una variante dell'indovinello pubblicato da George Boolos sugli oracoli divini.
Questo indovinello che mi avevano proposto (e di cui possiedo la soluzione) secondo me è molto bello.

Tre oracoli A, B e C corrispondono in un qualche ordine ad Onesto, Bugiardo e Xor.
Onesto dice sempre il vero, Bugiardo dice sempre il falso mentre Xor "fa lo XOR" delle risposte di Onesto e di Bugiardo se la domanda posta a Xor fosse stata posta a loro.
L'obbiettivo è determinare le identità di A, B e C (ovvero determinare chi dei tre è Onesto, chi Bugiardo e chi Xor) ponendo loro un massimo di tre domande a cui è possibile rispondere con un "sì" oppure con un "no".
Ogni domanda dev'essere posta ad uno solo degli oracoli.
Può essere che a qualche oracolo venga posta più di una domanda o che non ne vengano poste affatto. Gli oracoli comprendono l'italiano ma parlano una loro lingua strana che solo loro comprendono. Dunque a priori non si conoscono le parole utilizzate da loro per dire "no" e per dire "sì". Le parole sono comunque comprensibili perché formate dalle lettere dell'alfabeto.

Esempio su come "funziona" Xor.
Se ponessimo a Xor la domanda D: "Il numero 1 è un numero pari?", Xor ci risponderebbe: "Sì" (nella propria lingua ovviamente)
Infatti:
- se la domanda fosse stata posta a Onesto egli avrebbe risposto "No" (nella sua lingua) dicendo il vero

- se la domanda fosse stata posta a Bugiardo egli avrebbe risposto "Sì" (nella sua lingua) mentendo.

Siccome le risposte di Onesto e Bugiardo sono diverse allora Xor risponde "Sì".
Se le risposte di Onesto e Bugiardo fossero state uguali allora Xor ci avrebbe risposto: "No"

[axpgn]

Non è vero! Occorrono anche tre risposte

[Drazen77]

Se siamo tutti d'accordo...
sarebbe ora della soluzione.
Contrari?

[veciorik]

La negazione del Bugiardo e la disgiunzione esclusiva di Xor sono applicati/valutati dagli oracoli prima o dopo degli eventuali connettivi logici (AND OR XOR ...) presenti nelle domande composte ?
IMHO dopo, ma mi resta un dubbio.

[Studente Anonimo]

"veciorik":La negazione del Bugiardo e la disgiunzione esclusiva di Xor sono applicati/valutati dagli oracoli prima o dopo degli eventuali connettivi logici (AND OR XOR ...) presenti nelle domande composte ?
IMHO dopo, ma mi resta un dubbio.

Dopo.

"Drazen77":Se siamo tutti d'accordo...
sarebbe ora della soluzione.
Contrari?

La soluzione la pubblicherò fra un paio di giorni.

"axpgn":Non è vero! Occorrono anche tre risposte

Come darti torto...

[gpm63]

Forse ci sono. La mia soluzione, però, prevede una domanda per ogni oracolo.

Prendo in considerazione i possibili casi di attribuzione d'identità. Sono sei:

e per ogni caso le risposte alle tre domande, come dallo schema qui sopra, supponendo 1=sì e 0=no.
Ad ogni caso corrisponde una combinazione di risposte diversa. La prima combinazione (1-0-1) si adatta al primo caso (A=Xor, B=Onesto e C=Bugiardo), la seconda al secondo caso e così via. Quindi ci sono sei possibili soluzioni.
Per dimostrare poi che effettivamente 1 significa "sì" e 0 significa "no" basta prendere in esame la prima combinazione di risposte rovesciando i significati dei simboli ossia 1=no e 0=sì (dimostrazione per assurdo), ne risulta il seguente quadro:

dal quale si ricava che molte risposte (in rosso) non potrebbero essere date dall'oracolo che dovrebbe fornirle,
es. Xor non risponderebbe "no" alla domanda "B è onesto?", dato che le risposte date da Onesto e Bugiardo sarebbero rispettivamente "sì" e "no".

Saluti
Melba

[dan952]

@melba
I casi 001 e 110 non sono distinguibili in quanto non puoi sapere a priori il significato delle parole sì e no. Questa strategia ha sviato sia me che Alex dalla vera soluzione

[gpm63]

@dan95
Hai ragione, questa strategia porta in un vicolo cieco, la strada giusta è un'altra

1a domanda ad A: "Sei tu bugiardo?"
tutti e tre gli oracoli risponderebbero "no", così sappiamo che no significa no (v. mio messaggio del 18 gennaio);
2a domanda sempre ad A: "Sei tu che hai risposto alla mia prima domanda?"
se A risponde "no" A=Bugiardo (gli altri due risponderebbero "sì", Onesto perché dice la verità e Xor perché le risposte di Onesto e Bugiardo a questa domanda sarebbero discordi);
3a domanda a B: "C è Onesto?"
se B risponde "no" B=Onesto, e di conseguenza C=Xor
se B risponde "sì" B=Xor (infatti anche in questo caso le risposte di Bugiardo e Onesto sarebbe discordi) e C=Onesto.
Nel caso che alla seconda domanda A risponda "sì" avremo A=Xor oppure A=Onesto. Con la 3a domanda a B "C è onesto?",
se B risponde "sì" B=Xor, A=Onesto e C=Bugiardo (infatti Onesto non risponderebbe "sì" perché questo implicherebbe che A fosse Bugiardo);
se B risponde "no" B=Onesto, A=Xor e C=Bugiardo.

Saluti
Melba

[gpm63]

Scusate non va neanche così

Anche Bugiardo potrebbe rispondere no alla 3a domanda

Melba

[Drazen77]

La chiudiamo con quattro domande.
Con tre no.

[gpm63]

Sarà così?

Si fa la prima domanda ad A:
"Bugiardo e Onesto danno sempre la stessa risposta?"
Onesto risponderebbe "no", Bugiardo e Xor risponderebbero "sì".
Si fa la seconda domanda sempre ad A:
"Sei tu Onesto?"
Onesto e Bugiardo risponderebbero "sì", Xor risponderebbe "no".
Quindi se le due risposte sono no-sì (nell'ordine) A=Onesto,
se le due risposte sono sì-sì A=Bugiardo,
se le due risposte sono sì-no A=Xor.
Si capisce qui che sì significa sì e no significa no perché la combinazione no-no non si verificherebbe. Infatti solo Onesto risponderebbe no alla prima domanda ma non potrebbe rispondere no alla seconda.
A questo punto se le prime due risposte sono no-sì, si fa la terza domanda ancora ad A (che è Onesto, come si è detto):
"B è Xor?"
Se la risposta è "sì" avremo A=Onesto, B=Xor e C=Bugiardo;
se la risposta è "no" avremo A=Onesto, B=Bugiardo e C=Xor.
Se le prime due risposte sono sì-sì, A=Bugiardo. In questo caso si fa la terza domanda a B:
"A è Xor?"
Se la risposta è "sì" avremo A=Bugiardo, B=Xor e C=Onesto;
se la risposta è "no" avremo A=Bugiardo, B=Onesto e C=Xor.
Se le prime due risposte sono sì-no, A=Xor. In questo caso si fa la terza domanda a B:
"A è Xor?"
se la risposta è "sì" avremo A=Xor, B=Onesto e C=Bugiardo;
se la risposta è "no" avremo A=Xor, B=Bugiardo e C=Onesto.

Melba

[axpgn]

@Melba

Purtroppo il problema è sempre quello, ciò che tu senti è una roba così: grt - prtg. Come fai ad affermare che sia "sì -no" piuttosto che "no-sì" ?

Cordialmente, Alex

[Studente Anonimo]

Ho deciso di pubblicare la soluzione dell'indovinello con 3 domande.

ATTENZIONE SOLUZIONE:

Per risolverlo bisogna definire prima una relazione d'ordine per le parole. In modo che date due parole diverse si possa dire quale delle due sia la più grande e quale la più piccola.
Definiamo una relazione d'ordine $ R $ per le parole.
Per fare ciò definiamo una funzione iniettiva $ f $ che faccia corrispondere ad ogni parola un numero naturale. E in quanto funzione iniettiva, a parole diverse corrispondono numeri diversi.
Siano $ p_1 $ e $ p_2 $ due parole qualunque, diremo che $ p_1 \leq p_2 $ secondo la relazione d'ordine $ R $ se e solo se $ f(p_1) \leq f(p_2) $
La funzione $ f $ è definita in questo modo, sia $ p $ una parola formata dalle lettere $ l_0 l_1 ... l_k $, e sia $ n_i $ il numero naturale di due cifre corrispondente alla posizione della lettera $ l_i $ nell'alfabeto. Abbiamo che $ f(p) = n_0 n_1 ... n_k $
Ovvero quello che andiamo a fare è sostituire ogni lettera $ l_i $ di $ p $ con il numero corrispondete alla posizione di $ l_i $ nell'alfabeto per formare un numero.
Esempio con "casa" e "cane":
A $ \Rightarrow 01 $
C $ \Rightarrow 03 $
E $ \Rightarrow 05 $
N $ \Rightarrow 14 $
S $ \Rightarrow 19 $
$ f(\text{Casa}) = 03011901 $
$ f(\text{Cane}) = 03011405 $
Paragoniamo i due numeri secondo la relazione d'ordine standard. La parola che corrisponde al numero più piccolo è la parola più piccola.
Nel esempio $ 03011405 < 03011901 $ dunque cane $ < $ casa
Oppure ancora come esempio possiamo prendere la parola "BE" e la parola "Z"
B $ \Rightarrow 02 $
E $ \Rightarrow 05 $
Z $ \Rightarrow 25 $
$ 25 < 0205 $ dunque z $ < $ be

$ R $ è una relazione d'ordine, infatti è riflessiva, antisimmetrica e transitiva. Dunque date due parole diverse si può sempre dire quale sia la parola più grande. Inoltre due parole sono "grandi uguali" se e solo se sono la stessa parola, infatti la funzione che fa corrispondere una parola ad un numero è iniettiva.
Siamo dunque certi che le parole utilizzate dagli oracoli per dire "si" e per dire "no", siccome parole diverse, avranno numeri diversi come immagine e pertanto una sarà "più grande" dell'altra.

Poniamo la domanda 1 e la domanda 2 all'oracolo A
Domanda 1
"La parola da voi utilizzata per dire "si" è più piccola - secondo la relazione d'ordine $ R $ - della parola da voi utilizzata per dire "no" ?

Domanda 2
"La parola da voi utilizzata per dire "no" è più piccola - secondo la relazione d'ordine $ R $ - della parola da voi utilizzata per dire "si" ?

Sia $ r_1 $ la risposta che otteniamo alla domanda 1 e sia $ r_2 $ la risposta che otteniamo alla domanda 2.
Compariamo le due risposta che abbiamo ottenuto dall'oracolo A secondo la relazione $ R $
Possiamo trovarci in uno dei seguenti casi.

i) $ r_1 < r_2 $ significa che l'oracolo A è Onesto, $ r_1 $ e $ r_2 $ sono due parole distinte
ii) $ r_2 < r_1 $ significa che l'oracolo A è Bugiardo, $ r_1 $ e $ r_2 $ sono due parole distine
iii) $ r_1 = r_2 $ significa che l'oracolo A è Xor, , $ r_1 $ e $ r_2 $ sono la stessa parola.

Nel caso i) A è Onesto, dunque chiediamo ad A
Se ti chiedessi: "B è Bugiardo ?" Mi risponderesti $ r_1 $?
La risposta $ r_1 $ indica che B è Bugiardo e C è Xor.
La risposta $ r_2 $ indica che C è Bugiardo e B Xor

Nel caso ii) A è Bugiardo, dunque chiediamo ad A
Se ti chiedessi: "B è Onesto?" Mi risponderesti $ r_1 $?
La risposta $ r_1 $ indica che B è Onesto e C è Xor
La risposta $ r_2 $ indica che C è Onesto e B è Xor

Nel caso iii) A è Xor, dunque chiediamo a B
Se ti chiedessi: "C è Onesto?" Mi risponderesti $ r_1 $?
La risposta $ r_1 $ indica che C è Onesto e B è Bugiardo
La risposta $ r_3 $ indica che B è Onesto e C è Bugiardo

Spiegazione
Per semplicità supponiamo che le parole utilizzate dagli oracoli siano "Nir" e "Sir"
Secondo la relazione d'ordine $ R $ abbiamo che NIR $ < $ SIR indipendentemente dal loro significato


Caso 1) Sir = si e Nir = no. Supponiamo dunque che la parola "più grande" significhi "si"
1.1) Facciamo la domanda 1 all'oracolo A
-Onesto risponde NIR (che significa no) ovvero risponde con la parola più piccola secondo la relazione $ R $
-Bugiardo risponde SIR (che significa si) ovvero risponde con la parola più grande secondo la relazione $ R $
-Xor risponde SIR (significa si)

1.2) Facciamo la domanda 2 all'oracolo A
- Onesto risponde SIR (che significa si) ovvero risponde con la parola più grande secondo la relazione.
- Bugiardo risponde NIR (che significa no) ovvero risponde con la parola più piccola secondo la relazione.
Xor risponde SIR (che significa si)

Caso 2) Sir = no, Nir = si. Supponiamo dunque che la parola "più grande" secondo la relazione significhi "no"
2.1) Facciamo la domanda 1 all'oracolo A
- Onesto risponde NIR (che significa si) ovvero risponde con la parola più piccola secondo $ R $
- Bugiardo risponde SIR (che significa no) ovvero risponde con la parola più grande secondo la relazione.
- Xor risponde NIR (che significa si)

2.2) Facciamo la domanda 2 all'oracolo A
- Onesto risponde SIR (che significa no) ovvero risponde con la parola più grande secondo la relazione
- Bugiardo risponde NIR (che significa si) ovvero risponde con la parola più piccola secondo la relazione.
- Xor risponde NIR (che significa si).

[axpgn]

Soluzione interessante e sicuramente bella ed elegante però ... permettimi una considerazione ...
In un "indovinello" usare artifici per arrivare alla soluzione è sicuramente permesso anzi talvolta il bello sta proprio in quello;
devi però ammettere che l'artificio deve avere almeno una minima coerenza con il contesto se non è espressamente citato ...
chiedere se una parola è più lunga di un'altra presuppone che sia ben definito il concetto di "lunghezza" ... ora, perché il giochetto funzioni si dà per implicito che la relazione d'ordine che tu hai ben definito sia condivisa con la controparte: ma come sia ragionevolmente possibile questo con una controparte di cui non conosciamo neppure come dica "sì" o "no"?
Io lo trovo un po' forzato ... IMHO ...

Cordialmente, Alex

[dan952]

Basta essere più specifici nelle domande specificando, appunto, da quale parte viene presa la teoria, formulando una domanda del tipo: "Definendo la relazione così e così, la " lunghezza" così e così"+ecc...

Oppure intendi dire che proprio defininendo la "lunghezza" per loro non sia ben definita e quindi la loro risposta potrebbe essere influenzata anche da questo. Comunque sia la matematica non è un opinione se per noi qualcosa è ben definito lo è per qualsiasi altro essere vivente dotato di un intelligenza paragonabile se non superiore alla nostra.

[axpgn]

@dan95
Usa lo spoiler ...

Non ci siamo capiti: io parlo di comunicazione, non di matematica o fisica. 3m0o ha dato una definizione ben precisa di "lunghezza di una parola" che, tra l'altro, coinvolge anche i numeri: come possiamo noi essere sicuri che si stia parlando della stessa cosa? Perché si possa dire che tre domande sono sufficienti, è necessario che OGNI parola delle domande abbia già A PRIORI un significato chiaro ed univoco sia per noi che per loro; altrimenti non sono tre domande ma di più ... IMHO
Ah, è ovvio (come ho detto) che è sufficiente citare nel testo le condizioni possibili, accettabili, ecc...

[Studente Anonimo]

"axpgn":

Soluzione interessante e sicuramente bella ed elegante però ... permettimi una considerazione ...
In un "indovinello" usare artifici per arrivare alla soluzione è sicuramente permesso anzi talvolta il bello sta proprio in quello;
devi però ammettere che l'artificio deve avere almeno una minima coerenza con il contesto se non è espressamente citato ...
chiedere se una parola è più lunga di un'altra presuppone che sia ben definito il concetto di "lunghezza" ... ora, perché il giochetto funzioni si dà per implicito che la relazione d'ordine che tu hai ben definito sia condivisa con la controparte: ma come sia ragionevolmente possibile questo con una controparte di cui non conosciamo neppure come dica "sì" o "no"?
Io lo trovo un po' forzato ... IMHO ...

Cordialmente, Alex

Premetto che l'indovinello non l'ho inventato io. Io l'ho risolto così, la persona che me lo aveva proposto aveva usato una relazione d'ordine meno "astrusa" della mia e più evidente. Detto questo nel testo è specificato che la lingua degli oracoli utilizza il nostro alfabeto (informazione che permette la risoluzione). Ed è stata proprio quell'informazione che mi aveva permesso di arrivare alla soluzione. Infatti è un'informazione che deve dare un'indizio perché avere una lingua sconosciuta oppure una lingua sconosciuta basata su un alfabeto conosciuto sono due informazioni molto diverse. Perderebbe di senso l'informazione supplementare dell'alfabeto a meno che l'alfabeto stesso non serva per la risoluzione dell'indovinello.

Per quanto riguarda la seconda cosa i componenti della controparte sono degli oracoli e sanno anche cosa stai pensando
O come dice dan95, è sufficiente essere esaustivi nella formulazione della domanda, sebbene questo implichi avere delle domande molto lunghe. Per questo io mi sono limitato a definire prima la relazione R e poi a riferirmi ad essa nella domanda con "R" appunto. Niente ci vieta di sostituire alla "R" presente nella domanda la definizione di relazione d'ordine. La mia è stata un impostazione di domanda per rendere il tutto più chiaro e pulito.

[Studente Anonimo]

Inoltre...

credo che l'ordine alfabetico non sia l'unico modo per risolverlo, non ci ho mai ragionato troppo e magari mi sbaglio ma credo esistano anche altri modi come ad esempio il tempo di pronuncia, o l'altezza del suono prodotto. L'importante è che le risposte siano paragonabili l'una all'altra rispetto al metodo in modo da distinguere i casi Bugiardo e Onesto.

[Drazen77]

Avevo provato 7000 diverse possibili soluzioni, ma a questa non avevo proprio pensato...
La soluzione "meno astrusa" del tuo amico qual è?

[dan952]

Potrebbe essere questa l'alternativa

Domanda 1: "Se numerassi il nostro alfabeto, la prima lettera della vostra parola "sì" occupa una posizione minore della prima lettera del vostro "no"?"

Domanda 2: "Se numerassi il nostro alfabeto, la prima lettera della vostra parola "sì" occupa una posizione maggiore o uguale della prima lettera del vostro "no"?"

Edit: no non va bene

[veciorik]

Riassumo con le mie parole a beneficio di chi ritiene complicata la soluzione esposta. Spero sia utile.
L'indizio chiave era presente nella formulazione dell'indovinello, ma l'avevo sottovalutato:

... le parole utilizzate da loro per dire "no" e per dire "sì" ... sono comunque comprensibili perché ...
formate dalle lettere dell'alfabeto

Basta focalizzare le prime due domande rivolte allo stesso dio

sull'ordine delle parole divine corrispondenti a SI e NO, secondo l'alfabeto umano ben noto anche alle divinità:
[list=1][*:34tpxy0s]è VERO che il "vostro SI" precede il "vostro NO" in ordine alfabetico ?[/*:m:34tpxy0s][*:34tpxy0s]è FALSO che il "vostro SI" precede il "vostro NO" in ordine alfabetico ?[/*:m:34tpxy0s][/list:o:34tpxy0s]

La terza domanda si può ridurre a due casi:

[list=i][*:34tpxy0s]se A è Onesto o Bugiardo, gli si chiede: "B è Xor ?"[/*:m:34tpxy0s][*:34tpxy0s]se A è Xor si chiede a B: "A è Xor ?"[/*:m:34tpxy0s][/list:o:34tpxy0s]