A little while ago I posted a brainteaser: the three demons puzzle. For those who didn’t get it, who nearly got it, or who just wanted to compare answers, or who just couldn’t be bothered to try, here’s the solution.
Solution – Short Version
- “Amos, is it true that either (a) ‘da’ means ‘yes’ and Baeti lies more frequently than Corpi or (b) ‘ja’ means ‘yes’ and Corpi lies more frequently than Baeti?”
- If:
- Answer is “ja”: “Corpi, is exactly one of the following two statements true: (a) ‘da’ means ‘yes’; (b) this is my second question?”
- Answer is “da”: “Baeti, is exactly one of the following two statements true: (a) ‘da’ means ‘yes’; (b) this is my second question?”
- To the same demon again: “Is it true that either (a) ‘da’ means ‘yes’ and Amos answers randomly, or (b) ‘da’ means ‘no’ and Amos does not answer randomly?”
- If the answer to both question 2 and question 3 is “ja”, then Amos is the liar, the demon spoken to in questions 2 and 3 is the honest one, and the remaining demon is the random one.
- If the answer to question 2 is “ja” and the answer to question 3 is “da”, then Amos is the random demon, the demon spoken to in questions 2 and 3 is the honest one, and the remaining demon is the liar.
- If the answer to question 2 is “da” and the answer to question 3 is “ja”, then Amos is the random demon, the demon spoken to in questions 2 and 3 is the liar, and the remaining demon tells the truth.
- If the answer to both question 2 and question 3 is “da”, then Amos tells the truth, the demon spoken to in questions 2 and 3 is the liar, and the remaining demon answers randomly.
Solution – Long Version
If your brain wasn’t fully pickled by the short version and you’re brave enough to take on the long version, here it is:
First Question
Our first goal is to find one of the demons who is not the demon who always answers randomly, because such a demon would just be bad news. My initial attempt at solving the puzzle started with about seven questions which got cut down to four when I realised the importance of this first step, and then later to three.
There are, essentially, 12 different states of play that we have to consider and find a way of differentiating between:
Demon state
(T = truthful, L = liar, R = random)State Amos Baeti Corpi meaning of “da” 1 T L R yes 2 T R L yes 3 L T R yes 4 R T L yes 5 L R T yes 6 R L T yes 7 T L R no 8 T R L no 9 L T R no 10 R T L no 11 L R T no 12 R L T no For no particular reason, we ask our first question to Amos: at this point, all possibilities are equal. We ask “Amos, is it true that either (a) ‘da’ means ‘yes’ and Baeti lies more frequently than Corpi or (b) ‘ja’ means ‘yes’ and Corpi lies more frequently than Baeti?” This cleverly-worded question helps us to separate the possibilities in the following ways:
The “lies more frequently” clause is a quick way to obtain information quickly about the relationship between the other two demons (assuming that Amos is not answering randomly), rather than asking a more simple question which, in turn, could only have a true or false answer. Liars (L) will lie more frequently than random demons (R), because random demons will sometimes tell the truth, and random demons will lie more frequently than truthful demons (T), because truthful demons always tell the truth. On my paper diagrams, I drew arrows between the columns of Baeti and Corpi, one for each row, indicating who lied most frequently of the two in each state.
The combination of the “test for meaning of da/ja” and “demon X lies more frequently than demon Y” gives us a wonderful split in the results, laterally, through the da-meanings. This occurs because the pattern of possibilities is now identical for each meaning of “da”, as shown:
State Amos meaning of “da” Answer Amos says… 1 T yes yes da 2 T yes no ja 3 L yes no da 4 R yes no da/ja 5 L yes yes ja 6 R yes yes da/ja 7 T no no da 8 T no yes ja 9 L no yes da 10 R no yes da/ja 11 L no no ja 12 R no no da/ja As you can see, the lateral split ensures that we get the same answer from Amos regardless of the meaning of “da” (notice how the pattern of “Amos says…” repeats itself in the second half of the table).
In states 4, 6, 10 and 12, Amos may say “da” or “ja”, because Amos is the random demon. This is not a problem, because the entire point of this question is to determine which of the other two demons is not a random demon (no matter what the configuration, this must be the case for at least one of them): whichever way he happens to answer is irrelevant, because whomever of Baeti and Corpi we choose as our “definitely not random” demon, we’ll be right.
In states 1, 3, 7, and 9, and, potentially, in the four ambiguous states – the states in which Amos will answer this first question with “da” – we can see from the original table that Baeti can only ever be truthful or a liar; never random. In states 2, 5, 8 and 11 (and, again, potentially, the random responses Amos would give in states 4, 6, 7 and 9) the response “ja” shows us (check the original table again) that Corpi is never random.
Therefore, this single question tells us that one of Baeti at Corpi is not random, and which one. This is valuable information, because we can trust the information given by non-random demons in order to trick them into revealing whether or not they are random.
Second Question
From here on, we’ll be dealing with whichever demon we decided, through question one, is definitely not a random demon: either Baeti or Corpi. The one we have chosen shall be known as x1, and the other shall be known as x2.
Next, we can use a slightly more complicated version of the question one must ask gaolers (when one lies and one tells the truth – you know the puzzle I mean) in order to determine if the demon we’re dealing with, x1, is truthful or a liar (we have already ensured through question one that Amos or x2 are random, so x1 cannot be). We ask, “[x1], is exactly one of the following statements true: is exactly one of the following two statements true: (a) ‘da’ means ‘yes’; (b) this is my second question?”
Again, this is a lateral split technique: by demanding that exactly one of the criteria must be met in order for the response to be true (and knowing that the liar demon will say that respond negatively if it is and that the honest demon will respond positively), we ensure that half of the possible states are treated differently, like so:
x1 state meaning of “da” actual answer demon’s answer demon says… T yes no no ja L yes no yes da T no yes yes ja L no yes no da See what we did there? By setting up a question involving both the meaning of the word “da” and an indisputable fact (that this is our second question – although we could equally use any other indisputable fact and these demons, knowing everything, would understand) we set up the answers in the heads of the “da = yes” theoretical demons than in the heads of the “ja = yes” ones. Because we know that lying demons will invert the answer we can identify them. Now, we know whether or not x1 is an honest demon or a liar.
Unfortunately, we still don’t actually know the meaning of the word “da” (or “ja”) so we can’t just ask our new-found honest demon (or easily-manipulated known liar) about his friends, and to ask about the meaning of the words would use up our last question and still leave us in the dark about the nature of the other two demons.
Third Question
We need one more fact – the identity of one of the remaining two demons – but we don’t understand the language well enough to just ask, so we’ll have to do our language-inversion trick again to “flip” the results of the second half of the table and thereby be able to understand the results (even if we don’t know the language).
We ask “Is it true that either (a) ‘da’ means ‘yes’ and Amos answers randomly, or (b) ‘da’ means ‘no’ and Amos does not answer randomly?” Spot the inversion again – “da means yes”/”da means no”!We already know whether or not x1 is honest, so we can dramatically simplify our tables:
If x1 is known to be honest:
Amos state meaning of “da” actual answer demon’s answer demon says… L yes no no ja R yes yes yes da L no yes yes ja R no no no da
Amos state meaning of “da” actual answer demon’s answer demon says… T yes no no da R yes yes yes ja T no yes yes da R no no no ja It’s probably possible to rewrite the question to get more beautiful truth tables, but I honestly couldn’t be bothered. If x1 is honest and says “ja” then we know that Amos is a liar, and if he says “da” then we know that Amos is random. If x1 is a known liar than “da” means that Amos is the honest one and “ja” means that Amos is the random one.
We’ve now ascertained the identities of two of the demons, and the third is therefore obvious.
Now wasn’t that a mind-blowingly cool puzzle?