Free drinks in the pub.

A tourist is enjoying an afternoon refreshment in a local pub in England when the bartender says to him: “Do yu see those 3 men over there? One is Mr. X who always tells the truth, one is Mr Y who always lies and one is Mr. Z who sometimes lies by randomly answering questions with yes or no.

You may ask them 3 yes or no questions indication who should answer. If after asking these questions you can identify Mr. X, Mr. Y and Mr.Z, they will buy you a drink. What yes or no questions should the thirsty tourist ask?

The first question is important. It should be asked in such a ways so that you can eliminate Mr.Z. It is easier to deal with a person who always tells the truth or who always lies.

Advertisements

6 Comments

  1. We can label the people (say by distance from us) as A, B and C. With no prior knowledge we may as well ask
    the first question to A. A could be a knight, a knave or a normal (that’s what we call people who lie or tell the
    truth at random). The hint tells us that if should use the first question to identify someone who is not normal —
    once we have done that the rest is easy: ask a knight or a knave if 2 + 2 = 5 and you immediately know what
    they are and can then use them to tell you the rest are with one question.

    The Eureka step is to realise that you can calculate the first question by working out what properties it must
    have and then rearranging a description of the properties as propositions into the form:

    where Q stands for a question of the form “Is it True that . . . ” where the question is trying to identify whether
    B is normal or not.

    In this case our first question (to A) should satisfy the
    following:

    1 If A is a knight and A says Q is True then B is normal.

    2 If A is a knave and A says Q is True then B is normal.

    3 If A is a knight and A says Q is False then B is not normal.

    4 If A is a knave and A says Q is False then B is not normal.

    We can represent the above as a compound proposition — we use “BN” to represent “B is normal”; “Q”
    stands for “Q is True”. Remember that is a knave says “Q is True” that “not Q” is really the case (and vice-
    versa).

    (A and Q) ⇒ BN
    and
    (not A and not Q) ⇒ BN
    and
    (A and not Q) ⇒ not BN
    and
    (not A and Q) ⇒ not BN

    We now use the following identity (use a truth table to prove the
    identity):

    ( p and q) ⇒ r ≡ q ⇒ ( p ⇒ r)

    This gives us:

    Q ⇒ (A ⇒ BN)
    and
    not Q ⇒ (not A ⇒ BN)
    and
    not Q ⇒ (A ⇒ not BN)
    and
    Q ⇒ (not A ⇒ not BN)

    We now use the identity: (again prove that this is an
    identity)

    ( p ⇒ q) and ( p ⇒ r) ≡ p ⇒ (q and r)

    Q ⇒ ( (A ⇒ BN) and (not A ⇒ not BN) )
    and
    not Q ⇒ ( (not A ⇒ BN) and (A ⇒ not BN) )

    We finally use the definition of ⇐⇒ and the identity:

    not p ⇐⇒ q ≡ not( p ⇐⇒ q)

    to get:

    Q ⇐⇒ (A ⇐⇒ BN)

    So in English our first question (to A) would be:

    Is it true that the statement that you are a truth teller is equivalent to the statement that B is normal ?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s