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:
- What is the name and/or source of this logical riddle?
- 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:
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.