- Ask god
A
: "Would the other non-random god answer 'Ja' to the question 'Does the random god sit to your left1?'"
=> If the answer is 'Ja', then it's false (or random), therefore NonRandom1 = C
;
else it's true (or random), therefore NonRandom1 = B
- Ask
gods[NonRandom1]
: "Would the other non-random god answer 'Ja' to the question 'Does the random god sit to your left1?"
=> If the answer is 'Ja', then it's false, therefore NonRandom2 = left_of(NonRandom1)
;
else it's true, therefore NonRandom2 = right_of(NonRandom1)
- Ask
gods[NonRandom1]
: "Would the other non-random god answer 'Ja' to the question 'Are you the True god?'"
=> If the answer is 'Ja', then it's false, therefore gods[NonRandom2] = 'False'; gods[NonRandom1] = 'True'
;
else it's true, therefore gods[NonRandom2] = 'True'; gods[NonRandom1] = 'False'
Now that NonRandom1
and NonRandom2
have been identified, the remaining god must be 'Random'
.
-
1.
A
is left ofB
;B
is left ofC
;C
is left ofA
right is also circular, the other way
There are 3 gods in positions A
, B
, and C
, so there are 3 x 2 x 1 = 6 permutations:
A | B | C |
---|---|---|
True | False | Random |
True | Random | False |
False | True | Random |
False | Random | True |
Random | True | False |
Random | False | True |
We are permitted to ask 3 boolean questions, so the total information that can be communicated is 2^3 = 8 possibilities to identify 1 of 6 permutations.
The problem can be broken down into 3 sub-problems:
-
Q. How do we avoid
Random
's answers messing up our search? -
A. We can eliminate
Random
in the first pass by asking one god (we choose A arbitrarily) for the location of the random god, then addressing the following questions to the god who is not A and is not who A said isRandom
. (IfA
isRandom
,B
andC
cannot beRandom
so either is a safe choice.) -
Q. How do we learn the truth from the non-
Random
gods when one of them always lies? -
A. We can always ask the non-
Random
god how the other non-Random
god would answer. This way we will always get a lie--either lie(truth) or truth(lie)--which we can then invert for the truth. -
Q. How can we know true/false when the gods respond in their own language, 'Ja'/'Da'?
-
A. We can ask the question in terms of one of their words (effectively applying an
XOR
that cancels out their vocabulary word). Consider a true response. If 'Ja' means true and we ask if the response is equal to 'Ja', we'll get back(true == true) = 'Ja'
; if 'Ja' means false we'll get back(true == false) = 'Ja'
. (And then we will need to invert that because of the earlier rule.)
Here are all 6 permutations showing the answers to the 3 inner questions (those in single quotes in the solution above) and the interim decisions of which gods are NonRandom1
and NonRandom2
. Note that the last two have two different reply paths each since the Random
god can answer either way. These extra rows consume the remaining 2 spare possibilities to map 8 possibilities into 6 permutations! Note that all combinations of answers (1, 2, 3) are unique, which proves that we can use those answers to deduce the god positions A
, B
, C
.
A | B | C | <--- | 1 | 2 | 3 | NonRandom1 |
NonRandom2 |
---|---|---|---|---|---|---|---|---|
True | False | Random | 'Da'=true |
'Ja'=false |
'Da'=true |
B | A | |
True | Random | False | 'Ja'=false |
'Da'=true |
'Da'=true |
C | A | |
False | True | Random | 'Da'=true |
'Ja'=false |
'Ja'=false |
B | A | |
False | Random | True | 'Ja'=false |
'Da'=true |
'Ja'=false |
C | A | |
Random | True | False | 'Ja'=false |
'Ja'=false |
'Da'=true |
C | B |
| | | | 'Da'=`true` | 'Da'=`true` | 'Ja'=`false` | B | C
Random | False | True | |'Ja'=false
| 'Ja'=false
| 'Ja'=false
| C | B
| | | |'Da'=true
| 'Da'=true
| 'Da'=true
| B | C