One Question for Liar and Truth-Teller
A traveller reaches a fork in the road: one path leads to a sage, the other into the jungle. Two dwarfs stand at the fork; one always tells the truth and the other always lies, but you cannot tell which is which. You may ask exactly one yes/no question, addressed to either dwarf, to determine which path leads to the sage. Find such a question, or show none exists.
Work it out, then compare with the answer.
SolutionShow the worked solution
Key idea. Make the answer pass through both dwarfs, so that it contains exactly one lie whichever dwarf you ask.
Such a question exists. Point at either dwarf and ask:
“If I asked the other dwarf whether the left path leads to the sage, would he say yes?”
Let be the statement “the left path leads to the sage”. We check both cases.
- You asked the truth-teller. The other dwarf is the liar. Asked about , the liar would say “yes” exactly when is false. The truth-teller reports this faithfully, so he answers “yes” exactly when is false.
- You asked the liar. The other dwarf is the truth-teller. Asked about , the truth-teller would say “yes” exactly when is true. The liar misreports this, so he answers “yes” exactly when is false.
In both cases the answer is “yes” if and only if is false. The answer is therefore always the false answer to “does the left path lead to the sage?”, so you take the opposite of what it says. You do not need to know which dwarf you asked.
Alternative. Ask either dwarf: “If I asked you whether the left path leads to the sage, would you say yes?” The truth-teller answers truthfully about . The liar would lie about , and then lies again about what he would say. The two lies cancel. So here “yes” means left.
Ask either dwarf: “Would the other dwarf say the left path leads to the sage?”
Answer “no” go left; “yes” go right.