Solving "The Hardest Logic Puzzle Ever"

In a paper titled "The Hardest Logic Puzzle Ever", MIT professor George Boolos discusses and explains the following puzzle:
There are three people, one of which is a True Man, who always speaks the truth. Another of which is an Eternal Liar, who always lies, while the remaining is a Random Rambler, who answers every yes-no type of question totally randomly. These three men are standing in a line facing you. Your mission, should you choose to accept it, as the seeker of the Ultimate Answer is to find out which man is the True Man (T), which man is the Eternal Liar (L) and which one is the Random Rambler (R).

You are allowed to ask only yes-no type questions. You can ask no more than three questions. Everytime you decide on a question to ask, pick any one of the three, and ask him that question. Only the picked man will answer the question. Repeat the same procedure for the next question.

Sounds easy? Wait! These people understand English, but they can't answer in English. They will answer in their own language in which "Da" and "Ja" stand for "yes" and "no", but need not be in that order. (You don't know whether "da" means "yes" or "no".)
Boolos' solution starts with three simpler puzzles, each one pretty easy to solve. Once you solve those puzzles, it doesn't take much time to realize that those three solutions, when put together will constitute the solution for the main puzzle. And before you know it, you would have solved "the hardest logic puzzle ever"!

I did that, but did not get the satisfaction of solving the puzzle. Is this how I would explain the solution? How did Boolos come up with those three smaller puzzles? Would I have been able to break the puzzle into those smaller ones?

I thought that the reasoning and motivation behind breaking the puzzle in that way is more important and insightful than the three solutions themselves. The paper did not attempt to explain that at all. On the other hand, I found the discussion of "iff" (if and only if) statements a bit cumbersome and not quite to my taste. (I have a hard time understanding the truth value of iff statements, because I have a hard time parsing those kind of statements as statements in the first place).

Here is an attempt to solve the puzzle, explaining the reasons/motivations/heuristics which went into breaking down the puzzle. I have also tried to present it in a way which does not have any "iff statements" (Don't worry if you have no idea what they even mean. Even I don't!)

Hmm... Let's see... Looks like we would have to figure out which man is which and in addition to that, figure out their language! Let's do some rough calculation: the three people could be standing in any of the following 6 ways
  1. LTR
  2. LRT
  3. RTL
  4. RLT
  5. TRL
  6. TLR
Also, "da" either means "yes" or it means "no". In total, there are 12 possibilities. We have got 3 yes-no type questions to ask. Assuming we ask the right questions so as to unearth as much information as possible, in the end, we can have only 8 kinds of responses.
  1. DDD (all three questions were answered as "da")
  2. DDJ (the last question was answered as "ja" while for the first two, we got "da"s)
  3. DJD
  4. DJJ
  5. JDD
  6. JDJ
  7. JJD
  8. JJJ
There! We have hit a fundamental obstacle! While we have 12 cases to differentiate between, we have just 8 possible outcomes to use. Something isn't right! Let's read the puzzle again. Our goal is to figure out which man is which - the puzzle tells us so. Wait! Where does it say that we have to figure out their language? Come on, once you think about it, at one level, how different is "yes" and "no" from "da" and "ja"? It is just a pair of words one meaning "not the other". As the puzzle has to be solvable, it follows that it must be solvable without figuring out the language. Can we use the fact that the da-ja language is yet another language just like yes-no language? Can we devise a way of asking the questions so that we don't need to know the translation logic between these two languages? So, here is the first thing to do - Figure out a way of asking yes-no questions such that the actual mapping between da-ja and yes-no doesn't matter.

Figured? Well, this is my way: suppose you want to ask the question "Do you have some tea?" we go ahead and ask "Would your answer be 'da' to the question 'you have some tea?'?". When answered, a 'da' should be interpreted as an 'yes' and a 'ja' as a 'no'. We can see that no matter what 'da' actually means, this scheme works.

Now that we have figured out a way of asking questions suitable to the da-ja language and making sense of the answers, let's put it in some kind of program which does this for us automatically from now on. Thus, for further discussion, we can assume that those people answer in yes-no.

This Random Rambler seems a bit troublesome, doesn't he? It looks like a question asked to him is going to be less useful (because of the utterly useless, random answer given) than a question asked to one of the two Definite Answerers. So, let's make it our strategy that we ask R as few questions as possible. That means that after the first question, we should have figured out one person whom we definitely know to be not Random Rambler. Here, we note that we are just interested in whether a person is Random or Non-Random. A thought comes to my mind - Can we somehow ask questions in such a way that both L and T answer the same way? Because, after all, at this stage, we don't even want to differentiate between them. Next thought - Say, somehow we can get both of them to answer the same way, then there must be a way to get both of them to answer the question as if it were being answered by T!

Let's see if we can do that. If we look at it, L flips the true answer (like a NOT gate) while T gives the true answer (like a straight wire). We know that flipping first and then keeping it as it is is same as keeping it as it is first, then flipping it (adding a wire after or before the NOT gate doesn't change anything). This gives us a hint - make them make use of how the other thinks (let the wire make use of the NOT gate and let the NOT gate use the wire). Here is my way: if you want to ask the question "X?" ask "Would the other answer 'no' to the question 'X?'". (wire, a NOT gate and then again a NOT gate). You can see that irrespective of whom you ask the question, if the true answer to "X?" is "yes" they would answer "yes" and if it is "no", they would answer "no".

With the above technique, we have a way of asking questions such that both L and T answer it as if they are T. So for this part, now we have reduced the problem to T T and R. 3 situations arise:
  1. TTR
  2. TRT
  3. RTT
We need to pick one T. Say, we pick the middle person for questioning and we are going to pick one of the end-persons as our Non-Random guy. Have a look at case number 2. No matter what you ask R and what he answers, we can pick either left or right and we will anyway be correct in picking a T. This means that we just need to worry about case 1 and case 3. What question should we ask the middle T? Oh wait! He is a T after all! Let's just ask whether the person to his left is R or not and pick accordingly!

So far, we have picked up a T for further questioning, but we don't know which of the remaining two is R. Simple! Pick any on of those two and ask the T earlier chosen whether this one is R. Good! We have determined which one is R. One more question remaining. We have 2 people remaining: T T.

Now, let's forget about the technique using which we converted our questions such that the L became T. Now we have L and T and we don't know which one is which and we have one question remaining. Got it? Congratulations! Just pick any one and ask one obvious question "Is 'one' same as 'one'?" The Eternal Liar would answer "no" the Truth Man would answer "yes". Mystery solved!

The wikipedia article on "the hardest logic puzzle ever" spells out the verbose and long questions one needs to ask when we actually put in the abstractions and techniques we saw into framing the questions. I don't wish to reproduce them here :)

No comments :

Post a Comment

Note: Only a member of this blog may post a comment.