7
$\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$
  • $\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 '17 at 10:27
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$
  • 7
    $\begingroup$ Why will the dude you direction your question to always want to say yes? $\endgroup$ – Santana Afton Mar 31 '17 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$ – Pierre Arlaud Mar 31 '17 at 9:24
  • 3
    $\begingroup$ It works if you replace 'liar' with 'truth-teller' - I suspect a typo $\endgroup$ – LogicianWithAHat Mar 31 '17 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$ – stack reader Mar 31 '17 at 13:35
  • 1
    $\begingroup$ Yes, typo. Or getting myself muddled to be more precise $\endgroup$ – Dr Xorile Mar 31 '17 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, privacy policy and cookie policy

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