mwk@cornell.UUCP (Mark W. Krentel) (10/20/83)
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, CSnm@hou2b.UUCP (10/31/83)
Let T, L, and R represent a truth teller, a liar, and one who
answers randomly, respectively. It is known of A, B, and C
that one is T, another is L, and the thrid is R. The following
procedure determines who is who using 3 yes/no questions.
Ask A: Q1. Does ABC eual either LRT or TLR?
If he ansers "yes", ask the follwing two questions from B
Q2. Is 3 an even number?
Q3. Does A=R?
If the answer to Q1 is "no" ask the same Q2 and Q3 from C.
The followng chart dertermines who is who:
Q1 Q2 Q3 A B C
------------------------------
Y Y Y T L R
Y Y N R L T
Y N Y R T L
Y N N L T R
N Y Y T R L
N Y N R T L
N N Y R L T
N N N L R T