12 Nov 2008
Puzzle

A traveler has to pass tests of increasing difficulty to meet an Eastern mystical master. For the first test, he meets a pair of twins at a fork in the road: one path leads to the jungle, the other to the mystic. One of the twins always says the truth, the other always lies. What yes/no question should you ask one of the twins to determine the path that goes to the mystic? For the second test, the traveler encounters a second fork in the road. Again, one path leads to the jungle, the other to the mystic. This time, there are three look-alike brothers: one always tells the truth, the second always lies but the third sometimes tells the truth and sometimes lies. What two Yes/No questions should the traveler ask two of the brothers to determine the path to the mystic? Each question is answered by only the brother it is posed to. For the second question, the traveler may choose the brother and the question depending upon the answer to the first question.

Source

Logic puzzles like these are the brainchild of Raymond Smullyan, a famous logician who has devised hundreds of them to illustrate key theorems in logic through series of puzzles! The three-brother problem above was borrowed from The Puzzle Toad, Number 14 — Restrooms. Many more puzzles are to be found in books by Robert Smullyan.

Solution

The two-brother problem may be solved in two different ways:

1. The traveler may ask, "Would your brother agree that the road on the left leads to the mystic?" The answer is guaranteed to be 'Yes' if and only if the road on the right leads to the mystic.
2. The traveler may ask, "If I were to ask you whether the road on the left leads to the mystic, would you say 'Yes'?" The 'if i were to ask you' construct makes both twins tell the truth. So if the answer is 'Yes', the road on the left indeed leads to the mystic, otherwise the road on the right does so.

Solutions to the three-brother problem:

1. With 4 questions: We first ask each brother, "Is one of the other two inconsistent, i.e., sometimes tells the truth and sometimes lies?" The truthful brother would say 'Yes', the lying brother would say 'No'. The third brother might say 'Yes' or 'No. Interestingly, if the answers form the multi-set {'Yes', 'Yes', 'No'}, then the 'No' answer was certainly given by the lying brother. If the answers form the multi-set {'Yes', 'No', 'No'}, then the 'Yes' answer was certainly given by the truthful brother. No other multi-set of answers is possible. So the fourth question may be posed appropriately to either the truthful brother or the lying brother depending upon which multi-set was observed.
2. With 3 questions: We ask the same question to all three, "Would your consistent brother (who always tells the truth or always tells lies, other than you) agree that the road on the left leads to the mystic?" In response, the consistent brothers would both say 'Yes' or both say 'No'. The inconsistent brother may say either 'Yes' or 'No'. So the majority vote allows us determine which road leads to the mystic.
3. With 2 questions: The key idea is to utilize the first question to identify a consistent brother (who always speaks the truth or always lies). The second question is posed to the brother just identified — at this point, the problem is identical to the 2-brother problem. Let us label the brothers as #1, #2 and #3. We shall use X to denote the brother whom we shall ask the second question. Here are some possibilities for the first question. In each case, if the answer is 'Yes', set X to #3, otherwise set X to #2. Claim: X is consistent!
1. (devised by Ovidiu Gheorghioiu at Google) Ask #1 whether the following logical proposition is true: ("You always tell the truth" == "#2 gives random answers").
2. Ask #1, "Is #2 more likely to give the correct answer than #3?"
3. Ask #1, "If I were to ask you 'Is #2 consistent?', would you say 'Yes'?" Note that the 'if I were to ask you' construct makes consistent brothers truthful!
The second question is posed to X (see the solution to the 2-brother problem). Either of the following suffices: