The Third Hardest Logic Puzzle in the World

Question

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!

Answer 1

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

Answer 2

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

Answer 3

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.