Puzzle to find one good person [duplicate]

Question

There are 15 people who may lie or say the truth(bad people) and 16 people who will always say the truth(good) . Suppose A- bad person , B-good person and C-bad person, when asked about A, B will say that A is a bad person(truth), when asked C about A, it may lie or say the truth. How can we find atleast one good person from the lot.

Answer 1

Ask "Is [this person] a good person?" until you get 16 people to reply "Yes" for a particular person. Since there are only 15 bad people, even if they all coordinate together to try and say that a bad person is a good person, it's not enough to fool you, and all the good people would reply "No". Conversely, all 16 good people would reply "Yes" if you asked about a good person, whereas the bad people could only at best reply with 15 "No" answers.

Answer 2

I'm not sure if this is optimal

Take $16$ of them and split them into $2$ groups of size $8$, $A$ and $B$
- there will be at least $1$ truth-teller amongst the $16$

Ask all $31$ in turn, "Is the number of truth-tellers in $A$ greater than the number of truth-tellers in $B$?".
until you have $16$ agreeing answers, at which point you know this is the truth.

"Yes" identifies $A;$ "No" identifies $B$
(when equal $B$ is identified, but $B$ will still contain at least $1$ truth-teller)

Split the identified group into $2$ again and repeat, until you have identified a group of size $1$

The worst case is that you ask a truth-teller last in every round and the others all lie at every opportunity, $4\times31=124$ questions.

Alternatively, if we are not limited to "yes" or "no" questions

Label each person $1,2,3,4,\cdots,31$

Ask all $31$ in turn, "Please list all the truth-tellers, including yourself if you are one, by label"

Once you have $16$ responses identifying the same set you have found all your truth-tellers.

Answer 3

The accepted answer to the "Knights and Jokers" question of which this is almost a duplicate guarantees to identify everyone in at most $31+15-1=45$ questions.

The accepted answer to the "Faulty computers" question of which this is almost a duplicate claims, assuming it translates in the obvious way, to guarantee to identify one good person (= working computer) in at most $31-2=29$ questions. I say "claims to" simply because it references an answer to the "Knights and Jokers" question which (1) was not optimal and (2) is alleged in a comment to be incorrect.

... OK, having looked at that second accepted answer, it looks OK to me and doesn't depend on the difference between 16+15 here and 50+49 there. To summarize: we are going to build a chain of people, each of whom vouches for the next and containing more good people than bad. In particular there is at least one good person in the chain. Everyone after a good person in the chain must also be good, so in particular the last person in the chain is good. Here's how we do it: start with an empty chain and a "candidate pool" containing everyone. Now repeat the following. Take the last person in the current chain, or anyone at all if the current chain is empty. Ask them about someone from the candidate pool. If they say "good", put that person on the end of the chain. If they say "bad", remove that person from the candidate pool and the person who said "bad" from the end of the chain. Note that at least one of the people you have removed is bad, so there remain more good people than bad after the removal. Eventually you will run out of candidates, so everyone you haven't removed is in the chain. Done.

How many questions does that require us to ask? The first question that creates a non-empty chain adds 2 to the chain. Other than that, every question either adds 1 to the chain or subtracts 1 from the chain and 2 from the total number of people uneliminated; hence every question reduces (#uneliminated - #chain) by exactly 1; at the start this figure is the total number of people, and at the end all the uneliminated people are in the chain so it's zero. So on the face of it this requires (#people-1) questions. BUT there's an optimization available: as soon as there are more people in the chain than out of it, we can stop because there has to be at least one good person in the chain; in particular, if ever there is only one person out of the chain, we're done. (What if the chain is empty? Then, because there are always more good people than bad, that one person is known to be good.) So we never need more than (#people-2) questions.

OK. Now, really the only thing missing here is that we haven't proved this optimal. So suppose we have $n$ bad people and $n+1$ good people, and we start asking questions "person $i$, is person $j$ good?" and every answer is no. A "no" answer tells you precisely that either $i$ or $j$ is bad, so what we have is: $N=2n+1$ people, just over half of whom are good, and $N-3$ facts of the form "these two people are not both good". Perhaps this cannot be enough to definitely identify a single good person.

That would mean that for each of the $2n+1$ people, we can delete that person from the list and still find a way of marking $n+1$ as good and not violating any of our $2n-2$ facts. That will be true if every graph with $2n$ vertices and $2n-2$ edges has an independent set of size at least $n+1$. The usual lower bound on independent set size comes from Turan's theorem but I think that isn't sharp when, as here, the number of edges is very small. I haven't yet found a proof (or disproof) of the bound we need in this case, but I haven't tried terribly hard.