three_gods.md

Solution to Three Gods Logic Puzzle

1. Ask god A: "Would the other non-random god answer 'Ja' to the question 'Does the random god sit to your left¹?'"

=> If the answer is 'Ja', then it's false (or random), therefore NonRandom1 = C; else it's true (or random), therefore NonRandom1 = B

2. Ask gods[NonRandom1]: "Would the other non-random god answer 'Ja' to the question 'Does the random god sit to your left¹?"

=> If the answer is 'Ja', then it's false, therefore NonRandom2 = left_of(NonRandom1); else it's true, therefore NonRandom2 = right_of(NonRandom1)

3. 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 of B; B is left of C; C is left of A

  right is also circular, the other way

Analysis

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 is Random. (If A is Random, B and C cannot be Random 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