Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Forks in a Road

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:
    1. "Would your consistent brother agree that the road on the left leads to the mystic?"
    2. "If I were to ask you whether the road on the left leads to the mystic, would you say 'Yes'?"

Followup

The Knights and Knaves Puzzle Generator has 382 puzzles that you might enjoy. An exhaustive analysis of Knights and Knaves puzzles — "This page is not meant for human consumption" :-) Knights and Knaves (wikipedia) and The Hardest Logic Puzzle Ever (wikipedia). Three (easy but fun) puzzles, compiled by Salvador Gutierrez.

An Interesting Puzzle: "In a room there are 100 people, numbered from 1 to 100. A person is either a knight or a spy. Knights always tell the truth, but spies may tell the truth or lie as they see fit. Every person knows the identity of everyone else. It is known that there are strictly more knights than spies present. Asking only questions of the form `Person i, what is the identity of person j?', what is the minimum number of questions which will guarantee to find everyone's true identity?" Solution by Mark Wildon at Swansea University.

Previous Puzzle: Average Salary

Four honest and hard-working computer engineers are sipping coffee at Starbucks. They wish to compute their average salary. However, nobody is willing to reveal an iota of information about his/her own salary to anybody else. How do they do it?

Next Puzzle: Bigger or Smaller

Alice writes two distinct real numbers between 0 and 1 on two chits of paper. Bob selects one of the chits randomly to inspect it. He then has to declare whether the number he sees is the bigger or smaller of the two. Is there any way he can expect to be correct more than half the times Alice plays this game with him?

12 Nov 2008
© Copyright 2008—2017, Gurmeet Manku.