A personal account of solving the Three Gods Puzzle

This is the first I heard of the Three Gods Puzzle, and I have decided to log my thought process as I attempt to solve it. I don’t know if I will solve it, I have never been that good with logic puzzles. My goal is to be able to look back at it and see whether what I attempted was useful/relevant/interesting. Recording my thoughts is hard for me, they are often too fleeting to notice. Of course, recording my thoughts will necessarily affect my thought process. We’ll see what happens. The puzzle: Three gods A, B, and C are called, in no particular 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 all questions 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. It looks like there is a subtask, to identify the meaning of the words da and ja. Though it is possible that the puzzle is solvable even without doing that (how?). In any case, we start with 6 possibilities:

G = {AT BF CR, AT BR CF, AF BT CR, AF BR CT, AR BT CF, AR BF CT}.

This is less than 3 bits of information, so if we gain at least one bit per question, the puzzle can be solved. I wonder if it is even possible to gain more than one bit of information from a Yes/No answer?

Wait, in addition, there are two more possibilities:

Language = {daYes jaNo, daNo jaYes}.

They appear to be independent from the 6 above. This brings the total to 12 possibilities from the product set

GL = G x L,

which is more than 3 bits. Assuming only one bit per question can be gained, we cannot hope to figure out both the god assignment and the language assignment. So probably at the end of the day we will not know the language assignment precisely. Hmm, something is fishy here. Once the problem is solved, and we know who is who, we should be able to retrospect and see which answers were false and which true, right? If so, at least some answers should yield more than 1 bit! Or our questions are posed in a way which yields information without ever determining the language assignment. I recall something that looks like an inverse of this, actually, with just two people, truth teller (T) and a liar (L). Asking either of them if the other person lies yields “Yes”. And asking them if they lie always yields “No”. Kind of useless, but maybe if it can be inverted. What does it mean? Something like asking will tell you that one person is a liar without knowing whether the answer is Yes or No?

OK, time to simplify. The original TL puzzle ought to be solvable with one question, what is it? The liar must answer such a question differently from the truther. This is easy, just ask something you know the answer to, like is 1+1=2 or something.

What’s next?

An aside to think through: is there a way to separate R from the rest? For example, is there a question which R always answers differently than T or L? Actually, R’s answers are not truly random:

Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely. 

This means that it mimics T or F, randomly, not provides a random answer! Thus R will necessarily answer “Yes” to the question which both T and F answer “Yes”. So R’s answers are not random, only its mode of operation is.

If I can devise such a question, I can figure out the language assignment. Which still leaves me with 6 choices, just two questions and no idea about the god assignment. Seems like a bad idea. Probably should try to figure out a question which partitions the 12 cases into two parts with different god assignments.

Another toy problem to set up: is it ever possible to discriminate between 3 possibilities with one Yes/No question? Not if getting an answer is equivalent to partitioning the set of possibilities into two disjoint subsets. Can’t think of any other possibility.

So back to the original puzzle: what would be the initial or the final partition of the set GL? Let’s try the dynamic programming approach: working backwards. An example of the final subset could be

{AR BT CF, AR BF CT} x L.

Can this situation be resolved with one question, but without knowing the language assignment? Here we already know that A=R, so the hard part is presumably done. All we have left is the toy problem {AT BF, AF BT} in a slightly harder version, with unpartitioned L. … This is hard. if I have no clue whether the answer means Yes or No, how can I differentiate based on it? How do we get information from an answer that can mean either Yes or No?

Is there another final partition? If so, it is probably not of the form {something} x L. What other forms are there? Here is an example: {AR BT CF da, AR BF CT ja}. This is not a direct product! And getting an answer lets us perform the final partition without knowing the language assignment. So the next questions to ponder are:

  • which two elements G1 and G2 of G are the best candidates for the subset {G1 da, G2 ja}?
  • what type of questions lets us receive da or ja for such a subset? Heck, what type of question lets us discriminate without knowing what the answer means?
  • is there a different version of the Question 3 subset, other than {G1 da, G2 ja}?

But first, let’s spell out what G1 da means, to begin with: receiving “da” as the answer to the (yet unknown) question means G1. Maybe we can short-circuit the set L by making questions self-referential? Like “would you answer “ja” to the <question>?”. Let’s see where this leads. …Returning to this after a couple of days… Let’s first solve the puzzle with yes/no instead of da/ja. We can apparently force any of the 3 to answer truthfully with a self-referential “would you answer yes to the question …”. How many questions would it take to figure out who’s who? If 2 is enough, then the above partition logic is flawed, as we would have to gain more than 1 bit per question.

Another toy problem, forget lying, since we can deal with that. Let’s assume there are 3 people {A,B,C} hiding 3 numbers {1,2,3}. All are known to be truthful, but will only answer a yes/no question. How many questions are needed to figure out the assignment? Something simple like “A: are you hiding a?” or “A: are you hiding a or b?”. First one: partitions are Yes:{Aa{{Bb,Cc},{Bc,Cb}}, No:{Ab{{Ba,Cc},{Bc,Ca}},Ac{{Ba,Cb},{Bc,Cb}}, so 2 and 4 choices. Second one: partitions are Yes:{AaBbCc,AaBcCb,AbBaCc,AbBcCa},No:{AcBaCb,AcBbCa}, so 4 and 2 choices.

Just to be sure, I should try to find a 3 and 3 partition question. Let’s start by figuring out the equivalent partitions. Let’s simplify the notation by making ABC assignment implied by position. Then the choices are {123,132,213,231,312,321}. This is a permutation group. Let’s separate the cyclic subgroup based on 123: {123, 312,231}, The remainder is the cyclic group based on 321: {321,132,213}. It is certainly possible to ask a question based on that. So we can narrow the choices down to 3 with one  question.

OK, it does not look like there is some magical way to squeeze more than one bit of information per question. So, based on that, I need to do:

  • solve the 123 problem (easy)
  • figure out how to avoid knowing the language (harder)

Let’s start with the easy problem: 3 truthful people {A,B,C} hiding 3 numbers {1,2,3}. The questions are, for example:

  1. A: Is your number 1? Partitions: Y:123 or 132, N: 213, 231,312,321
  2. Y: B: Is your number 2? Partitions: YY:123, YN:132. N: A: Is your number 2? Partitions: NY:213,231, NN:312,321
  3. B: Is your number 1? Partitions: NYY:213,NYN:231,NNY:312,NNN:321

Next step: allow for consistent or random liars: rephrase each question as “If I asked you whether your number is <n>, what would you say?”

Second part: language-independence. Let’s try the 2 truthful people {A,B} hiding 2 numbers {1,2}, able to answer ja (j) or da (d), where the bijection from {j,d} to {yes, no} is not specified. We will attempt to incorporate the potential answer into the questions. For example, “would you answer j to “my number is 1″?”. Two cases: j=y: “Would you answer yes to “my number is 1″?” The answer is Yes if it’s 1, No if it’s not 1, or j if 1, d if not 1. Second case: j=n: Would you answer no to “my number is 1”? The answer is No if it’s 1, Yes if it’s not 1, or j if 1, d if it’s not 1. This works!

Now, let’s see if this can be transferred from AB->12 to AB->(honest,liar). The original question: “If I asked you whether you are honest, what would you say?” results in the answer Yes for Honest, No for Liar. Now incorporate shrouded answers: “If I asked you whether you are honest, would you answer with “ja”?” 4 cases: (Honest,Liar) x (ja=yes,ja=no)

  • Honest, ja=yes: answer is yes = ja
  • Honest,ja=no: answer is no = ja
  • Liar, ja=yes: “asked you whether you are honest” = yes, would you answer “yes” = no=da
  • Liar,ja=no: “asked you whether you are honest” = yes, would you answer “no” = yes=da

So this also works, we can tell the liar without knowing what “ja” means just from the reply being “da”. Now it’s time to put it all together as a solution to the original problem.

  1. Ask A “If I asked you whether you are always honest, would you answer with “ja”? Partitions: (ja:(HFR,HRF),da:(FHR,FRH,RHF,RFH)
  2. If the answer was “ja”, Ask B “If I asked you whether you are a consistent liar, would you answer with “ja”? Partitions: jaja:HFR,jada:HRF [and we don’t even need the 3rd question]. If the answer to 1 was “da”, then ask A “If I asked you whether you are a consistent liar, would you answer with “ja”? Partitions: daja: (FHR,FRH), dada:(RHF,RFH)
  3. Ask B: “If I asked you whether you are always honest, would you answer with “ja”? Partitions: dajaja:FHR, dajada:FRH, dadaja:RHF, dadada:RFH.

This is basically identical to the 123 problem, after mapping 123->HFR.

So, this solves the 3 Gods puzzle. Some notes:

  • How confident am I in this solution? Potential issues: maybe there is something wrong with using double negation to defeat the liar mode? Maybe I missed something in the mapping between 123 and HFR? Maybe there was a missed subtlety in the behavior of R, or in defeating the language barrier?
  • What are the odds that this solution is correct, in a sense that it would be accepted as correct by the person who posed it? I am feeling pretty confident, so probably 90%.
  • There is a room for more choices, up to 8 total, vs the current 6. How would one rephrase the problem to max out the number of options and requiring 3 questions every time, not sometimes 2?

OK, the moment of truth, time to check the answer in Wikipedia!

Hmm, looks like I got most of the features right, though there are multiple solutions. The following is the closest one to mine:

  • Q1: Ask god B, “If I asked you ‘Is A Random?’, would you say ja?”. If B answers ja, either B is Random (and is answering randomly), or B is not Random and the answer indicates that A is indeed Random. Either way, C is not Random. If B answers da, either B is Random (and is answering randomly), or B is not Random and the answer indicates that A is not Random. Either way, you know the identity of a god who is not Random.
  • Q2: Go to the god who was identified as not being Random by the previous question (either A or C), and ask him: “If I asked you ‘Are you False?’, would you say ja?”. Since he is not Random, an answer of da indicates that he is True and an answer of ja indicates that he is False.
  • Q3: Ask the same god the question: “If I asked you ‘Is B Random?’, would you say ja?”. If the answer is ja, B is Random; if the answer is da, the god you have not yet spoken to is Random. The remaining god can be identified by elimination.

There is also the qualification “in your current mental state” to elicit a useful response from R. Let’s see the partitions as presented in the above answers.

There is another feature I missed: “exploding god heads”, when the question posed cannot be answered either truthfully or falsely. Assuming that the gods have an option of not answering, this effectively provides us with three possible answers, Yes, No and Silence. Thus each question lets us partition the set into 3. So we can partition a 9-element set with just two questions.

Conclusion: I don’t think I screwed up anywhere, and in some ways my analysis was more thorough than what’s quoted on Wikipedia (sometimes 2 questions are enough), but in other ways it was less thorough (I missed the non-reflective ways of solving it).