[bushindo]

Suppose that you encounter 6 people, each of whom is either a truth teller (always tells the truth), a liar (always tell lies), or a random answerer (always answer randomly with 'Yes' or 'No'). You know that in this group of 6, there are 3 random answerers, 1 truth teller, and 2 liars, but you don't know which person is which. The puzzle is to identify the 3 random answerers with the following information:

1) You can only ask yes/no questions to 1 person at a time

2) You can ask the same question of different people, or address different questions to the same person.

3) Everytime you ask a question, your question count increases by 1

4) Each person in the group of 6 knows what type of people the remaining 5 are.

So, determine a strategy that is guaranteed to identify the 3 random answerers. Bonus: what is the maximum number of questions required to guarantee correct identification?

Edited November 22, 2010 by bushindo

[Guest]

Hypothetically, if a question is asked of the truth teller with an answer he cannot possibly determine accurately (e.g. "If asking a yes or no question of a random answerer, will his/her answer be correct"), does the truth teller's head explode?

[bushindo]

Hypothetically, if a question is asked of the truth teller with an answer he cannot possibly determine accurately (e.g. "If asking a yes or no question of a random answerer, will his/her answer be correct"), does the truth teller's head explode?

Yes, if that happens, the truth teller's head will explode. Actually, more seriously, I just realized that I made a mistake in constructing this puzzle. Turns out in the worst case I can narrow the ₆C₃ = 20 possible configurations down to 2, but no further. Therefore a solution is not possible, at least not for me. If a mod can delete this topic, I'd appreciate it very much. Sorry to those who spent time thinking about the problem as it was posted.

[araver]

Yes, if that happens, the truth teller's head will explode. Actually, more seriously, I just realized that I made a mistake in constructing this puzzle. Turns out in the worst case I can narrow the ₆C₃ = 20 possible configurations down to 2, but no further. Therefore a solution is not possible, at least not for me. If a mod can delete this topic, I'd appreciate it very much. Sorry to those who spent time thinking about the problem as it was posted.

Allowing for non-answers (head exploding)

can give a 5-question strategy.

Simply ask 5 men the same question: "Would you answer 'yes' to the question of whether you would answer 'no' to this question?". This question blocks both liars and truth-tellers. Random answerers can answer.

After 5 questions you get either 2 or 3 answers identifying 2 or 3 random answerers. The last person is a random answerer if and only if you got 2 answers so far.

Seriously now

There are 60 possible R, R, R, T, L, L combinations with 20 unique combinations of 3 R's (since we don't care where the truth-teller lies).

Theoretically, 20 combinations can be distinguished in 5 questions (which provide 2^5=32 possible cases).

I too was not able to find an adaptive strategy that actually works in all cases. Mostly because of the symmetry (half of the people are R's)

But I cannot formally prove the fact that such a strategy does not exist. Yet.

Still not sure we need to delete this as we do not have a formal proof that it's impossible.

I propose we leave it as an open question for now or as "Bushindo's 3-Randoms-Hiding-Successfully Conjecture"

Edited November 23, 2010 by araver

[araver]

Actually, after thinking a little more ... I almost had a proof but it had a hidden fallacy in it. Just putting it here maybe it inspires an actual proof.

First, the distinction between liars and truthtellers is irrelevant. A well-known technique (when dealing with truthtellers/liars alone) if you want to see if a statement P is true or not is to ask another question instead:

Q:"If I would ask you if P is true would you answer Yes?".

If P is true: a liar answers No to P therefore answering Yes to Q. a truthteller answers Yes to both P and Q.

If P is false: a liar answers Yes to P therefore answering No to Q. a truthteller answers No to both P and Q.

So P is true if and only if you get an Yes answer to Q.

So if the problem with N randoms and N truthtellers can be solved then the problem with N Randoms and N liars/truthtellers can be solved by adapting a strategy.

To follow a consistent notation I would propose (Truthtellers, Liars, Randoms)-instance of the problem of finding the randoms.

The above reads "If (N,0,N) is solvable then (X,N-X,N) is solvable where 0<=X<=N"

Simplest instance of the second problem is 1 random and 1 truth teller.

And that's unsolvable. I think I have a proof in 3 steps.

Step 1 (General reasoning)

Assume you have a M question strategy that succeeds. Then there is a minimal strategy derived from this strategy in which all questions are helpful i.e. give information about the distribution of the people.

A constructive proof is to simply prune-off the un-necessary questions.

Step 2 (Particular reasoning)

If a successful minimal strategy exists to (1,1) problem then it has 1 question.

Assume the first helpful question asks about the truth value of P. And learning the truth value of P says something about the distribution.

Note that there's actually no fractional information that can be gained about the distribution. Either you find it or not since there are only 2 possibilities.

Step 3 (Particular reasoning continued)

There is no 1-question strategy

Assume there is such a 1-question strategy. Then the answer to the question Yes/No maps unequivocally to the two possible distribution (R,T) and (T,R) where the first is the one you ask the question to and the second is, well, the other one. Only two such mappings exist.

Assume one mapping Yes means R-T and No means T-R. Basically, this means that Random's always answer Yes to the question which is absurd since they answer randomly.

Along these lines, I think that a proof that (N,0,N) is not solvable can be constructed, using the symmetry (2N people, N randoms).

However, this would not help.

The fallacy is that the argument "If (N,0,N) is solvable then (X,N-X,N) is solvable where 0<=X<=N" does not say anything about (X,N-X,N) if (N,0,N) is not solvable. We would need the other implication in order to derive a meaningful result.

I have yet to come up with a proof of this statement "If (X,N-X,N) is solvable for some 0<=X<=N is solvable then (N,0,N) is solvable" which would actually help.

OFF-TOPIC I admit I still enjoy this puzzle as I'm a twisted-version of a researcher

I enjoy mostly proving that something is either not possible or undecidable

Edited November 23, 2010 by araver

[araver]

And since I started ranting, let me continue with

a proof that (N,0,N) is not solvable (always) because of the symmetry.

For every (N,0,N) instance (N truthtellers, 0 liars and N randoms) there are a number of possible arrangements.

This number is always even, since for each arrangement there is a mirror arrangement where truth-tellers take the place of randoms and viceversa.

And no arrangement is it's own mirror.

E.g. mirror(TRRT)=RTTR, mirror(TR)=RT.

Note that this mirror argument (the mirror of an arrangement is an arrangement of the same type of instance) only works for (N,0,N)-instances.

Assume that a successful interrogation strategy exists for the (N,0,N)-instance. Let M be maximum number of questions this strategy needs in the worst-case scenario. This means that in at most M number of questions, one can tell who the randoms are, independent of the random answerers' answers/strategy/randomness.

Assume the following infinite-strategy: "I will act as if I am the truth-teller standing on the same position in the mirror-universe".

I'll call this type of person Infinite-Look-Alike.

He is neither Random (since he's predictable), he is neither Truth-teller.

One might ask if he is a perpetual liar, but this is not relevant to the proof. Actually he lies only about the arrangement and tells the truth otherwise i.e. a Perfect-Liar - choose a lie and stick with it without contradicting known facts

Now, since random answerers are truly random, there's no certain way to distinguish them from an Infinite-Look-Alike in a finite number of questions. A random guy (by himself) can act like the Infinite-Look-Alike indefinitely.

In all the possibilities of M consecutive random answers, for any number M, there is a possibility where all random answerers act like Infinite-Look-Alikes (for the first M questions directed at them).

Which means there is a possibility that they act like Infinite-Look-Alikes for the entire successful interrogation strategy.

The problem is, that in that mirror universe, the mirror-truth tellers act like Infinite-Look-Alikes, and mirror-Randoms act like truth-tellers.

In these circumstances, that ideal-interrogation strategy, applied in the mirror universe, gives the exact opposite result - failing.

So, (N,0,N) is not solvable.

Edited November 23, 2010 by araver

[Guest]

I am just going to go for the Bonus question.

Since you are asking for the maximum and not the minimum, then my answer would be "Infinite number of questions"! (or just a number higher than the number anyone comes up with)

[wolfgang]

Hi...did anyone think about deviding the 6 people into two groups of 3?

In this case we will have only three possiblities:-

1- RRR......TLL

2- RRL......TLR

3- RLL......TRR

This method may help to find a possible solution,and minimize number of questions..

[bushindo]

And since I started ranting, let me continue with

a proof that (N,0,N) is not solvable (always) because of the symmetry.

For every (N,0,N) instance (N truthtellers, 0 liars and N randoms) there are a number of possible arrangements.

This number is always even, since for each arrangement there is a mirror arrangement where truth-tellers take the place of randoms and viceversa.

And no arrangement is it's own mirror.

E.g. mirror(TRRT)=RTTR, mirror(TR)=RT.

Note that this mirror argument (the mirror of an arrangement is an arrangement of the same type of instance) only works for (N,0,N)-instances.

Assume that a successful interrogation strategy exists for the (N,0,N)-instance. Let M be maximum number of questions this strategy needs in the worst-case scenario. This means that in at most M number of questions, one can tell who the randoms are, independent of the random answerers' answers/strategy/randomness.

Assume the following infinite-strategy: "I will act as if I am the truth-teller standing on the same position in the mirror-universe".

I'll call this type of person Infinite-Look-Alike.

He is neither Random (since he's predictable), he is neither Truth-teller.

One might ask if he is a perpetual liar, but this is not relevant to the proof. Actually he lies only about the arrangement and tells the truth otherwise i.e. a Perfect-Liar - choose a lie and stick with it without contradicting known facts

Now, since random answerers are truly random, there's no certain way to distinguish them from an Infinite-Look-Alike in a finite number of questions. A random guy (by himself) can act like the Infinite-Look-Alike indefinitely.

In all the possibilities of M consecutive random answers, for any number M, there is a possibility where all random answerers act like Infinite-Look-Alikes (for the first M questions directed at them).

Which means there is a possibility that they act like Infinite-Look-Alikes for the entire successful interrogation strategy.

The problem is, that in that mirror universe, the mirror-truth tellers act like Infinite-Look-Alikes, and mirror-Randoms act like truth-tellers.

In these circumstances, that ideal-interrogation strategy, applied in the mirror universe, gives the exact opposite result - failing.

So, (N,0,N) is not solvable.

Good work, araver. You made some valuable contribution from an otherwise flawed puzzle. I'm glad you enjoyed it. I sure enjoy reading your proof.

Hi...did anyone think about deviding the 6 people into two groups of 3?

In this case we will have only three possiblities:-

1- RRR......TLL

2- RRL......TLR

3- RLL......TRR

This method may help to find a possible solution,and minimize number of questions..

This is a good start, but it is virtually impossible to distinguish between mirror pairs. Suppose we narrow the problem to either possibility 2 or 3 in your example, it is virtually impossible to determine which is the correct one from there.

Edited November 23, 2010 by bushindo