Associated Topics || Dr. Math Home || Search Dr. Math

### 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
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

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:

rule for asking three questions might be something like the following:

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

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

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
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!

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

>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
you must know what state he is in. The only way to avoid this is 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

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

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!

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

(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

(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

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

>I don't see what the distinction that you are trying to make is. If
>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

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.

-Leif
```
Associated Topics:
College Logic
High School Logic

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search