24
$\begingroup$

You are investigating a shop robbery. The CCTV footage shows that there was one criminal, but it doesn't show their face. There are 10 suspects and you know that one of them is the criminal. The suspects don't know who the criminal is, except the criminal themselves. The suspects either always tell the truth or always lie. You can ask the whole group a yes/no question and every suspect must answer it. Can you deduce who the criminal is in 2 questions?

Bonus: Can you do it in just 1 question?

Improve this question
$\endgroup$
2
  • $\begingroup$ I've added the bonus question after seeing Bass' brilliant answer. $\endgroup$
    – Dmitry Kamenetsky
    Oct 3, 2021 at 23:30
  • $\begingroup$ I've updated my answer. Technically you can do better than asking 1 question of the whole group of suspects... $\endgroup$
    – Anon
    Oct 5, 2021 at 1:31

11 Answers 11

Reset to default
47
+50
$\begingroup$

Two questions?

"In five minutes, I'll ask you the question "Are you the criminal?" Will your answer be 'yes' then?"

The truth tellers that are not the criminal will simply answer "no". The liars that are not the criminal will know their answer would be "yes", so they also answer "no".

If the criminal is a truth teller, they'll simply answer "yes". If the criminal is a liar, they know they'd answer "no", so they'll answer "yes" anyway.

Improve this answer
$\endgroup$
13
  • 2
    $\begingroup$ Wow this is brilliant! I feel a bounty coming your way. $\endgroup$
    – Dmitry Kamenetsky
    Oct 3, 2021 at 13:52
  • 1
    $\begingroup$ Why the five-minute delay? You could just say (ROT13 for spoilers): Vs V jrer gb nfx lbh "Ner lbh gur pevzvany?", jbhyq lbhe nafjre or "Lrf"? $\endgroup$
    – paxdiablo
    Oct 4, 2021 at 3:04
  • 2
    $\begingroup$ @paxdiablo IMO the delay does not matter and it reads better this way. $\endgroup$
    – Andrew Savinykh
    Oct 4, 2021 at 7:26
  • 2
    $\begingroup$ @aslum Adding "if" to the question fixes that issue. $\endgroup$
    – Rushabh Mehta
    Oct 4, 2021 at 14:45
  • 5
    $\begingroup$ @AndrewSavinykh is correct, the delay is there for the sole reason of isolating the subjunctive clause into a simple, easy to grasp situation in the future. This automatically turns the human brain into the mode of considering hypotheticals, and can be explained in simple, declarative sentences. This wasn't so much planned out as it was a manner of speaking learned during years and years of customer service: if you need to make every single one out of ten random persons understand you on the first go, your language has to be stupidly simple. I do love Ted's brilliant take though. $\endgroup$
    – Bass
    Oct 4, 2021 at 18:40
23
$\begingroup$

If I ask:

Am I a tree-frog?

The truth-tellers will answer "no", and the liars will answer "yes" (assuming I am not a tree-frog), and I now know who is who.

Then I ask:

Did you rob the store?

If the guilty party is a truth-teller, precisely one of the truth-tellers will say "yes", and if the suspect is a liar, precisely one of the liars will say "no".

In either case I know who the guilty party is.

To clarify,

This exploits a humorous loophole in these logic questions thanks to Kaspar Hauser/Werner Herzog (see this clip from a movie which I highly recommend if you haven't watched it already).

Specifically, these knight/knave questions generally rely on the subject asking a complicated purely logical question that assumes the presence of no extra information (e.g. whether I am a tree-frog) such as if I asked you whether you are a liar, would you say "no"?, when there are numerous simpler questions that would suffice if actual only-liars and only-truthtellers existed in the real world.

Edit: My answer above was to the initial question (whether it is possible to ask two questions to all ten suspects to deduce who the criminal is). As was pointed out by @Bass, and now by a number of other answerers, this can in fact be done in only one question. @Ted's brilliant answer is essentially equivalent to:

Are you either a lying criminal or a truth-telling innocent person?

Which all innocents will answer "yes" to, and all criminals will answer "no" to.

We can come up with a lot of other single question solutions, e.g. exploiting the fact that non-criminals do not know who the criminal is to ask something like:

Would you deny knowing who the suspect is?

To which all innocent people will say "yes" and all criminals will say "no".

However...

We can actually do slightly better even than one question if you think about it...

The OP's setup has us asking all ten suspects a single yes/no question which they must all answer. But we do not need to ask all ten. If we take any nine of the suspects into a room, and ask them all one of the many possible single questions (e.g. are you either a lying criminal or a truth-telling innocent person?), then if the suspect is in the room, we will obviously be able to identify them, and if the suspect is not in the room, then they will all answer as innocent people, and we will know ipso facto that the criminal is the excluded one

If the OP's setup is $1.0$ questions, this is technically $0.9$ questions

But can we do better?

Unfortunately not.

Obviously if we took 8 people into the room, then if the suspect is among them (a $0.8$ chance) we will identify them, but there is a $0.2$ chance that the subject will be among those excluded. In this case we will have to ask a second question of the two outside the room.

The expected value in this case of the number of questions needed will be:
$$(1\times0.8)+(2\times0.2)=1.2$$ Which is now worse than $1.0$. In general, if we ask a single question of $n\in{2,...,n-2}$ of the people in the room, the expected value of the number of questions we need will be:
$$\left(1\times\frac{n}{10}\right)+\left(2\times\frac{10-n}{10}\right)$$ $$=2-\frac{n}{10}>1$$ Thus it looks like asking a single question of nine suspects is the best we can do

Thinking about it this makes sense:

If we ask a single question of any less than 9 people, then if the criminal is not in their number we will need to ask a second question of those outside the room, as we know (per the OP) that non-criminals do not know who the criminal is, hence they can give us no further useful information to distinguish them. And the fewer people we ask initially, the greater the chance this will happen.

An interesting variation of the puzzle arises though if all of the suspects know who the criminal is.

Figuring which of the ten is the criminal requires 3.3 bits of information, so theoretically it should be possible to ask a single question of only 4 of the suspects. We could 'hack' the question to give us all the information we need.
An example of such a question would be (label the suspects 1-10, take suspects 1-4 into a room and tell them who has which number in binary):

If I asked you whether ((you're number 1 AND the first bit of the criminal's number is 0) OR (you're number 2 AND the second bit of the criminal's number is 0) OR (you're number 3 AND the third bit of the criminal's number is 0) OR (you're number 4 AND the fourth bit of the criminal's number is 0)) would you say "no"?

Once the four have had time to parse this question, their answers will let you determine the criminal:

For instance, person 3's truthful response to each of the bracketed questions would be "no", "no", "yes"/"no" (depending on the criminal's number's third bit), "no" which because of the connecting OR statements means if person 3 is a truthteller they would say "no" to the main bracketed question if the bit is 1 and "yes" if it is 0, and vice-versa if they are a liar. The whole italicized question then (which asks if they would say "no") forces them to answer the same whether they are a liar or truthteller, which now tells us the third bit of the criminal's number.

Combining this with the responses of 1, 2, and 4 enables us to determine who the suspect is. Note this would work with the same question with up to 16 total suspects, as there is wasted information in the truth-table of the question when we ask 4 people (as $\log_2{10}\approx3.3$)

Nevertheless I don't think such a strategy will work in the original question where the other suspects do not know the criminal's identity.

There is one final possibility.

We've demonstrated that it is in fact possible to ask a single question of only nine of the suspects to deduce the criminal's identity.

However if you think about it this is really nine questions (or ten if we ask the whole group as in Bass's answer) as we get nine (or ten) bits of information.

But...

The OP's question states "you can ask the whole group a yes/no question and every suspect must answer it". It does not explicitly state that you must ask them all at the same time...

If you ask them one-by-one as you likely would in a real interrogation (e.g. ask Would you deny knowing who the suspect is?) you can stop when you know who the suspect is.

There is a $0.9$ chance the suspect will be in the first 9 you ask, and if not, you know they are the one you have not interviewed. Thus the expected value of the number of questions you will need to ask is:
$$\sum_{n\in{1,2,...,9}}\left(n\times\frac{1}{10}\right)$$ $$=\frac{45}{10}=4.5$$ Thus instead of asking a single question of a proportion of $1.0$ of the group, we can actually ask it of an average of $0.45$ of the group.

I don't think we can do better.

Conclusion:

1. We can ask a single question of all ten at the same time:
   - If I asked whether you're the criminal would you say "yes"? (based on @Bass's answer)
   - Are you either a lying criminal or a truth-telling innocent person? (based on @Ted's answer)
   - Would you deny knowing who the suspect is?

2. We can ask the same question of only nine of the suspects at the same time

3. If asking individually is allowed, we can ask the same question to random subjects one-by-one, and only need to ask an average of $4.5$ (maximum $9$) suspects

Improve this answer
$\endgroup$
8
  • 3
    $\begingroup$ Well done. This is correct! This was the intended solution. In fact I am not aware of another solution, so would be interested to see one. Thank you for the nice video too :) $\endgroup$
    – Dmitry Kamenetsky
    Oct 3, 2021 at 13:45
  • $\begingroup$ What if the criminal was delusional and truly believed the answer to the first question was true? :-) $\endgroup$
    – paxdiablo
    Oct 4, 2021 at 3:06
  • 2
    $\begingroup$ @paxdiablo In fact there's an even more fundamental issue with translating liar puzzles to the real world... Generally they require that each person's statements be either true or false, so a knight or knave cannot say "this statement is false" or something like that. This is of course not realistic, as many things we say may be logically inconsistent (and in fact I think Godel implies that in many cases we cannot even figure what is consistent and what is not)... $\endgroup$
    – Anon
    Oct 4, 2021 at 12:22
  • 1
    $\begingroup$ @Anon: A well-formed question should be equivalent to showing a list of possible scenarios and asking if any of them applies the present situation. It shouldn't be necessary to allow ambiguous or hypothetical questions. On the flip side, if people who may answer arbitrarily can be classified according to whether they will answer "yes" or "no", and if those who answer truthfully know into which subcategory the arbitrary-answer people belong, it's possible to make strong inferences even if arbitrary-answer people are in the majority. $\endgroup$
    – supercat
    Oct 4, 2021 at 21:33
  • 2
    $\begingroup$ @DmitryKamenetsky A further edit, exploring a slight variation on your original puzzle which gives some cool results... $\endgroup$
    – Anon
    Oct 5, 2021 at 2:03
16
$\begingroup$

I'm not sure if this is equivalent somehow to Bass' answer, but I think this does it in one question:

You could ask "Are you a liar xor a robber?"
We can kind of reframe the question as there are four people, one robber/liar, one non-robber/liar, one non-robber/non-liar, and one robber/non-liar. How can we identify the robbers? Any robbers will answer yes to "Are you a liar xor a robber?", and anyone else will answer no.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Clever. Works whether they lie about inputs and outputs or just outputs. Doesn't work if they lie just about the inputs, but I think that matches the question. It might be clearer to break it out since "yes" isn't really boolean (maybe like "are you _ and also _ OR not _ and also not _"). $\endgroup$
    – melds
    Oct 5, 2021 at 1:02
6
$\begingroup$

The first question could be..

Are you suspects? The suspects will now be split in true tellers and lie tellers. True tellers will say YES, lie tellers will say NO. So now you know who's always telling the truth and who's lying.

The second question could be..

Are you the robber? If it's one of the true tellers you'll get 1 YES and the rest NO. If it's one of the lie tellers you'll get 1 NO and the rest YES. So it's now easy to identify who the robber is.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yeah, this is a similar idea to my answer. rot13(Unir gur svefg nfxvat n onfvp gehgu gung nyy gur fhfcrpgf zhfg nafjre rvgure gehgushyyl be snyfryl. Gung'f jul nqqvat n enaqbz orvat znxrf guvf zhpu uneqre.) I suspect that's not the intended answer here though... $\endgroup$
    – Anon
    Oct 3, 2021 at 13:44
2
$\begingroup$

Question to ask the group :

" If I asked you whether you are the criminal, will you reply with a "yes" or a "no"?

The one who replies with a " yes" is the criminal.

- For the innocent suspects : The truth tellers would have said " no " ( they are innocent) and also they have to tell the truth about what they would have said, and hence they reply with a "no" to the question. The liars would have said "yes" , but they also have to lie about what they would have said , hence they reply with a "no" to the question.

- For the Criminal : If he is a truther, he would have said "yes" ( he is guilty ), and he also has to tell the truth about what he would have said. Hence his final answer is "yes". If the criminal is a liar, he would have lied, and hence would have said "no", but he also has to lie about what he would have said, hence his final answer is "yes".

The power of two NOT gates !!

Improve this answer
$\endgroup$
3
  • $\begingroup$ I disagree on the last part, a lying criminal would answer no, as the answer the question is yes, he is a criminal, so he would lie and say no. If he says yes to the question, then it is not a lie $\endgroup$
    – Beastly Gerbil
    Oct 4, 2021 at 0:16
  • 3
    $\begingroup$ @BeastlyGerbil: That's not how the question works. The criminal has to lie about the lie he would hypothetically have told. $\endgroup$
    – user2357112
    Oct 4, 2021 at 1:03
  • 1
    $\begingroup$ This is a very common technique for these kinds of "liars and truth tellers" problems. $\endgroup$
    – user2357112
    Oct 4, 2021 at 1:05
2
$\begingroup$

My attempt at the 1 question version

Would the robber tell me who they are?

Explanation (I might be wrong here...):

The robber will be the first to answer as the other 9 do not know what to say yet. The lying robber would answer yes and the truthful robber would answer yes, then the others will be able to answer yes or no, but the answer does not matter to us.

Improve this answer
$\endgroup$
1
$\begingroup$

My take on this:

Question 1: "Are you a robber?" Robber-Truthteller and Innocent-Liar will say "yes".
Question 2: "Did you answered "yes" to previous question?" Robber-Truthteller will say "yes", but Innocent-Liar will say "no".

Improve this answer
$\endgroup$
0
$\begingroup$

You only need one question for each person. you can ask "If I would ask you if you had robbed the store, what would you answer?" The robber answers with yes, the innocent people answer no, no matter if they are liars or not.

Improve this answer
$\endgroup$
0
$\begingroup$

Though this is just a two-question solution it has, I think, an original mathematical flavor. Though, I'm not sure whether it's valid, since it requires either physically rearranging the suspects or giving them name tags, and does "magic" with the constant truthfulness of each suspect.

First, put the suspects in a circle. Equivalently we can give them numbers on their tags from 0 to 9, so that each suspect can see all the other suspect's tags. Then ask them:

Is the person to your right the robber?

and then

Is the person to your left the robber?

If they aren't in a circle, these questions have analogues in modular arithmetic w.r.t. the number tags.

Finally, the robber is the suspect where

both of their neighbors answered differently on the two questions. Regardless of truthfulness, a suspect with two non-robbers on either side will answer the same to the two questions, but the suspects on either side of the robber must change their answer.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Welcome! While I really like this answer I think it ignores the phrase "the suspects don't know who the criminal is, except the criminal themselves" in the original question. But I do like the idea behind it, and I may have misinterpreted... $\endgroup$
    – Anon
    Oct 5, 2021 at 0:40
  • 1
    $\begingroup$ @Anon I'm glad you liked it! And yes, it does somewhat warp the question; mainly I think it messes with the meaning of "lie," for if this merely means false statement then it's okay imo, but if we require an intention to deceive, then... not so much. $\endgroup$
    – Mushroom Man
    Oct 5, 2021 at 2:23
0
$\begingroup$

A simple answer with two questions:

First, ask everyone if they know the criminal. Then learn if they're liars or not by asking a trivial question.

We can improve it by linking the two elements in the paragraph above:

These are the knowledge of the criminal and being a liar or truth teller. We want the innocent truth tellers and liars to say X, and the guilty truth teller or liar to say the opposite. Ask "Is the state of your knowledge the same as the truth value of your statement?" or something to that effect. A truth-telling criminal will say yes. A lying criminal will say yes. A truth-telling innocent will say no. A lying innocent will also say no.

Improve this answer
$\endgroup$
-1
$\begingroup$

do you know who the criminal is ?

And that's it. Since only the criminal has a different answer for this question

In the "suspects always tell the truth" setup, criminal says yes and non-criminals say no.

In the "suspects always lie" setup, criminal says no and non-criminals say yes.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ I think you've fallen into the same trap as some of the other answerers in assuming that either everyone tells the truth or everyone lies. The actual intended meaning is that each person either tells the truth or lies. $\endgroup$
    – Rand al'Thor
    Oct 6, 2021 at 15:31
  • $\begingroup$ I was expecting that answer because that would have been a redundant information otherwise $\endgroup$
    – Stardust Motion
    Oct 6, 2021 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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