Logic Puzzle: Truth Tellers and Deceivers
Steven Den Beste has a discourse on an old Martin Gardner puzzle (which is more interesting that the political point he was trying to make; I’m more inclined to think a better explanation lies less in terms of active malice than being trapped in orthodoxies and mind sets). This logic puzzle is an old one that I remember appearing in the old Tom Baker Dr. Who episode, The Pyramids of Mars and saw recently in some Japanese anime thing. The Gardner variation is:
Suppose you have two villages, one that always tells the truth and one that always lies. At a fork in the road, you meet one member of each village, and you can only ask one question of either villager. Down one branch of the fork is your destination village; down the other is more wilderness. What do you ask the pair of villagers to know which way to go?
Basically, you phrase your one question so that the truth values of both individuals are taken into account. You ask one of them, what road will your companion point me down? Then you go the other way, because he would have pointed you down the wrong road.
The discussion of the puzzle becomes more interesting once you remove the constraints of binary logic. In the original variation, the villagers are like computers: they either answer truthfully or falsely, without regard to the intention of your question. Because they’re constrained by logic, you can use logic to get the right answer. However, suppose that the village of liars is peopled with real deceivers, whose goal is to mislead you. In this case, the deceiver would know the intent of your question, and act to confound your intentions. There is no logical way to get the truth out of this situation.
One of Gardner’s readers notes this, and proposes that the proper question is, did you know there’s free beer at my destination? The truth-teller would head down the right road to get the free beer. The deceiver would be in a quandry: does he want free beer more than deceiving you? Following him, in the worst case, may mean that you don’t get to your destination any time soon, but you’ll have the satisfaction of denying the deceiver free beer.
Just an extra note: Brad DeLong has a page of what will eventually be 100 interesting math calculations that he’s using to teach his children about logical/mathematical thinking. Interestingly, it’s a Wiki, so other people can contribute.
October 2nd, 2004 at 10:17 pm
Here’s a more interesting and complicated liar/truth teller puzzle:
In a certain land, the inhabitants are only one type or the other. You meet three of them. You ask # 1 if he tels the truth. You don’t hear what he responds (“yes” or “no”). Number 2 says that # 1 responded, “Yes.” (“I tell the truth”). Number 3 says that # 1 is, in fact a liar. The question to solve is, “(based on just the above information), “How many of each are there?”
Email me if you think you’ve gotten the answer and explain what your reasoning was or if you want the correct answer and reasoning.
October 2nd, 2004 at 11:20 pm
I’m not sure if this puzzle is more complicated. The original puzzle required you to form a question to ask and elicit a response that would be useful. I think it’s relatively hard to come up with a good question.
The puzzle you propose can be solved by, say, drawing a diagram and mapping out the relatively limited set of possibilities. As the only variable is what #1 said, let’s consider what he said:
You ask him if he tells the truth. If he is a truth-teller, he’ll answer “Yes”. If he’s a liar, he’ll answer “Yes” also. So #1 will always answer yes to your question. Consider #2, then, who says that #1 answered “Yes”. #2 is a truth-teller, otherwise he would have said “No”. Lastly, consider #3 who says that #1 is a liar. If #1 is a liar, then #3 is a truth-teller. If #1 is a truth-teller, then #3 is a liar. So, while it’s not possible to determine whether #1 or #3 is the liar, we can say for sure that there are two truth-tellers and one liar in that group.
As noted, I feel this is less complicated because all the information is all there, and it’s just a matter of working through the possibilities. The original puzzle, on the other hand, required invention.