#79 cavalieri, furfanti e normali

L’anno nuovo è appena cominciato, e torna il tradizionale appuntamento* con i wellen-enigmi. Avevo parlato qui di Raymond Smullyan e dei suoi indovinelli di logica che hanno per protagonisti cavalieri e furfanti. Una variante di questo problema riguarda tre tipi di persone: cavalieri, che dicono sempre la verità; furfanti, che mentono sempre; e persone normali, che talvolta mentono e talvolta dicono la verità. Inoltre, in questa particolare isola, i furfanti sono detti di rango inferiore, i normali di rango medio e i cavalieri di rango superiore.

*Se c’è un appuntamento, è tradizionale. (Per analoghe frasi fatte, vedi qui).

Le soluzioni sono in fondo al post, dopo la prossima vignetta della Settimana Enigmistica.
Le soluzioni sono in fondo al post, dopo la prossima vignetta della Settimana Enigmistica.

1 Ci sono tre persone, A, B, C, una delle quali è un cavaliere, una un furfante, e una un normale (ma non necessariamente in questo ordine).
A dice: «Io sono un normale.»
B: «È vero.»
C: «Io non sono un normale.»
Cosa sono A, B e C?

2 Due persone, A e B, ognuna delle quali è o un cavaliere, o un furfante o un normale, fanno le seguenti affermazioni:
A: «Io sono di rango inferiore a B.»
B: «Non è vero!»
Si può determinare il rango di A e di B? Si può determinare se queste affermazioni sono vere o false?

3 Ci sono tre persone, A, B, C, una delle quali è un cavaliere, una un furfante, e una un normale.
A: «B è di rango superiore a C.»
B: «C è di rango superiore ad A.»
Quindi viene chiesto a C: «Chi è di rango più alto, A o B?»
Cosa risponde C?

L’isola di Bahava
Sull’isola di Bahava anche le donne sono cavalieri, furfanti e normali. Per la legge, un cavaliere può sposare soltanto un furfante e un furfante può sposare soltanto un cavaliere. Un normale può sposare soltanto un normale. In tal modo qualsiasi coppia sposata sarà composta o da due normali, oppure da un cavaliere e da un furfante.

4 Il signor e la signora A sono una coppia sposata. Fanno le seguenti affermazioni:
Sig. A: «Mia moglie non è un normale.»
Sig.ra A: «Mio marito non è un normale.»
Cosa sono il signor e la signora A?

5 Se invece avessero detto:
Sig. A: «Mia moglie è un normale.»
Sig.ra A: «Mio marito è un normale.»
La soluzione sarebbe diversa?

6 Ci sono due coppie sposate: il Sig. e la Sig.ra A, e il Sig. e la Sig.ra B. Tre di loro fanno le seguenti dichiarazioni:
Sig. A: «Il Sig. B è un cavaliere.»
Sig.ra A: «Mio marito ha ragione; il Sig. B è un cavaliere.»
Sig.ra B: «È vero. Mio marito è proprio un cavaliere.»
Cosa sono le quattro persone intervistate, e quali delle tre affermazioni sono vere?
IMG_3465

Soluzioni

1 A = furfante
B = normale
C = cavaliere
Spiegazione: Le affermazioni di A e B non si contraddicono: devono essere entrambe vere o entrambe false, di conseguenza A e B non possono essere un cavaliere e un furfante: uno di loro dev’essere un normale. Se A è normale, B dice la verità, dunque è un cavaliere. Rimane un furfante: dovrebbe essere C, ma allora la sua affermazione è vera, e i furfanti non possono dire la verità.
Dunque B deve essere il normale. Siccome nel gruppo c’è solo un normale, C sta dicendo la verità: è un cavaliere. Rimane A, che è un furfante, e infatti sta mentendo quando afferma di essere normale.

2 L’unica soluzione possibile è che A e B siano entrambi normali. L’affermazione di A è falsa, e quella di B è vera.
Spiegazione: A non può essere un cavaliere, perché i cavalieri rappresentano il rango più alto, e mentirebbe affermando di essere di un rango inferiore.
Se A è un furfante, deve mentire: l’unico modo in cui la sua affermazione possa risultare falsa, è che anche B sia un furfante, ma in questo caso l’affermazione di B risulterebbe vera, allora non potrebbe essere un furfante. (Comunque, le due affermazioni di A e B si contraddicono: non possono essere entrambe false, dunque A e B non possono essere entrambi furfanti).
A deve essere un normale: se la sua affermazione fosse vera, B sarebbe un cavaliere: ma starebbe negando la verità, e non è possibile. L’affermazione di A dev’essere falsa: in realtà A deve essere di rango superiore o uguale a B. Se l’affermazione di A è falsa, quando B dice che non è vera, B sta dicendo la verità. (Okay, è complicato, ma una negazione del falso è una verità. Esempio più semplice: A, mentendo, afferma: «2+2=5». B risponde: «Non è vero!». È evidente che B ha contraddetto un’affermazione falsa, dunque ha detto la verità). Dunque, l’affermazione di B è vera. Allora B non può essere un furfante. Abbiamo già spiegato che B non può essere un cavaliere, dunque B può essere solo un normale, e la sua affermazione è vera (è vero che “«A è di rango inferiore a B» è falso”: A e B sono entrambi normali, nessuno è di rango superiore all’altro).

3 C risponde che B è di rango superiore ad A.
Ci sono due scenari possibili:
A = cavaliere
B = normale (sta mentendo)
C = furfante
Oppure:
A = furfante
B = normale (dice la verità)
C = cavaliere
In ogni caso, B è un normale. C, indipendentemente dal fatto che sia cavaliere o furfante, risponde che B è di rango superiore ad A.
Spiegazione: Prima di tutto, consideriamo le possibilità che riguardano A e dimostriamo che C non può essere un normale: Se A è un cavaliere, B è davvero di rango superiore a C, dunque B è un normale e C è un furfante. Se invece A è un furfante, in realtà B è di rango inferiore a C, dunque B è normale e C è un cavaliere. Se A è un normale, sia che dica la verità sia che menta, ne segue che C non è un normale (perché c’è solo un normale tra i tre personaggi). In ogni caso, C non è un normale. Se B è un cavaliere, C è davvero di rango superiore ad A, dunque C è un normale e A un furfante – ma abbiamo appena dimostrato che C non può essere un normale, inoltre in questo scenario A è un furfante, dunque la sua affermazione dovrebbe necessariamente essere falsa, e invece si rivela vera perché B (cavaliere) è davvero di rango superiore a C (normale). Se invece B è un furfante, C è in realtà di rango inferiore ad A, dunque C è un normale e A è un cavaliere – di nuovo, C non può essere un normale, inoltre l’affermazione di A dovrebbe essere vera e invece risulta falsa perché B (furfante) non è di rango superiore a C (normale). L’unica possibilità rimasta è che B sia un normale: dunque la sua affermazione potrebbe essere o vera o falsa. Intanto sappiamo che né A né C sono normali: uno di loro è un cavaliere e l’altro è un furfante. Se A è un cavaliere, C è un furfante: risponderebbe alla domanda («Chi è di rango più alto, A o B?») mentendo, dunque direbbe B. Se A è un furfante, C è un cavaliere e darebbe una risposta sincera alla domanda, dicendo B.

4 Il signor e la signora A sono entrambi normali (e hanno mentito entrambi).
Spiegazione: La regola è che qualsiasi coppia sposata è composta o da due normali, oppure da un cavaliere e da un furfante. Se il signore A e la signora A fossero un cavaliere e un furfante, entrambe queste loro affermazioni risulterebbero vere: non è possibile che un furfante dica la verità. L’alternativa è che siano entrambi normali.

5 No, la soluzione sarebbe la stessa: il signor e la signora A sono entrambi normali (ma questa volta hanno detto la verità entrambi).
Spiegazione: Anche questa volta non è possibile che il signore A e la signora A siano una coppia cavaliere-furfante perché, in quel caso, entrambe le affermazioni risulterebbero false, e i cavalieri non possono mentire.

6 Tutti e quattro sono normali, e tutte le affermazioni sono false.
Spiegazione: Il signore A e la signora A affermano entrambi che il signor B è un cavaliere: due affermazioni non contraddittorie non possono essere una vera e una falsa, dunque il signore A e la signora A non possono essere cavaliere e furfante: devono essere due normali. Se dicono la verità, il signor B è davvero un cavaliere: in questo caso sua moglie dovrebbe essere un furfante, ma starebbe dicendo la verità, e non è possibile. Allora il signor B non è un cavaliere, e la signora B sta mentendo: se mente, potrebbe essere un furfante, ma allora il marito dovrebbe essere davvero un cavaliere, e allora non starebbe mentendo. Dunque anche la signora B è normale, e anche suo marito. E tutte e tre le affermazioni sono false.

La fonte degli enigmi (scaricabile, ad esempio, qui): Raymond Smullyan - Qual e il titolo di questo libro

Annunci

#76 raymond smullyan, cavalieri e furfanti

Dopo il grande successo (?) dell’enigma dei tre interruttori e l’enigma dei prigionieri nella sabbia, continuo con i wellen-enigmi, e vi presento Raymond Smullyan:

Raymond Smullyan
Raymond Smullyan

Raymond Smullyan è un matematico, logico, pianista, filosofo taoista e prestigiatore statunitense.
Nato a New York nel 1919, iniziò a suonare il pianoforte a tre anni. Presto sua madre si accorse che il figlio aveva l’orecchio assoluto. Anni dopo, fu costretto ad abbandonare lo strumento a causa di una grave tendinite al braccio destro: “ciò però gli permise di approfondire i suoi studi di matematica”. Mentre faceva il college, “si sostentava economicamente grazie alla sua attività di prestigiatore”.

Ha scritto cose molto importanti sul teorema d’incompletezza di Gödel, ed è autore di molti libri di matematica e logica ricreativa, il più noto dei quali si intitola Qual è il titolo di questo libro?.

tumblr_m2q8o4AOby1r235t4o1_400

Cavalieri e furfanti

Una tipologia celebre di indovinelli logici di Raymond Smullyan ha come ambientazione un’isola immaginaria in cui tutti gli abitanti sono o cavalieri (Knights), che dicono sempre la verità, o furfanti (Knaves), che mentono sempre. Gli enigmi contengono un visitatore che incontra piccoli gruppi di abitanti, e deve dedurre dalle loro affermazioni se si tratta di cavalieri o furfanti (cioè di che “tipo” sono), oppure deve dedurre altri fatti o formulare domande per scoprire determinate informazioni.

Un primo esempio di questo tipo di indovinelli coinvolge tre abitanti: A, B e C. Il visitatore chiede ad A di che tipo sia, ma A borbotta qualcosa che il visitatore non riesce a capire.
B allora dice: «A ha detto di essere un furfante».
Il terzo uomo, C, dice: «Non credere a B: sta mentendo!»
Che cosa sono A, B e C?

Una tristissima vignetta della Settimana Enigmistica al solo scopo di guadagnare tempo prima della soluzione.
Una tristissima vignetta della Settimana Enigmistica al solo scopo di guadagnare tempo prima della soluzione.

Soluzione


Per arrivare alla soluzione, si può considerare prima di tutto che nessun abitante dell’isola può affermare di essere un furfante (se fosse un furfante, mentirebbe e non ammetterebbe mai di esserlo; se invece fosse un cavaliere non potrebbe mai mentire affermando di essere un furfante). Quindi A non può avere detto di essere un furfante: l’affermazione di B è falsa, di conseguenza B è un furfante, mentre C ha detto la verità e allora C è un cavaliere. A ha sicuramente detto di essere un cavaliere, ma in questo caso ci è impossibile stabilire se dicesse la verità o no.
(Questa cosa ricorda molto il paradosso del mentitore, di cui avevo parlato qui.)
È utile tenere presente anche che due affermazioni contraddittorie non possono essere entrambe vere, né entrambe false.

Di seguito cinque esempi di questo tipo di indovinelli: in ogni enigma ci sono due o tre persone, ognuna delle quali può essere o un cavaliere o un furfante.
Metto le soluzioni in fondo al post (sono molto schematiche: se volete ulteriori spiegazioni, o vi sembrano sbagliate, o volete dare inizio a un vivace dibattito, scrivete pure un commento qui sotto oppure una mail a wellentheorie chiocciola gmail punto com).

1
Ci sono due persone, A e B.
A dice: «Almeno uno di noi è un furfante».
Cosa sono A e B?

2
Ci sono tre persone, A, B, C.
A e B fanno le seguenti affermazioni:
A: «Siamo tutti furfanti».
B: «Solo uno di noi è un cavaliere».
Cosa sono A, B e C?

3
Ci sono tre persone, A, B, C.
A: «B è un furfante».
B: «A e C sono dello stesso tipo».
Cos’è C?

4
Ancora tre persone, A, B e C.
A dice: «B e C sono dello stesso tipo».
Qualcuno allora chiede a C: «A e B sono dello stesso tipo?»
Cosa risponde C?

5
Visitiate l’isola dei cavalieri e dei furfanti. Vi imbattete in due abitanti.
Voi chiedete a uno di essi se l’altro è un cavaliere e ricevete come risposta un sì o un no.
Poi chiedete al secondo se il primo è un cavaliere e di nuovo ottenete come risposta un sì o un no.
Le due risposte sono necessariamente uguali?

IMG_3472

Soluzioni

1
A = cavaliere
B = furfante

2
A = furfante
B = cavaliere
C = furfante

3
C è un furfante.
Riguardo A e B, le possibilità sono due: A è un cavaliere e B è un furfante, oppure viceversa A è un furfante e B è un cavaliere. È impossibile stabilire quale delle due affermazioni sia vera e quale falsa. In ogni caso, C è un furfante.

4
C risponde sicuramente “sì”.
Riguardo a quale “tipo” appartengano A, B e C, ci sono quattro possibilità:

A = cavaliere
B = cavaliere
C = cavaliere

A = cavaliere
B = furfante
C = furfante

A = furfante
B = cavaliere
C = furfante

A = furfante
B = furfante
C = cavaliere

5
Sì, le due risposte saranno uguali.
Se i due abitanti sono entrambi cavalieri, o se sono entrambi furfanti, risponderanno entrambi “sì”.
Se il primo è un cavaliere e il secondo è un furfante, o viceversa il primo è un furfante e il secondo è un cavaliere, risponderanno entrambi “no”.

#74 l’enigma dei tre interruttori e l’enigma dei prigionieri nella sabbia

Oggi vi propongo del divertimento sfrenato per il vostro sabato sera: due appassionanti indovinelli di logica. For real party people only.

incandescentbulb

L’enigma della lampadina e dei tre interruttori

In una prima stanza, c’è una normale lampadina. Nella seconda stanza, ci sono tre interruttori. Solo uno dei tre interruttori accende la lampadina.
La prima stanza non è assolutamente visibile dalla seconda stanza (niente spiraglio di luce sotto la porta o cose simili).

Puoi azionare i tre interruttori a tuo piacimento, ma puoi andare nella prima stanza soltanto una volta per verificare lo stato della lampadina. Come puoi individuare l’interruttore in grado di accenderla?

Le condizioni iniziali sono:
• lampadina spenta
• tutti gli interruttori in posizione off.

Soluzione:

Per prima cosa, possiamo mettere due interruttori su on, lasciando il terzo su off. Ora, se la lampadina fosse ancora spenta, sapremmo subito che l’interruttore giusto è il terzo. Se invece fosse accesa, potremmo escludere il terzo interruttore, ma non potremmo distinguere tra i primi due.
La soluzione consiste nell’accendere due interruttori (diciamo i numeri 1 e 2), attendere qualche minuto e poi spegnere uno dei due (diciamo il numero 2). Ora possiamo andare a controllare la lampadina.
Se l’interruttore giusto fosse il numero 2, come potremmo determinare che la lampadina, ora spenta, prima è stata accesa? Risposta: le lampadine accese si scaldano.

Quindi:
• la lampadina è accesa: l’interruttore giusto è il numero 1 (l’unico interruttore che è rimasto acceso).
• la lampadina è spenta, ma calda: l’interruttore giusto è il numero 2 (l’interruttore che è stato acceso e poi spento).
• la lampadina è spenta e fredda: l’interruttore giusto è il numero 3 (l’unico interruttore che è sempre rimasto spento).

Una vignetta che non c'entra niente ma è simpatica.
Una vignetta che non c’entra niente ma è simpatica.

L’enigma dei prigionieri nella sabbia

Quattro uomini sono stati catturati e sepolti nella sabbia fino al mento, in modo che sporga solo la testa. Sono disposti in fila, uno davanti all’altro, e il quarto è separato rispetto agli altri da un muro. Non possono muoversi, né voltarsi per vedere alle proprie spalle: possono guardare solo dritto davanti a sé. Come nel disegno qui sotto, sono tutti girati in direzione della freccia: quindi il prigioniero A vede B e C, B vede C, C vede solo il muro e D non vede nessuno.
Inoltre, comunicare tra loro è proibito.

Il carceriere mette un cappello sulla testa di ciascun prigioniero e spiega: “Ognuno di voi quattro indossa un cappello. Due di essi sono bianchi, due sono neri.
Se uno di voi sa dirmi qual è il colore del proprio cappello, verrete tutti liberati. Se chi parla dà la risposta sbagliata, verrete tutti giustiziati.”

La domanda è: quale dei prigionieri può trovare la risposta giusta, e perché?

prigionieri

Ulteriori chiarimenti e indizi:

• Ovviamente i prigionieri non sono in grado di vedere il proprio cappello, e non hanno visto i cappelli mentre il carceriere glieli metteva in testa. Inoltre non possono vedere oltre il muro.
• I prigionieri non possono parlare tra loro, non possono dire né chiedere niente al carceriere. È concesso aprire bocca soltanto per dare la risposta.
• Bisogna assumere che i prigionieri siano persone razionali, di normale intelligenza, lucidi, e privi di istinti suicidi.
• Siccome la risposta sbagliata condurrebbe alla morte tutti e quattro, nessun prigioniero parla se non è sicuro al 100% che la risposta sia giusta.
• Esiste un modo, per uno dei prigionieri, di determinare con certezza quale sia il colore del proprio cappello.

Soluzione:

Il prigioniero A può vedere due cappelli davanti a sé: uno nero e uno bianco. Di conseguenza A non può determinare il proprio colore, perché ha il 50% di probabilità di avere il restante cappello nero e 50 di avere quello bianco (in questo senso, si trova nella stessa condizione di C e D).
Il prigioniero B sa che A, alle proprie spalle, può vedere i cappelli B e C. Sa che A potrebbe facilmente dedurre il colore del proprio cappello, per esclusione, se vedesse davanti a sé due cappelli dello stesso colore. Ma se A non dice niente, significa che non conosce la risposta perché vede due cappelli di colore diverso. Dal silenzio di A, B può dedurre che il colore del proprio cappello è l’opposto di quello di C.

Il prigioniero oltre il muro è in realtà irrilevante per la risoluzione del problema: il suo unico scopo è indossare il quarto cappello.

In un’altra versione dell’enigma, non vengono mostrati i colori dei cappelli, e la domanda è: indipendentemente da come il carceriere ha disposto i capelli, in che modo i prigionieri possono trovare la soluzione giusta e quindi essere liberi? La risposta è semplicemente che il prigioniero A può capire il proprio colore se vede due cappelli uguali davanti a sé; in caso contrario A rimane in silenzio e di conseguenza B può capire che il suo colore è diverso da quello di C.

Questo enigma ha una pagina nella Wikipedia inglese in cui vengono illustrate anche diverse varianti.

Siete riusciti a risolverli? Conoscete altri appassionanti indovinelli di logica? Odiate gli indovinelli di logica? Fatemi sapere.