Name of the Logical Puzzle with One Always Lies and One Always Tells the Truth

logicpropositional-calculuspuzzle

So i was solving exercises in propositional logic lately and stumbled upon a puzzle, that goes like this:

Each inhabitant of a remote village always tells the truth or always lies. A villager will only give a "Yes" or a "No" response to a question a tourist asks. Suppose you are a tourist visiting this area and come to a fork in the road.
One branch leads to the ruins you want to visit; the other branch leads deep into the jungle. A villager is standing at the fork in the road. What one question can you ask the villager to determine which branch to take?

I intuitively guessed the answer is "If I asked you this path leads to the ruins, would you say yes?". So my questions are:

  1. What is the name and/or source of this logical riddle?
  2. How can i corroborate my answer with mathematical rigor?

Best Answer

The specific problem is shown in My Best Mathematical and Logic Puzzles, by Martin Gardner. It was in his Scientific American column long ago. The solution is on page 40 with a reference in 1957. The problem itself is the fourth one and is on the page 2. The full definition of the problem is, as published on This Side of the Pond:

The Fork in the Road

Here’s a recent twist on an old type of logic puzzle. A logician vacationing in the South Seas finds himself on an island inhabited by the two proverbial tribes of liars and truth-tellers. Members of one tribe always tell the truth; members of the other always lie. He comes to a fork in a road and has to ask a native bystander which branch he should take to reach a village. He has no way of telling whether the native is a truth-teller or liar. The logician thinks a moment and then asks one question only. From the reply, he knows which road to take. What question does he ask?

Added: the point is that you get only one bit of information. You need that bit to tell you which road leads to the village, so you can't learn whether the native tells the truth or lies. The key to many of these puzzles is finding a way to get the information you need without getting anything more. In this case (and in many truth-teller/liar puzzles) the secret is arranging two negations so you get the answer you need.

Related Question