Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math: FAQ

  Liars and Truthtellers  

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

 

A logic problem: What question should the princess ask?

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 don't belong to which road I should take to get to the castle, what would he say?"

  1. 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.

  2. 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 general case

Forget 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 any proposition P whose subject is the world. A truth-teller and a liar will always give different answers, because they will always agree on propositions about the world. If you don't already know whether P is true or false -- and if you knew, why would you be asking? -- then the answer to the question doesn't really tell you anything because you don't know whether the person is lying.

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 not agree. But the only difference between the two potential situations (i.e., you're talking to a truth-teller, or talking to a liar) is the identity of the person you're talking to.

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 and the person. The "standard" way to do that is to ask the person's opinion about what a member of the other group would say. That is, P' would be "A member of the other group would say that P is true." This gives the following result:

         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

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

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

Ask Dr. Math ®
© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.