6

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

mnaoumov
  • 221
  • 1
  • 9
  • 2
    can you whisper the question to their ears? (meaning the rest would not hear your question) – Oray Feb 03 '17 at 08:57
  • @boboquack & Oray Thanks for your questions, I've updated the topic with replies – mnaoumov Feb 03 '17 at 09:01
  • 1
    Also are we assuming that the likelihood of the random people saying yes/no is 50/50? – DeepPurple Feb 03 '17 at 09:11
  • 1
    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 03 '17 at 09:12
  • 2
    @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 03 '17 at 09:24
  • 1
    What's the solution with 25 questions? – mowwwalker Feb 03 '17 at 09:35
  • 1
    @DeepPurple it doesn't matter the likelihood as we need to build a 100% guarantee strategy in the worst case scenario where random answerers do their best to confuse you – mnaoumov Feb 03 '17 at 09:42
  • @EspeciallyLime, I know at least two people who have a strategy for less than 25 questions – mnaoumov Feb 03 '17 at 09:43
  • @mowwwalker Updated my question to include strategy for 25 – mnaoumov Feb 03 '17 at 09:44
  • 1
    i think i found better answer, gonna post after gym. (considering questions are not heard from others than answerer) – Oray Feb 03 '17 at 09:56
  • 1
    all of them could be truthtellers? or at least one of them is randomanswerer? – Oray Feb 03 '17 at 10:18
  • @Oray all of them could be truth-tellers. But if you have strategy that requires random answerer, please share it as well – mnaoumov Feb 03 '17 at 11:42
  • 3
    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 03 '17 at 15:54
  • 1
    Pull one person to one side to be your buddy and assume that you still have at least 12 truth tellers out of 26 people.

    Split them into two even groups and ask your buddy whether group A has more truth tellers than group B. Now stab your buddy to prove a point and to serve as a warning. Ask the remaining tellers to present to you a truth teller, on the understanding that if they lie, disagree or say "yes" or "no", they'll be stabbed.

    – Brent Hackers Feb 03 '17 at 16:13
  • 1
    you need to elaborate on your N=1 proof. I was able to convince myself of it, but it's not obvious and it deserves a sentence or two clarifying. – Kate Gregory Feb 03 '17 at 17:41
  • @Brent Hackers, nice trick but not truly logical :) – mnaoumov Feb 03 '17 at 18:21
  • @Kate Gregory, thanks, I've added a better explanation for N=1 – mnaoumov Feb 03 '17 at 19:10
  • @supercat, thanks for the advice. I replaced 'random answerer' with 'trickster' – mnaoumov Feb 03 '17 at 19:18
  • I couldn't understand your 25 question strategy . But here is a 25 question strategy that I understood : https://math.stackexchange.com/a/3034816/645672 – Hemant Agarwal Jun 27 '22 at 21:54

1 Answers1

6

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

mnaoumov
  • 221
  • 1
  • 9