8
$\begingroup$

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)\in\mathbb{Z}_{>0}\times\mathbb{Z}_{>0}$.

Known Results:

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

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

  • If $m<n$, then Todor Markov gave an improvement: $$N(m,n)\leq \max\big\{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 $m\geq 5$.

  • The user fedja and I discovered that $N(3,2)=2$ and $N(m,2)=3$ for all $m\geq 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)\in\mathbb{Z}_{>0}\times\mathbb{Z}_{>0}$.

$\endgroup$
  • $\begingroup$ Your title reminds me of the film An Honest Liar, a biography of the illusionist (magician) and debunker James Randi. $\endgroup$ – DanielWainfleet Dec 12 '18 at 14:16
  • $\begingroup$ Can you describe how to solve $N(1,100)$ in $2\cdot\min(1,100)=2$ tests? $\endgroup$ – Mike Earnest Dec 12 '18 at 23:08
  • $\begingroup$ @MikeEarnest I seem to have made an assumption that $m>n$ in my old (faulty) proof. Therefore, I redacted my claim. $\endgroup$ – Batominovski Dec 12 '18 at 23:15
  • 1
    $\begingroup$ It is possible to succeed in $\max(n,2\cdot\min(m,n))$ queries by modifying your original strategy. One by one, query $X$ about other people. If $X$ says everyone is truthful, you are done after $n$ tests (because these $n+1$ people cannot all be liars, so they are all truthful). Otherwise, if $X$ says at least one person is a liar, then your argument shows you are done after $2\cdot\min(m,n)$ tests. $\endgroup$ – Mike Earnest Dec 12 '18 at 23:45
  • 1
    $\begingroup$ We can do improve @MikeEarnest's value slightly for the case $m<n$ (in the other case fedja's is already better). If $m<n$, the moment X has named $n-1$ as truthful, we know X and they are all the liars, and anyone else is truthful. So we have, if $m<n, N(m,n) = \max(n-1, 2m)$ $\endgroup$ – Todor Markov Dec 13 '18 at 8:19
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Yeah, this upper bound works even in the setting when liars can say anything they want (though I prefer to write it as $2n-B(n)$ and derive it from the recursion $f(n)\le n+f([n/2])$). That is the easy part. The hard part is the estimate from below. The best one I currently know is $2n-O(\sqrt n)$. Can you do any better for large $n$? $\endgroup$ – fedja Dec 13 '18 at 17:10
  • $\begingroup$ @fedja I think I can prove the matching lower bound when $m\ge 2n+1$ by adapting the proof in this paper (you need access from an institution to read). That is, $N(m,n)=2n-B(n)$ when $m\ge 2n+1$. But I do not have the energy to reword that two-page proof. $\endgroup$ – Mike Earnest Dec 13 '18 at 21:00
  • $\begingroup$ Thanks! I'll look it up when I am at work tomorrow. $\endgroup$ – fedja Dec 13 '18 at 21:18
  • $\begingroup$ I looked at it. Very cute paper but I still do not see how to modify it for our setting. We have a completely different decision tree now both in terms of the number of admissible colorings and in terms of leaves (I mean the information that we have exactly $n$ liars is not the same as the information that the truth-tellers are the majority). So if you could just clearly indicate what is the subset of admissible coloring schemes you want to look at and what is the new claim about the leaves in the decision tree, it would be very helpful. $\endgroup$ – fedja Dec 14 '18 at 19:09
  • $\begingroup$ @fedja Let $S$ be a subset of $2n+1$ people. We will only pay attention to information about the subset of truth-tellers in $S$. Initially, there are $2^{2n}$ possibilities for the set of truth-tellers in $S$. Letting $x\in S$, there are $2^{2n-1}+\frac12\binom{2n}n$ possibilities where $x$ is a truth teller. As you make comparisons, the number of possibilities is always a power of two, and the same goes for possibilities where $x$ is a truth-teller. Etc, etc $\endgroup$ – Mike Earnest Dec 14 '18 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.