The Truth-teller, the Liar, and Ambiguous

Date: 7/9/96 at 3:47:5
From: Humphrey Clerx
Subject:The Truth-teller, the Liar, and Ambiguous

Hello Dr. Math,

There are three people in front of you. You know that:

One of them is God. He knows everything, and always tells the truth.
One of them is the Devil. He also knows everything, but lies. 
The third person knows nothing, but answers questions as if he knows 
the answers. His answers, however, are completely useless and could be 
right or wrong.

You can ask a total of three questions that can correctly be answered 
with yes or no, each to one of the persons. You may choose whom to ask.

Determine who is who...

Regards,

Humphrey

Date: 7/18/96 at 16:38:56
From: Doctor Sydney
Subject: Re: The Truth-teller, the Liar, and Ambiguous

Dear Humphrey,

What a great problem!  I had a fun time working on it.  The solution 
is certainly not obvious, in my opinion - that is part of what made 
it so interesting.  But, so that you, too, can enjoy the fun of 
solving the problem yourself. I'll give you a few hints, and then you 
can work on it. If after having worked on it more you are still stuck, 
write back, and I can help more.  

 No. 1        No. 2         No. 3
  a G           D             K
  b G           K             D
  c D           K             G
  d D           G             K
  e K           D             G
  f K           G             D

2. Given a set of questions, we can, for each different way G, D, and 
   K are standing, determine what the answers to those questions will 
   be.  For instance, suppose we were looking at the following set of 
   questions:

  i. (To individual #1) Is G standing in the middle?
 ii. (To individual #2) Is D to the left of G (assume, this is the 
     left from our perspective, not theirs.  Thus, above in row f, K 
     is to the left of G and G is to the left of D and K is to the 
     left of D)?
iii. (To individual #3) Does D tell the truth?

Then, if G, D, and K are standing in order (a) where G is in the #1 
spot, D is in the #2 spot, and K is in the #3 spot, then we will get 
the following  answers:  

  i. No. (G tells the truth, and the truth is that G isn't in the    
     middle). 
 ii. Yes. (D always lies, and the truth is that D is NOT to the left   
     of G).
iii. No or Yes (K could answer either way - K lies and tells the    
     truth arbitrarily). 

So, the point of all of this is that, given a set of questions, we can 
determine for each case a, b, c, d, e, and f, what the answers will 
be.  Our goal, then, is to come up with a set of questions such that 
when we figure out what  a, b, c, d, e, and f will say, they will all 
be distinguishable from one another.  So, does the above set of 
questions work?  In other words, could we have had a sequence of 
answers No Yes No or No Yes Yes from one b, c, d, e, or f?  Well, you 
can look at b, c, d, e, and f, and discover that this wasn't really a 
good set of questions.  Row b might answer the same way row a 
answered, and so, if we were to get the answers No Yes Yes, we 
wouldn't know whether we had arrangement a or arrangement b.  

So, we need to search for a better set of questions.  How can we do 
that?  Well, certainly one way to do that is trial and error.  Think 
of three questions you think might give you enough information to 
figure out who's who.  This is a method that will sometimes randomly 
work, but if you are like me, you probably won't be lucky enough to 
happen upon the solution, so perhaps a further analysis of the problem 
is needed.  Let's make some more observations:

3.  Your three questions CAN depend on previous answers.  Thus, your 
rule for asking three questions might be something like the following:

First, ask question a. If the answer to question a is yes, then ask 
question by.  If the answer to question a is no, then ask question bn.  
Now do the same thing for question c - let it depend on question b's 
answer.

So, the following scheme sums it all up:

   a -- yes -- by -- yes -- cyy
   a -- yes -- by -- no  -- cyn
   a -- no  -- bn -- yes -- cny
   a -- no  -- bn -- no  -- cnn

So, the first line of the scheme indicates that if the answer to 
question a is yes, ask by.  If the answer to question by is yes, ask 
question cyy. 

Okay, this is very important, and will most likely help you come up 
with a good set of three questions.  

Okay, my observations are over.  The neat thing about logic problems 
like this is that there are lots of different ways to look at them.  
No one way is "better" than another, so while my way works, you might 
be able to come up with a different but also completely valid way of 
doing the problem.  Thus, I don't want to say a whole lot more.  I 
suggest you think about the above observations for a bit and see if 
anything comes to you.  Just in case you need an extra boost, I'll 
just mention one more thing which you can look at now if you want or 
later, after you have thought about what I've said above. 

Think about your first question.  Without loss of generality, we can 
assume you will ask your first question of the person in the No.1 
position.  If the answer to the first question is yes, then we will 
know a certain amount of information, and if it is no, we will know a 
certain amount of information. Step back for a minute and don't worry 
about what question you will ask. Try to figure out what you would 
like the answers to be for the 6 different orderings, a through f.  
Suppose that for your first question, ordering a will give you a yes, 
ordering b will give you a yes, and ordering c will give you a yes, 
and ordering d will give you a no. Because K is in position No.1, we 
have no idea whether or not K will answer the first question with a 
yes or a no, right?  So, we can sum up this information by saying that 
if we get a yes answer, we know the group we are dealing with is in 
order a,b,c,e, or f. If we get a no answer, we know we are dealing 
with the group d,e, or f. Okay, so the point is we will, after the 
first question break the 6 orderings into 2 groups based on the 
response. Orderings e and f will always be in both groups, but 
depending on the question we ask, we can decide which of the two 
groups we want to put a,b,c, and d into. Thus, if we want to, we 
could probably find questions such that the answers would break the 
group into the following to groups: a,b,e,f for an answer of, say, 
yes, and c,d,e,f, for an answer of no.  

Okay, that was just an example.  Now you need to go back and look at 
the different orderings and see how you would like to break the groups 
up.  Keep in mind that if you can break them up in such a way that in 
place No.2 or place No.3 there can only be D's or G's that will help 
you because then you can ask your second question to person No.2 or 
No.3, respectively, and if you ask a question to which you already 
know the answer, you can figure out quite easily if you are dealing 
with G or D.  Once you know where either G or D is, you can ask G or D 
about the ordering of the seating and since you know G always tells 
the truth and D always lies, you will be done!  

So, I know this was rather long, and somewhat vague, but I didn't want 
to give away the solution to the problem that I came up with, both 
because you may come of with your own neat solution that is different 
and also because it is more fun to get things for yourself.  If you 
were confused by any of the smaller details of what I wrote above, 
don't worry - just think about the stuff that wasn't confusing or 
write back for clarification.  I'd love to hear how you do with the 
problem, so do feel free to write back to give your own answer or ask 
for more help.  I really had a good time working on this problem, so 
thanks very much for sending it in!  I hope that you, too,  enjoy 
working on it.  Good luck!   

See also the Classic Problem "Liars and Truthtellers" in the
Dr. Math FAQ: 
 
   http://mathforum.org/dr.math/faq/faq.liar.html   .

-Doctor Sydney,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 05/15/2000 at 02:35:35
From: Leif Terry
Subject: Your solution to The Truth-teller, the Liar, and Ambiguous

Hello,

I believe that your answer to the puzzle "The Truth-teller, the Liar, 
and Ambiguous" is incorrect in its assertion that there is, in fact, a 
solution.

You can ask only 3 yes/no questions, and that can only distinguish 
among 2^3 = 8 possibilities.

At first glance it appears that there are 3! = 6 possible states, one 
for each ordering of the truth-teller (T), liar (F), and random (R). 
These are: 

     TFR, TRF, FTR, FRT, RTF, RFT

However, R's answers may either be true (t) or false (f) (not 
necessarily with equal probability) and we don't know which. Thus there 
are actually 12 possible states that we have to distinguish among. 
These are:

     TFt, TFf, TtF, TfF, FTt, FTf, FtT, FfT, tTF, fTF, tFT, fFT

Since we can not possibly distinguish among these 12 states with 3 
yes/no queries, we can not find a line of questioning that will tell 
for certain who is who.

I find your site very entertaining and helpful but I think you goofed 
on this one.

Cheers,
Leif

Date: 05/15/2000 at 11:48:00
From: Doctor Rick
Subject: Re: Your solution to The Truth-teller, the Liar, and Ambiguous

Hi, Leif.

If you'll ignore your proof that the problem can't be solved, and make 
use of Doctor Sydney's hints, you'll find a solution in short order. I 
found his hints to be very helpful.

If you asked one question and got responses from all three individuals, 
the set of 3 answers would be one of the 12 possibilities you list. But 
you aren't asked to determine how each individual would answer a 
particular question. You are only asked to determine which is the 
truth-teller, which is the liar, and which is the random answerer. 
There are only 6 possible states, as Doctor Sydney enumerates.

If you follow Doctor Sydney's suggestions, after the first question you 
will have four possibilities left. Furthermore, you will know that one 
of the individuals can't be a random answerer, so you can make use of 
all the information you get from that point on. Two questions are then 
just enough to distinguish among the 4 possible states.

I'm glad you like our site. I hope you'll like it even more now that 
you know that we never goof! ;-) No, really, if you find another goof, 
let us know -- readers do catch real mistakes now and then, and we 
appreciate it.

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/   

Date: 05/16/2000 at 02:01:30
From: Leif Terry
Subject: Re: Your solution to The Truth-teller, the Liar, and Ambiguous

Hello again Dr. Math,

>If you'll ignore your proof that the problem can't be solved, and make 
>use of Doctor Sydney's hints, you'll find a solution in short order. I 
>found his hints to be very helpful.

I'd be more willing to ignore my "proof" if someone could point out the 
fallacy in it. I think it is very important for students to be able to 
figure out what can be solved and what can't. That way we can spend our 
time productively working on the unsolved problems instead of wasting 
time on the unsolvable (as amusing as the Bridges of Koenigsberg are).

I've read and re-read the hints, but I still don't see a solution. I'm 
entirely willing to be wrong on this one, but I must admit that I find 
your counter-arguments unsatisfying.

>If you asked one question and got responses from all three 
>individuals, the set of 3 answers would be one of the 12 possibilities 
>you list. But you aren't asked to determine how each individual would 
>answer a particular question. You are only asked to determine which is 
>the truth-teller, which is the liar, and which is the random answerer. 
>There are only 6 possible states, as Doctor Sydney enumerates.

I don't see what the distinction that you are trying to make is. If you 
find the random answerer you also know how he answered your question so 
you must know what state he is in. The only way to avoid this is to 
never ask the random answerer a question, which is impossible to 
guarantee.

>If you follow Doctor Sydney's suggestions, after the first question 
>you will have four possibilities left.

Yes, I can do that. Of course, I count 6 possibilities not four.

>Furthermore, you will know that one of the individuals can't be a 
>random answerer,

Yes, but one of them could be.

For example, we could ask the first person:

   1) Are you random?

If yes, then we are in one of the following 4 (6) states:

     FTR, FRT, RTF, RFT

If no then we are in one of these 4 (6):

     TFR, RTF, TRF, RFT

Suppose the outcome was "yes". What shall our next question be?

The best one I've found so far is:

   2) Are you random?

If yes then we have it narrowed down to two (2), FRT or RFT. In fact, 
since we know that T is the last one, we have a solution -- but only 
for this one case. We have *not* solved the puzzle.

If the answer to (2) was "no" then it could be either one of these 
three (4) states: FTR, RTF or FRT.

Obviously no matter how you count states we have hit a dead end here.

Here is further evidence that you need to include the random state of 
the Ambiguous into your count of possibilities:

Consider a simpler puzzle. You have two men, one of which is omniscient 
and always tells the truth. The other answers randomly. Determine who 
is who. Since there are only 2 [sic] states TR or RT, you only get 
*one* question to put to the man of your choice. This puzzle is not 
solvable as stated. The reason is obvious: R may answer either yes (y) 
or no (n) regardless of the question so there are really four possible 
states:

     Ty, Tn, yT, nT

This puzzle *is* solvable if you are given 2 questions, as you would 
expect.

I ask you to reconsider your posted "solution" to this problem. If you 
still believe me to be in error, then please point out the fallacy in 
my "proof" or send me your solution.

Regards,
Leif "Mathboy" Terry

Date: 05/16/2000 at 10:39:12
From: Doctor Rick
Subject: Re: Your solution to The Truth-teller, the Liar, and Ambiguous

Hi, Leif. I agree that an important element of problem solving is to do 
whatever you can do up front to determine whether the problem has a 
solution, and if so, what general characteristics the solution must 
have.

In advising you to ignore your "proof" of impossibility, I was not 
saying that you shouldn't use such reasoning. I was, in fact, applying 
the same principal to a new problem, namely, that of identifying the 
fallacy in your reasoning.

By solving the (original) problem first, we establish up front that 
there must indeed be a fallacy -- we're not on a wild goose chase. 
Furthermore, in solving the original problem, we may stumble on 
something that could help you to see where the fallacy lies. And I 
think we will!

With this in mind, let's start with my solution.

>There are three people in front of you. You know that:
>
>One of them is God. He knows everything, and always tells the truth.
>One of them is the Devil. He also knows everything, but lies. 
>The third person knows nothing, but answers questions as if he knows 
>the answers. His answers, however, are completely useless and could be 
>right or wrong.
>
>You can ask a total of three questions that can correctly be answered 
>with yes or no, each to one of the persons. You may choose whom to ask.
>
>Determine who is who...

Line up the three individuals, front to back, and number them #1, #2, 
and #3. I'll abbreviate as you do, T for truth-teller, L for liar, and 
R for random answerer.

(Question 1) Ask #1, "Is R immediately behind L?" If he answers yes, 
then either he is T and the order is TLR, or he is L and the order is 
LTR, or he is R and the order can be either RTL or RLT. Thus we have 
divided the 6 states like this:

     Q1 yes   Q1 no
     ------   -----
      TLR      TRL
      LTR      LRT
      RLT      RLT
      RTL      RTL

Notice that if the answer was yes, then #2 cannot be R. So (Q2y) ask 
#2, "Are you R?" If the answer is yes, you know this is a lie, so #2 
must be L. This leaves two possible states: TLR or RLT. To distinguish 
between these states, (Q3yy) ask #2, "Is #3 T?" You know he will lie, 
so an answer of yes means TLR, and an answer of no means RLT.

If the answer to Q2y was no, then you know this is the truth, and #2 
must be T, leaving two possible states: LTR or RTL. To distinguish 
between these states, (Q3yn) ask #2, "Is #3 L?" You know he will tell 
the truth, so an answer of yes means RTL, and an answer of no means 
LTR.

If the answer to Q1 was no, then #3 cannot be R (see the table above). 
You can follow exactly the same procedure as above, except that you 
switch #2 and #3. In summary, here is a flow chart of the questions you 
ask:

     (Q1) #1, Is R immediately behind L?
          Yes --> (Q2y) #2, Are you R?
                        Yes --> (Q3yy) #2, Is #3 T?
                                       Yes --> TLR
                                       No  --> RLT
                        No  --> (Q3yn) #2, Is #3 L?
                                       Yes --> RTL
                                       No  --> LTR
          No  --> (Q2n) #3, Are you R?
                        Yes --> (Q3ny) #3, Is #2 T?
                                       Yes --> TRL
                                       No  --> RTL
                        No  --> (Q3nn) #3, Is #2 L?
                                       Yes --> RLT
                                       No  --> LRT

After three questions, we know who is who. Does this solution work for 
you? The key was to ask a first question that gave me enough 
information to allow me to ask the second question of someone who was 
definitely not R. As Doctor Sydney suggested, I first wrote down the 
two sets of states that I wanted to distinguish by means of the first 
question. Then I hunted for a question that would have this result. 
Random selection of the first question is very unlikely to have a 
helpful result!

Here's why your simpler problem has no analogous solution: it takes at 
least two questions to make this method work. As long as it's possible 
that you're speaking to a random answerer (and this is possible on the 
first question), you can't distinguish R from either T or L. That first 
question, however, CAN give us real information about ANOTHER 
individual, as you see from the solution. We get this information by 
leveraging the information we already have, namely, that there is 
exactly one of each type. I admit this is counterintuitive; that's what 
makes the problem interesting.

Now that we have something concrete on the table, I'll take another 
shot at explaining why your state scenario doesn't apply. You say:

>However, R's answers may either be true (t) or false (f) (not 
>necessarily with equal probability) and we don't know which. Thus 
>there are actually 12 possible states that we have to distinguish 
>among. These are:
>
>     TFt, TFf, TtF, TfF, FTt, FTf, FtT, FfT, tTF, fTF, tFT, fFT

If we had to know how EACH individual answered a particular question 
(truthfully or falsely), then this list of states might be relevant. 
But if you examine the solution, you will see that only the first 
question is asked of someone who might be R, and it is asked of #1 
only. Thus the only possible states that arise in the course of the 
solution are:

     TFR, TRT, FTR, FRT, tTF, fTF, tFT, fFT

That's 8 states, exactly the right number to be distinguished by 3 
questions. This answers your comment:

>I don't see what the distinction that you are trying to make is. If 
>you find the random answerer you also know how he answered your 
>question so you must know what state he is in. The only way to avoid 
>this is to never ask the random answerer a question, which is 
>impossible to guarantee.

We do indeed avoid asking the random answerer a question, if he is #2 
or #3.

Have we resolved the problem yet? I understand your desire to see 
exactly what was wrong with your argument, in order to avoid making 
similar mistakes in the future. In problems like this, I often doubt my 
initial general conclusions, because I suspect I may be missing some 
possibility, just as you did in this problem. I wish I could tell you 
what to do, but all I can say is "don't be too sure too soon!"

- Doctor Rick, The Math Forum
  http:// mathforum.org /dr.math/   

Date: 05/17/2000 at 03:30:38
From: Leif Terry
Subject: Re: Your solution to The Truth-teller, the Liar, and Ambiguous

Hello again Dr. Math,

Thank you for patiently explaining the solution to that problem to me. 
I understand it now. No small part of my difficulty came from assuming 
that each person had to be asked a question.

It certainly is a devilish problem. I doubt I could have solved it the 
way it was intended but perhaps I would have been less sure of its 
impossibility.

Thank you for your help,
-Leif