8
$\begingroup$

5 shy dudes who can never talk for themselves stand in a circle.
Every time you ask one of them a question, the dude to their right will answer for them.
3 of them always lie and 2 of them always tell the truth.
The dudes are all-knowing about each other.

How many yes/no questions will it take you to find the 3 liars?

NOTE

The answers you receive are always formulated as such : "He wants to say [yes/no]".

$\endgroup$
1
  • $\begingroup$ "He wants to say [yes/no]" is ambiguous because it can mean "He wants to say [yes/no] but his lying nature makes him say [no/yes]" ; I think "His answer will be [yes/no]" avoids the ambiguity. $\endgroup$
    – Prem
    Mar 31, 2017 at 10:27

2 Answers 2

8
$\begingroup$

The answer is:

It can be done in 4 questions (2 or 3 if you're lucky).

I suspect this is the best case, actually, because there is a limit to how much information is conveyed by a yes/no answer. There's 10 possible results (combination 5,2), so you'll need at least $n$ questions to provide $2^n\geq 10$ results. So $n=4$ is the minimum.

Method:

Ask each in turn: Are you a truthteller? The dude you direct this at will always want to say yes. Thus the answer you receive will tell you whether the person to his right (the dude who's speaking) is a liar or not. Best case you get the 2 truth tellers in the first two questions. Worst cast, you get 2 liars followed by 2 truth tellers. You can stop as soon as you've got the 3 liars or the 2 truth tellers, which is at most 4.

$\endgroup$
5
  • 7
    $\begingroup$ Why will the dude you direction your question to always want to say yes? $\endgroup$ Mar 31, 2017 at 8:17
  • $\begingroup$ I don't get it, if I'm next to a liar, I will say "He wants to say no". Because the guy being a liar will say he's not a liar and I will say the truth… about what he wants to say. $\endgroup$ Mar 31, 2017 at 9:24
  • 3
    $\begingroup$ It works if you replace 'liar' with 'truth-teller' - I suspect a typo $\endgroup$ Mar 31, 2017 at 10:43
  • $\begingroup$ I really want to accept this answer but I think there is a little mistake you have to correct first. $\endgroup$ Mar 31, 2017 at 13:35
  • 1
    $\begingroup$ Yes, typo. Or getting myself muddled to be more precise $\endgroup$
    – Dr Xorile
    Mar 31, 2017 at 19:45
1
$\begingroup$

4 questions at worst, because the truth tellers and liars can be arranged in 10 ways (treating rotations as different results), which is less than $2^4$ but greater than $2^3$. Each time you ask a trivial yes-no question to one of the first 4 people, you'll know that if the answer is true, both the one whom you're asking and the next guy are either truth tellers or liars, and the duo is mixed if it's false. Letting the value for the very first guy be A and the opposite value B, it can be worked out that the symbol appearing thrice denotes the liars.

$\endgroup$

Your Answer

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

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