Fog Creek Software
Discussion Board




The hardest logic puzzle ever...

A modified version can be found here:
http://philosophy.hku.hk/think/logic/hardest.php

Three gods A , B , and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A , B , and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer in their own language, in which the words for yes and no are “da” and “ja”, in some order. You do not know which word means which.

S.C.
Friday, September 12, 2003

It's a nice puzzle. The more I think about it, the less likely it seems that it's possible. There are 6 possible ways to arrange them, and 2 language possibilities, giving 12 possibilities in all. I don't see how this can ever be encoded in 3 bits of information. I take it you do know the answer? (don't tell me what it is!)

Paul Viney
Friday, October 03, 2003

Okay, I've been thinking it over again, and I've decided that we don't actually need to work out which one of da and ja means yes and which means no, as long as we get consistant answers.


consider the table
answer to question    value of da      answer xor da
true                    true      false = ja
true                  false      true = ja
false                  true        true = da
false                  false      false = da

so by using (statement xor da) we can use an answer of 'ja' as meaning yes, and an answer of 'da' as meaning false (assuming a truthful answer).

To start with, we need to find a person who is definitely not random.
Luckily this has been handled recently in the question about buying computers.
After this we have two questions left to locate the random guy and check the true/false situation.

First I'll put the questions as if they were answering English yes and nos.
First question, put to A:

1) If I asked the first non-random answering god in the sequence C B A whether B was random answering, what would their answer be?

A  B  C  Answer

T  F  R  T
T  R  F  F
F  T  R  T
F  R  T  F
R  T  F  ?
R  F  T  ?

From this we can see that an answer of True/Yes means that B is non-random, and an answer of False/No means that C is non-random.
From now on, our last 2 questions will be put to the identified non-random guy - assume B

Second question, put to B

2) If I asked the non-random guy in A, C whether A was random, what would he say?

A B C Answer
R T F F
R F T F
T F R T
F T R T

As we can see, an answer of true means that A is random and an answer of false means that C is random. Assume A is random

Third question, put to B

3) If I asked C if he always spoke the truth, what would he say?

A B C
R T F T
R F T F

This identifies B and C.

Unfortunately we don't know yes and no, so question 3 needs to be phrased something like:

Defining a xor b as the question 'Is it true that the answer to a is yes or the answer to b is yes but the answers to a and b are not both yes?', what is the answer to the question: 'If I asked C if he always spoke the truth, what would he say?' xor 'does da mean yes?'
Asking the questions this way we can take an answer of ja to mean 'yes'

At the end we have identified A, B and C, but still don't know what da means!

Comments?

Paul Viney
Saturday, October 04, 2003

*  Recent Topics

*  Fog Creek Home