0
$\begingroup$

This puzzle is heavily derived from the Second Hardest Logic Puzzle in the World, which I also created. The current puzzle and the aforementioned are not identical, however.

You have 5 guards: one always tells the truth, one always lies, one flips a coin in their head to determine what they say, one always says yes and one always says no. Your goal is to find out who's who in the least questions. You aren't allowed to ask a head exploder or anything that would hinge on the coin flipper's behavior (but guards know how the others behave).

The major difference is that you can only ask a question to a single guard at a time. The standard strategy in this puzzle would require 11 questions using this metric. Can you do better?

Answers are distinguished as such, with points lower down the list being a tie breaker if all of the conditions above them are equal:

  • Number of questions in the worst case
  • Number of questions in the best case
  • Probability that the best case will be achieved
  • Time of posting

May the best answerer win!

$\endgroup$
8
  • 3
    $\begingroup$ The extra scoring conditions make this look like a game rather than a puzzle - the question isn't "find the optimal solution", it's "find the best solution among all answerers". While this may not be an open-ended puzzle as explained by this meta post, it still has many of the same features that make it not appropriate for this site (in my opinion, at least). $\endgroup$
    – Deusovi
    Jul 6 at 23:55
  • $\begingroup$ Would [optimization] fit here? I'm tempted to offer [open-ended], per Deus's comment $\endgroup$
    – bobble
    Jul 6 at 23:58
  • $\begingroup$ @Deusovi Except for "Time of posting", the other three criterion actually define an optimization problem. And adding "Time of posting" doesn't make it more like a game. I would say the question isn't "find the best solution among all answerers" but rather "find the optimal solution where optimality is defined by the three criterions with priorities from up to down". Nevertheless I don't think this is a good puzzle. $\endgroup$
    – WhatsUp
    Jul 7 at 0:23
  • $\begingroup$ @WhatsUp Yes, they do define an optimization problem, but one that seems to be structured more like a game than a puzzle. The phrasing of the question is essentially "the winner is whoever gets the best solution out of the submitted ones": rather than a puzzle with a single solution, the question appears intended as a competition. [...] $\endgroup$
    – Deusovi
    Jul 7 at 0:29
  • 1
    $\begingroup$ Wouldn't converting the answer to the previous question into this result in 9 questions easily? $\endgroup$
    – justhalf
    Jul 7 at 1:34
3
$\begingroup$

I think you can do this with 9 questions

first

you ask all 5 of them

Are you Alive?, that is total 5 questions.

You have answers that are (3 Yes and 2 No's) or or (3 No's and 2 Yes), depending on which side coin flipper chooses.

Now if there are 2 No's, you know those 2 people are one "Liar" and one "No Man"

if there are 2 Yes, you know those 2 people are one "Truth speaker" and one "Yes Man"

irrespective of the outcome

Next 1 question you can find either the person who always speaks truth or always lies

if you had a set of 2 No's, you ask do you always speak truth, this would force "No man to still say No and liar to say Yes"

if you had a set of 2 Yes, you ask do you always lie, this would force "Yes man to still say Yes and truth speaker to say No"

so you have got either of the person who always says truth or always lies, yo have also got either the person who always says yes or always says No

Now to figure the remaining people

remaining three to be identified,

you can ask about them directly to the liar or truth speaker and get their identity, i.e 3 questions more

so the final number of questions you need to ask is

5+1+3 = 9

$\endgroup$
3
  • $\begingroup$ In the last set, how do you deal with a coin flipper who happens to mimic another guard consistently? $\endgroup$
    – Lord Ratte
    Jul 17 at 21:15
  • $\begingroup$ The best case with this strategy is 6 questions. If #1 through #3 all have the same answer, then you can skip #4 and #5, and if #7 successfully identifies someone, then you can skip #9. $\endgroup$ Jul 19 at 0:04
  • $\begingroup$ @LordRatte Not counting the coin flipper, there will be 2 "Yes" and 2 "No" answers to "Are you Alive?", so you know for sure that the coin flipper is not among the guards who gave the minority answer. $\endgroup$ Jul 19 at 0:28
2
$\begingroup$

Turned out to be the same answer, but followed by a proof:

Let's ask a question whose answer we know is "yes" (eg. is 2x2=4 true?) to all of them (5 questions).

If there are 2 yes answers, then only the truth teller (TT) and yes sayer (YS) must have said yes. The randomer's answer is a no. To distinguish the TT from the YS, ask another question to one of them whose answer we know is a no (eg. is 2x2=4 false?). This only leaves 3 unidentified people who can form 6 permutations, so at least 3 more questions are necessary. The same applies to the opposite scenario (3 yes answers, starting from the nays and isolating the liar instead). Just use the TT to identify the others. You ask 9 questions in total.

Prove that a better answer isn't possible:

There are 120 possible permutations of the guards. Since 120>2^6, it requires at least 7 questions. This also means at least someone will be asked multiple times, and for all we know, that someone or one of them could be the randomer. Identifying everyone perfectly also means identifying the randomer's answers as truths or lies, so the 120 possibilities become 480 if they're unwittingly asked twice.

For a better answer, the randomer must be avoided after one question at most. Ask A a question, but then ask B in case A is a randomer. It's not enough, so ask C and D too. After asking D, the people telling truths and lies could be equally distributed, or they could be 3 to 1 / 1 to 3. The randomer can only be safely distinguished or dismissed by asking the TT or liar (L) about them, but the latter two can only be safely identified after talking to all the people. That means it's inevitable to ask the randomer a question (at least 240 possibilities), so at least 8 questions are required. Same for yes/no sayers (at least 480 possibilities).

$\endgroup$
1
  • $\begingroup$ Why do you assume that it will be impossible to avoid asking a second question of a randomizer? You give a strategy that avoids that. The reason your strategy requires nine questions rather than eight is that you don't do a good job of bisecting the sets of possibilities that would yield a "yes" answer from those that would yield a "no". $\endgroup$
    – supercat
    Aug 24 at 19:19
-1
$\begingroup$

The worst case has the potential to reach any positive, finite number. I will demonstrate this with a counter-example using the 11-question strategy. Let's label the guards: T always tells the truth. F always lies. Y always says yes. N always says no. R gives a random answer.

State 1:

Ask each one "Are you both T and F?" After which, suppose I get the following answers (zero is no; one is yes) T:0 F:1 Y:1 N:0 R:1

State 2:

Now I have two groups.

Group 1 contains T and N

Group 2 contains F, Y and R

Ask one guard from group 1, "Are you T?" If the answer is yes, they are T and the other one is N. Else, visa-versa. Cool.

That leaves group 2. Ask each one "Are you F?".

The answers will be F:0 Y:1 R:0/1

State 3:

Either R said yes, in which case the only one who said no was F. Or R said no, in which case the only one who said yes was Y. Let's take that as an example and say we can exclude Y.

State 4:

We must now figure out which of the remaining two is F and which is R. Let's ask: "are you F?" to both. in the best case scenario, F says no and R says yes.

But we're testing the worst case, so let's say R also says no. Oops. That leaves us at State 4. This could potentially go on for any finite amount of times until R finally gives a different answer to F so that you can tell the difference.

Now what?

Since the worst possible case is equally bad for all answers, all answers tie for that position according to scoring.

Number of questions in the worst case

My solution is then to not ask any questions at all and guess that the 1st, 2nd, 3rd, 4th and 5th are T, F, Y, N and R respectively.

This is the best case scenario which also happens to be the next tie-breaker.

Number of questions in the best case

Is this likely? Of course not! But the next tie-breaker (Probability that the best case will be achieved) only applies if someone actually ties with me (zero questions).

Note

I hope that it is clear that this is a genuine post and not a "troll answer". I'm not so interested in having the winning answer so much as providing an interesting answer should we take the rules as literally as we can.

I know it seems like an odd answer but read through the proof carefully and if you still have an objection, feel free to comment.

Update

This answer does not work because

As bobble pointed out in the comments, you can short circuit the loop by using either T or F (whoever isn't in the same group as R at the time) to find out the identity of everyone who is left.

I would, however, like to leave this answer in-tact in case anyone else tries to follow the same line of reasoning.

$\endgroup$
3
  • $\begingroup$ Once you've identified T, what's to stop you from using them to separate/identify everyone else? $\endgroup$
    – bobble
    Jul 17 at 23:41
  • $\begingroup$ @bobble That's a good question. It's true that you can use T, but only in situations when T is not in the same group as R. But that's not the worst case scenario. The worst case is having T in the same group as R until the end. But then again, in those questions you could have F in a different group to F providing equal utility. $\endgroup$
    – Lord Ratte
    Jul 18 at 0:01
  • $\begingroup$ So it may be that the presence of T and F in the same problem is what makes my answer not possible. Let me give it some thought and then edit accordingly. $\endgroup$
    – Lord Ratte
    Jul 18 at 0:02

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.