Finding a Truth-Teller
There are 69 people in a room, of which 42 are truth-tellers (they always tell the truth) and the rest are liars (they can lie
or
tell the truth).
You are allowed to ask any person A whether any person B (other than person A) is a liar or not. What is the minimum number of questions needed to ensure that you can correctly identify at least one truth-teller?
The answer is 53.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Hi, I have a solution that gives a minimum number questions of 53, which is less than the answer given of 106.
I list the people in some order p1 to p69, (max number of liars L=27). I get the first pair A(the one being asked a question)=p1 and B(the one being asked about)=p2. I ask of A whether B is a liar. If "no", then I continue with the next pair, (Ask p2 about p3, then p3 about p4...) until I get a "yes". If "yes", at least one of the pair involved are lying, and I remove both of them from my list, reduce the max number of liars by 1, and continue with the next available pair (e.g. If I remove p6&p7 then I may continue with p5&p8 if p5 is still in the list). This is so I get a chain of "no" answers of length N, involving N pairs and N+1 people.
If, after a "no", N+1 becomes greater than L, there must be at least 1 truth-teller in the chain. This person, and all the people after him in the chain, must be truth-tellers. Therefore the last person in the chain can always be identified as a truth-teller. If, after a "yes", L becomes zero, then the rest of the people in the list must all be truth-tellers.
Let's use induction to count the number of questions needed.
Say that for a group of L liars, and L+1 or more truth-tellers, we need Q(L) questions. We need at least L+1 or more truth tellers in case where we have L "yes"es in a row, so somebody is left in the list to be identified as a truth-teller.
For a group of L+1 liars and L+2 or more truth-tellers, we would reduce the problem to a group of L or L-1 liars after the first "yes". If the first question is a "yes", we would need a total of Q(L)+1 questions. If we get "no" then "yes", we would need a total of Q(L)+2 questions. If we get N "no" then "yes", it seems we would need a total of Q(L)+1+N questions. However, we already know the answer to the first N-1 questions once we reduce the problem to a group of L liars, so the real total would still be Q(L)+2 questions. We can also solve the problem by getting L+1 straight "no"s. So the minimum number of questions for L+1 liars is max(Q(L)+2, L+1).
For a group of 1 liar and 2 or more truth-tellers. L=1. We only need one question. Q(1)=1. If "yes" then L gets reduced to 0 and the remaining people p3,p4,... are truth-tellers. If "no" then N+1 = 2 becomes greater than L and p2 is definitely a truth-teller.
We can induce that Q(L) = 2L - 1 from: Q(1)=1. Q(L+1) = max(2L-1+2, L+1) = 2L + 1 = 2(L+1) - 1 for L>=1.
Finally, Q(27)=27*2 - 1 = 53.
It is much more difficult to prove that it cannot be done in less than 53 questions.