Dr. Math FAQ ||
Classic Problems ||
Formulas ||
Search Dr. Math ||
Dr. Math Home

A princess visits an island inhabited by two tribes. Members of one tribe always tell the truth, and members of the other tribe always lie. The princess comes to a fork in the road. She needs to know which road leads to the castle so as to avoid the fire-breathing dragon and rescue the prince from the wizard holding him captive in the castle. (Although the princess doesn't know it, the south road leads to the castle and the north road leads to the dragon.) Standing at this fork in the road is a member of each tribe, but the princess can't tell which tribe each belongs to. What question should she ask to find the road to the castle?
Simply asking which road leads to the castle won't help. The answer won't tell us which native is lying and which native is telling the truth. However, we really only need to talk to one of the natives. The trick is to ask a question where the response will be the same from both natives: a question that incorporates how a member of the tribe not answering would respond to the same question.
For example, what if we say to one of the natives, "If I asked a member of the tribe you
- If we ask a truthteller, the response will be: "He would say to take the north road." The road to the castle is the south road so the liar will tell us to take the north road, and the truthteller will faithfully report this to us.
- If we ask a liar, the response will be: "He would say to take the north road." The road to the castle is the south road and the truthteller will tell us to take the south road, but the liar will
*not*report this faithfully to us - he will say the opposite.
In both cases we'll get the same response. We should do the opposite of what we have been told because, regardless of whether we are speaking to a liar or a truthteller, our question will always produce the wrong answer to which road we should take. ## From the Dr. Math archives:-
The Truth-teller, the Liar, and Ambiguous
What Question Does She Ask? Which Twin is Telling the Truth? Who is a Liar, Who Tells the Truth?
## The general caseForget about north and south, villages and castles, and everything else for the moment. This is really a problem about how to tell when a proposition P is true or false when questioning someone who might lie to you. Suppose we have some proposition, P, about the world -- for example, "The Pope is Catholic," which happens to be true, or "3 is greater than 5," which happens to be false. If we ask the question, "Is P true?" of a truth-teller (T) and a liar (L), we get the following result, depending on whether the proposition is true (t) or false (f): T L +----------- Is P true? P = t | yes no | P = f | no yes This is the case for In order to get past this obstacle (i.e., in order to get the truth-teller
and the liar to give the same answer), you need to ask about a proposition
upon which they would Therefore, you need to make P a proposition about the person that you're talking to. For example, P could be "You are a liar." Now when we ask "Is P true?" we get the following result: T L +------------ Is P true? P = t | - no | P = f | no - (Note that if you're talking to a truth-teller, P can't be true, and if you're talking to a liar, P can't be false.) So we've found a way to get the same answer from either kind of person, which is good. But the answer to the question itself doesn't tell us what we want to know. So what we really need to do is to ask a question that is about both the
world T L +------------ Is P' true? P = t | no no | P = f | yes yes Which is exactly the result that we want. Regardless of whether we are talking to a truth-teller or a liar, if the answer is "No," we know that P is true, and if the answer is "Yes," we know that P is false. So we can now get a correct evaluation of any proposition P. Let's consider once more what happens if we ask about a proposition whose truth we already know, e.g., "The Pope is Catholic." We get the following result: T L +----------- Is P true? t | yes no | f | no yes Now let's make P' the proposition "If I asked you whether P is true, you would say 'yes'." What kind of result would we get? It's easy to see how the truth-teller would answer: T L +----------- Is P' true? t | yes ? | f | no ? But what about the liar? Let's consider the case where P is true. If asked whether P is true, a liar would have to say 'no'. But since he can't truthfully tell you what he would say, he'd have to say 'yes'. Which is the same answer given by the truth-teller: T L +----------- Is P' true? t | yes yes | f | no ? Now let's consider the case where P is false. If asked whether P is true, a liar would have to say 'yes'. But since he can't truthfully tell you what he would say, he'd have to say 'no'. T L +----------- Is P' true? t | yes yes | f | no no So this is another way to get a correct evaluation of any proposition P. Note that in this case 'yes' means 'true' and 'no' means 'false'. By the way, as I read it, the problem doesn't say that you are limited to one question, so my own question would be something like "Is the Pope Catholic?" The answer to that question would tell me what kind of person I was dealing with, and I could adjust the answers to subsequent questions accordingly. - Dr. Ian |

[**Privacy Policy**]
[**Terms of Use**]

Math Forum Home ||
Math Library ||
Quick Reference ||
Math Forum Search

© 1994- The Math Forum at NCTM. All rights reserved.

http://mathforum.org/