# Identify truth-teller amongst tricksters

There are 27 people. At least half of them are truth-tellers, others are tricksters. Tricksters can answer yes/no regardless of your question. But we should ask them such questions that truth-tellers can answer as well. I would also assume that tricksters also are trying to hide the fact they are tricksters. So if you ask 'are a you a truth-teller' any of them would answer 'yes'.

All of the people know who all the others are (trickster or truth-teller).

We can ask any of them any yes/no questions. You can assume the questions you are asking are not heard by other people.

We need to identify at least one of the truth-tellers using minimum questions.

I have a strategy for 25 questions but there is a better strategy that I am looking for. Ideally I would like to find an optimal amount of questions with a proof that it is not possible to solve the puzzle with less questions. But for now I am looking at least for strategy with less than 25 questions.

My strategy for 25 questions:

Prove by induction that if we have 2N+1 people with at most N tricksters, we have a strategy with 2N-1 questions.
Base N=1. We have 3 people with at most 1 trickster. We ask person #1 'Is person #2 a truth-teller?'. If answer is 'yes' - person #2 is a truth-teller, if 'no' - person #3 is a truth-teller. We solved it with 2N-1=1 questions. Let's see why this strategy works. If #1 is a trickster and as we know there are at most 1 trickster, #2 and #3 are truth-tellers so our strategy works. If #1 is truth-teller and said 'yes' - #2 is a truth-teller, our strategy works! If #1 is truth-teller and said 'no' - #2 is a trickster, so #3 is a truth-teller, our strategy works!
Now, assuming we proved the statement for N, consider N+1
We have 2N+3 people with at most N+1 tricksterstricksters. We need to prove that we have a strategy with 2N+1 questions.
We ask person #1 'Is person #(2N+3) a truth-teller?'.
a) If answer is 'no', then definitely either #1 or #(2N+3) is a trickster (or both). So we exclude them and we have 2N+1 people (#2,...,#(2N+2)) with at most N tricksters. We already used one question and by induction we will need 2N-1 questions to identify a truth-teller. So in total we used 1+(2N-1)=2N<2N+1 questions
If we got N+1 'yes' answers, then person #(2N+3) truly is a truth-teller, because only N+1 people could potentially lie. We used N+1 answers N+1<2N+1
c) If we got #1, ..., #k replied 'yes' and #(k+1) replied 'no', k<=N, it means, either #k or #(k+1) is a trickster. Exclude both of them from consideration. We have 2N+1 people with at most N tricksters. We already used k+1 questions, but first k-1 are exactly the same we would ask if we have those people (1,2,...,k-2,k-1,k+2,...,2N+3) from the very beginning. So actually only two questions should be thrown away. By induction, we will need 2N-1 questions. Adding those two thrown away, we will get 2+(2N-1)=2N+1
QED
In our case N=13, 27=2N+1 and we need 2N-1=25 questions!

What is the optimal strategy?

UPD: I found a related puzzle, but there is required to find all truth-tellers. In our puzzle we need to find only one. Knights and jokers

• can you whisper the question to their ears? (meaning the rest would not hear your question) – Oray Feb 3 '17 at 8:57
• Also are we assuming that the likelihood of the random people saying yes/no is 50/50? – DeepPurple Feb 3 '17 at 9:11
• Do you know that the better strategy exists? I can see how to do it with 25 questions, so would I be wasting my time trying to prove that is optimal? – Especially Lime Feb 3 '17 at 9:12
• @DeepPurple, does it really matter? A 99/1 random chance can still behave like a 50/50 or a 25/75 or a 0/100 chance in any case. – boboquack Feb 3 '17 at 9:24
• If you want to use the term "random answerer", I would suggest that you stipulate (1) a solution must have a 0% chance of failure, and (2) truth-tellers know the identity of all truth-tellers, but may arbitrarily answer yes or no to any question which is ambiguous or to which they do not know the answer. Alternatively, have truth-tellers and "schemers" who will answer in most vexatious way possible. – supercat Feb 3 '17 at 15:54

I found a strategy using

23 questions

Moreover if we restrict questions to something like 'Is person X a truth-teller?' then there is a proof that there is no a better strategy. It is too verbose to write it here, so follow http://www.sciencedirect.com/science/article/pii/S0166218X03001860/pdfft?md5=9cdb8311bfe6ae1512d65b2b9cd1d625&pid=1-s2.0-S0166218X03001860-main.pdf for more details

The strategy is the following

Form groups of people. Each group will have a leader.
Moreover form a special group for losers
Initially we have 27 groups with one person. Losers group is empty
Then establish the following process: take two groups with the same amount of people and ask leader of one group (A) is the leader of group (B) a truth-teller
a) if reply is 'yes', then we join that groups into a new one and make B its leader
b) if reply is 'no', throw both groups into losers group

Process stops when we don't have two groups with the same amount of of people (*) or each people came into losers group (**)

Note some properties
1) Each group (except losers) have $2^k$ people for some k. There was $2^k-1$ questions to form such group
2) If group's leader is a trickster, everyone in this group are tricksters. To see that, note that from every member of the group this is a 'yes' chain to the leader. And 'yes' answer about trickster may give only another trickster
3) If answer 'no' was given, either leader A or B is trickster. From 2) his whole group are tricksters so their union have at least half of tricksters
4) From 3), losers group have at least half tricksters
5) From 4), (**) is impossible
6) When two groups of site $2^{k-1}$ are moved into losers group, it gains $2^k$ people, and there were used $2^k-1$ questions for them
7) All groups except losers have more than half of truth-tellers

Process stopped with (*) so we've got groups with the following amount of people:
$2^{a_1}, 2^{a_2}, ..., 2^{a_m}, a_1>a_2>...>a_m\ge0$
Loser group have: $2^{b_1}+2^{b_2}+...+2^{b_n}, b_i\ge1$

Note that, $2^{a_2}+...+2^{a_m}<2^{a_1}$. Therefore the group with $2^{a_1}$ people has more than a half of people out of losers group. From 7), it has at least one truth-teller. From 2) its leader is a truth-teller. We choose him as an answer
Finally, let's count a required amount of questions to form such groups
$Q=(2^{a_1}-1)+(2^{a_2}-1)+...+(2^{a_m}-1)+(2^{b_1}-1)+...+(2^{b_n}-1)=(2^{a_1}+2^{a_2}+...+2^{a_m}+2^{b_1}+...+2^{b_n})-(m+n)$
From the other hand, that big sum in parentheses is exactly 27 people
Q=27-(m+n)
m+n is a amount of summands of powers of 2 that have total 27
Expansion 27=16+8+2+1, so it's impossible to expand with less than 4 summands
Q<=27-4=23

UPD: I was asked to show an example how the strategy works for 5 people with at least 3 truth-tellers.

5=4+1, so 5 expands into not less than 2 summands that are powers of 2. So there will be a solution with 5-2=3 questions.
Initially we have groups (1), (2), (3), (4), (5) and empty losers group []. Let's make mark last person in a group as a leader.
1) Ask #1 is #2 a truth-teller. If 'yes' - form a group (1,2). If 'no' move [1, 2] into losers. At least of them is trickster
2) Ask #3 about #4. If 'yes' - form a group (3,4). If 'no' move [3, 4] into losers. At least of them is trickster
3) After 1) and 2) there are three possibilities
a) Both answers were 'yes', So we have group (1,2), (3,4), (5). Ask #2 about #4. If 'yes' - we've got (1,2,3,4), (5). And 4 is a truth-teller. He cannot be a trickster, because otherwise all (1,2,3,4) are tricksters, which is impossible.
If 'no' - either #2 or #4 are tricksters so either (1,2) or (3,4) are tricksters. Move [1,2,3,4] into losers group and all tricksters sit there and 5 is a truth-teller
b) One answer was 'yes'. So we have group, say (1,2), (5) and [3,4]. So 2 is a truth-teller. We don't need to ask 3rd question
c) Both answers were 'no'. So we have only (5) and [1,2,3,4]. So 5 is a truth-teller

• @Oray, the example was too long for the comment, so I've added the example into answer itself – mnaoumov Feb 5 '17 at 22:24