15
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Do the liars lie with a given probability and is it the same for all the liars, or do they communicate and tell whatever confuses you the most? (I haven't thought enough about the problem to say if it makes a difference, but it nearly always does) $\endgroup$ – Henrik Jun 20 '15 at 16:42
  • 2
    $\begingroup$ Relevant : dl.acm.org/citation.cfm?id=2779687&preflayout=flat $\endgroup$ – miradulo Jun 20 '15 at 16:50
  • $\begingroup$ @Henrik Sorry Sir, but no information beyond what I've written was given. $\endgroup$ – Make a Difference Jun 20 '15 at 17:08
  • 3
    $\begingroup$ @RossMillikan The puzzle states clearly and explicitly of the so-called liars that "they can lie or tell the truth". You may be right to complain that calling them "liars" is misleading, or that it's nonstandard terminology for "puzzles like this". Still, the problem is what it is. It's about 42 people who will always tell the truth, and 27 unreliable sorts who may say anything. $\endgroup$ – bof Jun 21 '15 at 5:24
  • 1
    $\begingroup$ Related: math.stackexchange.com/questions/3036667/…. $\endgroup$ – Batominovski Dec 12 '18 at 13:22
9
+100
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @saulspatz Why? Ask A about B. If "truth teller", pick B; if "liar", pick C. $\endgroup$ – fedja Dec 12 '18 at 15:17
  • $\begingroup$ You're right. I missed the point where you said the number of truth-tellers is greater than $\ell.$ Still, I don't quite see how you get $2\ell-1$ in general. $\endgroup$ – saulspatz Dec 12 '18 at 15:21
  • $\begingroup$ Okay, I see it now. +1 $\endgroup$ – saulspatz Dec 12 '18 at 15:28
  • $\begingroup$ So what about the bound $2\cdot 27-B(27)=50$? $\endgroup$ – san Dec 17 '18 at 13:42
  • 1
    $\begingroup$ @san Yes. And the best lower bound I can show is 43, which still leaves quite a gap... $\endgroup$ – fedja Dec 17 '18 at 15:30
7
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ This is a good answer to what the question would have been, if the OP didn't clearly state a nonstandard definition for "liar". $\endgroup$ – Micah Jun 21 '15 at 5:47
  • 1
    $\begingroup$ "it is possible to reassign people so that this connected component will have at most 27 people from each type" That is not necessarily true. We also need to preserve the answers given, so what would you do if all answers were "truth teller"? $\endgroup$ – fedja Dec 11 '18 at 4:44
  • 1
    $\begingroup$ I guess I finally figured out what you meant, though it is not quite what is formally written ;-) The right answer is still 53 because with 54 people you can, indeed, get 27 of each type, but it would mean that any remaining person is a truth teller, so this partition is still fine. With 53 covered people (assuming each next covered person is assigned the type in an alternating order) you, indeed, know neither which type is the liar one, nor whether there are any liars left. $\endgroup$ – fedja Dec 11 '18 at 4:59
  • 1
    $\begingroup$ @Batominovski I lost it again in the morning. :-( Note that if we have 2 liars and 3 truth-tellers in the room (ABCDE) and the liars are obliged to lie, we can find a truth-teller in 2 questions: ask A about B and C about D, so something is still fishy. Can you post a clear proof of the lower bound you have in mind? I should confess that I currently cannot :-( $\endgroup$ – fedja Dec 11 '18 at 10:28
  • 1
    $\begingroup$ @Batominovski Then E is a truth teller. Weird, isn't it? $\endgroup$ – fedja Dec 11 '18 at 10:32
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

First of all, if you can ask any question, you only need one, "If I were to ask you for one person who is a liar, and if you were to lie or tell the truth based on how you are going to answer this question, then who could you not pick?" No matter who you ask, the answer must always be a truth-teller.

However, if I understand correctly your question, you can only ask person A, "Is person B a truth-teller or a liar?"

To find the minimum number of questions needed, you can assume the best circumstances. So let's pick a person B. Let's assume that B is a truth-teller.

Now you go ask 27 people (who all happen to be truth-tellers) if B is a truth-teller. They all say yes. Either B is a truth-teller or a liar. If B is a liar, then the 27 people who said that B was a truth-teller lied. If both B and the 27 people who lied are liars, then there are 28 liars. Since there are 27 liars (69-42), B must be a truth-teller.

Therefore, if the first person you pick happens to be a truth-teller, and everyone you ask tells the truth (not necessarily being truth-tellers), then you can figure out for sure that B is a truth-teller in 27 questions.

Now, I haven't proven that 27 is the minimum number of questions that can be asked to determine a truth-teller (nor do I know how), but I did prove that you can do it in only 27 questions. There may very well be a faster way to determine a truth-teller.

UPDATE: I have thought about how to prove what the absolute minimum number of questions needed to determine a truth-teller is, and I have decided it is impossible. The goal is to prove that someone is a truth-teller. But how can you know the minimum number of questions required to prove that unless you know every possible way to prove that someone is a truth-teller. I can come of with a list of several ways to do so, but how can I know that there isn't another way? You may also try to go through every possible number of moves up to 27 and try to prove that you can't determine a truth-teller with that number of moves, but even then you need to know every possible way to prove that someone is a truth-teller in order to prove that you can't do it with that number of moves. I could be wrong, but I think that if my assumption that you can't know 100% whether you know all the ways to prove that someone is a truth-teller, then you can't know 100% whether a certain number of questions is the minimum number possible.

$\endgroup$

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.