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$ is a liar or not. What is the minimum number of questions needed to reliably identify at least one truth-teller?
I was asked to try to solve this problem on logic. Unfortunately, this is way above my level and I couldn't even attempt solving it. Would somebody please guide me on how to solve this problem? Thank you very much in advance.
For a simpler problem, if there are $n>1$ people with only $1$ truth-teller, then the liars can simply lie all the time. In that case, it is not possible to tell which one is a truth-teller. I am not sure how to approach the problem when there are more than $1$ truth-teller.
Best Answer
You can also do the following. Let us call "a truth chain" a sequence of people $A_1,\dots, A_m$ such that $A_i$ says that $A_{i+1}$ is a truth teller for all $i=1,\dots,m-1$. Suppose we have at most $\ell$ liars and more than $\ell$ truth tellers. We can start building the truth chain asking the last member of the chain about somebody not in the chain yet. If he says "a liar", we remove the last member of the chain and the person we asked him about, thus reducing the chain size by $1$ and the number of liars by at least $1$. If he says "truth teller", we extend the chain. Once the length of the chain exceeds the available number of liars, the last member of the chain is a truth teller. If the upper bound for the number of liars drops to $0$, we just pick anybody left. For $\ell$ liars this algorithm gives $2\ell-1$ questions, so the upper bound in the original problem drops to $53$. @Batominovski presumably showed that it is the minimum even if the liars are obliged to lie (though it is too late here to figure out which one of us is 1 unit off).