A Knight and Knave Problem

Solution 1:

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).

Solution 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.

Solution 3:

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$.

Solution 4:

Let $q$ be the minimal number of questions needed to reliably identify at least one truth-teller. An algorithm from hHhh’s answer provides a bound $$q\le 55+53+\dots 3=-1+\sum_{k=1}^{28} 2k-1=-1+28^2=783.$$

We can improve it to $q\le 405$ as follows. Assume that we have $n$ persons in a room and at most $1\le l<n/2$ of them are liars. Pick arbitrary distinct persons $A_1$ and $A_2$ in the room and ask $A_2$ whether $A_1$ is a liar. If the answer is “yes” then at least one among $A_1$ and $A_2$ is a liar and we remove both of them from the room (because we don’t like liars :-) ) If the answer is “no” then we pick an arbitrary person $A_3$ distinct both from $A_1$ and $A_2$ and ask $A_3$ whether $A_2$ is a liar. If the answer is “yes” then at least one among $A_1$ and $A_2$ is a liar and we remove both of them from the room. If the answer is “no” then we pick an arbitrary person $A_4$ distinct from $A_1$, $A_2$ and $A_3$ and so on. If $A_{l+1}$’s answer was “yes” then $A_1$ is a truth-teller, because otherwise all $A_i$, with $i=1,\dots,l+1$ are liars, which is impossible. So after at most $l+1$ questions we either can reliably identify a truth-teller or remove from the room two people with at least one liar among them. When we have removed these two people from the room, we start to ask the questions again, and so forth. We stop when at the some step we obtain a chain $A_1,\dots, A_{l+1}$ with all answers “yes” or a room of no liars. So, applying this procedure for the initial room with $n=69$ and $l=27$, we shall need at most $$28+27+\dots +2=-1+\sum_{k=1}^{28} k=-1+28\cdot29/2=405$$ questions to reliably identify a truth-teller.