A Knight and Knave Problem

Question

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.

Answer 1

NOTE: I did not realize that the liars in the OP's definition can both tell the truth and lie. This solution assumes that liars always lie.

Associate a truth-teller with the boolean value $0$ and a liar with the boolean value $1$. Let $+$ be the exclusive disjunction (i.e., $0+0=0$, $0+1=1$, $1+0=1$, and $1+1=0$). For a person $P$, let $f(P)$ be the boolean associated to $P$. Hence, for two persons $A$ and $B$, if you ask $A$ whether $B$ is a liar, then $A$ would say $B$ is not a liar if $f(A)+f(B)=0$, and $A$ would say otherwise if $f(A)+f(B)=1$.

Pick a person $X$. Ask $X$ about $54$ other persons. You would be able to find out which persons among these $54$ are of the same type as $X$ (i.e., those $Y$'s such that $f(X)+f(Y)=0$, or equivalently $f(X)=f(Y)$). If at least $27$ of them are of the same type as $X$, then $X$ must be a truth-teller (as there are only $27$ liars, and the group of people like $X$ contains at least $27+1$ members). If not, then at least $28$ of these guys are of different type from $X$ (i.e., those $Y$'s with $f(X)+f(Y)=1$), which means that they are truth-tellers. Hence, the task can be done with at most $54$ questionings.

I claim that this is the minimum possible number of questions for this task to always be successfully accomplished. There is some faulty reasoning in the hidden portion below. I hope to fix it soon.

Suppose that there is a way to ask people around with less than $54$ questions. Now, consider a graph $G(V,E)$, where the vertex set $V$ is the set of all the people in the room and the edge set $E$ where an edge is drawn between two people if and only if one is questioned about the other. We have $|E|\leq 53$. Note that the questionings only tell us information on each connected component of $G$, and we can only complete the task if there is a connected component in which there are at least $28$ vertices of the same type. However, a largest connected component of $G$ has at most $|E|+1\leq 54$ vertices, and therefore, it is possible to reassign people so that this connected component will have at most $27$ people from each type. Knowing anything about other connected components won't contribute any more information.
More generally, if there are $m$ truth-tellers and $n$ liars with $m \neq n$, then the minimum number of questionings that the task can always be accomplished is $2\min\{m,n\}$. You have no hope if $m=n$.

Answer 2

This answer is a proposition for a partial answer if you suppose that liars can tell the truth.

Fix $A$ in the population.

If you ask $2 \times 27 + 1 = 55$ people that you select randomly (not $A$), you can make them "vote" to say if $A$ is a liar or if he tells the truth. If A tells the truth you've found one.

Otherwise, $A$ is a liar so you know there are at most $26$ liars in your "voting team", so you can chose only $53$ voters among them.

Then make them vote to determine if another persone $B$ is a liar or not, and so on.

If you're unlucky, you'll spot the $27$ liars before finding a truth-teller.