6
$\begingroup$

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
b) If answer is 'yes', we keep asking other people the same question about #(N+1).
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

$\endgroup$
  • 2
    $\begingroup$ can you whisper the question to their ears? (meaning the rest would not hear your question) $\endgroup$ – Oray Feb 3 '17 at 8:57
  • 1
    $\begingroup$ Also are we assuming that the likelihood of the random people saying yes/no is 50/50? $\endgroup$ – DeepPurple Feb 3 '17 at 9:11
  • 1
    $\begingroup$ 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? $\endgroup$ – Especially Lime Feb 3 '17 at 9:12
  • 2
    $\begingroup$ @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. $\endgroup$ – boboquack Feb 3 '17 at 9:24
  • 3
    $\begingroup$ 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. $\endgroup$ – supercat Feb 3 '17 at 15:54
6
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.