Csdrhrt

This question is inspired by this thread. In that thread, a liar may both tells lies and truths. However, in my version, liars always lie.

Main Question. A group of people consists of $m$ truth-tellers (who always are truthful) and $n$ liars (who always lie) where $m$ and $n$ are positive integers. In the group, everybody knows whether another from the group is a truth-teller or a liar. You do not have this information whatsoever, and cannot discern the distinction between a truth-teller and a liar, but you know the values of $m$ and $n$.

The aim is to identify a truth-teller within the group. You can only ask a person $A$ about another person $B$ whether $B$ is a liar. If $N(m,n)$ is the smallest possible number of questions you need to guarantee that the job can be accomplished, then determine the value of $N(m,n)$ for each pair $(m,n)inmathbb{Z}_{>0}timesmathbb{Z}_{>0}$.

Known Results:

• If $m=n$, then $N(m,n)$ does not exist.




• If $mneq n$, then Mike Earnest showed that $$N(m,n)leq maxbig{n,2,min{m,n}big},.$$




• If $m<n$, then Todor Markov gave an improvement: $$N(m,n)leq maxbig{n-1,2,min{m,n}big},.$$




• If $m>n$, then the user fedja found that $$N(m,n)leq 2n-1,.$$




• For all $m>1$, $N(m,1)=1$.




• I know that $N(2,3)=3$, $N(2,4)=4$, and $N(2,m)=m-1$ for $mgeq 5$.




• The user fedja and I discovered that $N(3,2)=2$ and $N(m,2)=3$ for all $mgeq 4$.




• The user fedja found that $N(m,3)=4$ for all sufficiently large $m$, and $N(m,4)=7$ for all sufficiently large $m$.

However, if you want to solve the following generalized version of the question in the linked thread here, then you are very welcome. In other words, I would also love to see the answer to this auxiliary question. (It is also good if you put your answer to the question below in the thread above.)

Auxiliary Question. A group of people consists of $m$ truth-tellers (who always are truthful) and $n$ drunkards (who may tell both truths or lies) where $m$ and $n$ are positive integers. In the group, everybody knows whether another from the group is a truth-teller or a drunkard. You do not have this information whatsoever, and cannot discern the distinction between a truth-teller and a drunkard, but you know the values of $m$ and $n$.

The aim is to identify a truth-teller within the group. You can only ask a person $A$ about another person $B$ whether $B$ is a drunkard. If $M(m,n)$ is the smallest possible number of questions you need to guarantee that the job can be accomplished, then determine the value of $M(m,n)$ for each pair $(m,n)inmathbb{Z}_{>0}timesmathbb{Z}_{>0}$.

Let $B(k)$ denote the number of ones that $k$ has when written in binary.

If $m>n$, then $N(m,n)le 2n+1-B(2n+1)$.

This corresponds with the bounds $N(m,3)le 4$ and $N(m,4)le 7$ mentioned in the post.

Proof: Take any $2n+1$ people and ignore the rest. The majority of those people are truth tellers, and we need to find a truth teller, where the only allowed operation is two select to people and learn whether or not they are the same. This is exactly the situation discussed in this paper, which provides an algorithm to succeed in the claimed number of tests.

At any point in the algorithm, the people will be divided into groups, such that people in a group are known to have the same identity as each other. Initially, everyone is in their own group. Repeatedly, find two groups of equal size, and compare a representative from each. If they are equal, then merge the groups. If not, then throw both groups in the "trash." Throwing away these two groups leaves a majority of truth-tellers among the non-trash groups.

The algorithm terminates when all the non-trash groups have different sizes. These groups are all sizes which are powers of two, so the largest group must be larger than the sum of the others, implying it must be made of truth tellers. In the worst case, no groups were thrown away, so these sizes correspond to the binary representation of $2n+1$. It takes $2^k-1$ operations to form a group of size $2^k$; adding these up, you get $2n+1-B(2n+1)$.