Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10    5/3/83; site cornell.UUCP
Path: utzoo!linus!decvax!microsoft!fluke!ssc-vax!uw-beaver!cornell!mwk
From: mwk@cornell.UUCP (Mark W. Krentel)
Newsgroups: net.math
Subject: A liar, truth-teller, and random puzzle.
Message-ID: <5522@cornell.UUCP>
Date: Thu, 20-Oct-83 14:41:55 EDT
Article-I.D.: cornell.5522
Posted: Thu Oct 20 14:41:55 1983
Date-Received: Sun, 23-Oct-83 14:59:33 EDT
Sender: mwk@cornell.UUCP
Organization: Cornell Computer Science
Lines: 43

From: mwk (Mark W. Krentel)
To: net-math, net-puzzle

   My Information Theory professor gave us this problem in class
(not an exam) last semester, and I found it interesting.

   You recall the problem of the liar and the truth-teller:
Given two people, one of which always lies while the other always
tells the truth, how can you determine which is which using one
yes/no question?  The answer is very easy, ask one of them if 0=0.

   Now, generalize the problem to allow 3 people, one liar, one
truth-teller, and one who answers randomly.  You are guaranteed
there is exactly one of each.  Now, there are 3! = 6 possibilities,
so clearly 3 questions are needed in the worst case.  The problem
is to show that 3 questions always suffice to identify them.
You may assume:

     (1) they each know the identities of the other two.
         (You will need this assumption.)

     (2) either the random person answers yes/no with equal
         probability, OR the random person is a daemon that can
         anticipate your future questions and tries to frustrate you.
                                             

   (A) The first part is to show that this can always be solved in
       a finite number of questions.
 
   (B) After solving (A), you should see how to obtain a simple 
       solution using only 4 questions.

   (C) Then show that 3 questions suffice.   This last part took
       me a half-hour with pencil and paper and isn't very obvious.
       I claim that the first question is essentially unique, i.e.,
       any first question in a solution to (C) is equivalent to
       it or its negation.

   If there is sufficient interest, I will give a solution in
a couple weeks.

                                         Mark W. Krentel
                                         mwk at Cornell, CS