Problem 27.1 Medium Free

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 LL 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 LL, the liar would say “yes” exactly when LL is false. The truth-teller reports this faithfully, so he answers “yes” exactly when LL is false.
  • You asked the liar. The other dwarf is the truth-teller. Asked about LL, the truth-teller would say “yes” exactly when LL is true. The liar misreports this, so he answers “yes” exactly when LL is false.

In both cases the answer is “yes” if and only if LL 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 LL. The liar would lie about LL, 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” ⇒\Rightarrow go left; “yes” ⇒\Rightarrow go right.