Variant of the hardest logic puzzle ever

Question

I have landed on a new planet and there are 4 people there. One of them is a truth teller and they always speak the truth. The other is a liar and they always lie. The other 2 are random and they sometimes say yes and sometimes say no, all at random. Each of them knows everything about all the others. I wish to find out the identities of all of them by asking the minimum number of questions possible. What should be my approach ?

This is a variation of "The hardest logic puzzle ever" . The only difference is is that in the original problem, there is only one random instead of two. The following is an excellent video that details, both the original question and the answer : https://youtu.be/LKvjIsyYng8

Coming back to my question, how many minimum questions will i need to ask to find the identities of all the 4 and what should be the questions?

I have solved it partially and am detailing my attempt below. Notice that I am able to solve it for cases 1 and 2 but not for cases 3 and 4.

---

My attempt :

Let us assume that the persons are standing in a line and are facing towards me.

I ask the first person about the second person, " Would you have said yes if I had asked you if the person standing to your left is a random?"

Then, I ask the third person about the fourth person, "Would you have said yes if I had asked you if the person to your left is a random?"

Possible replies :

Case1: Yes No ( the 1st person says yes & the 3rd says no)

Case 2: No Yes

Case 3: Yes Yes

Case 4: No No

I am able to solve it for the cases 1 and 2 i.e when one of them says yes and the other says no. I will illustrate why I am able to solve, by using case 1. However, the same logic holds for case 2.

Case 1:

Lemma 1: At least one person between the first person and the second person is a random. This is because :

a) The first person themselves is a random and chose to say yes randomly, or

b) The first person is a truthteller and if they are saying yes then that means that the second person is surely a random.

c) The first person is a liar and their answer to the above question can be yes only if the second is a random (it is easy to figure out why but if it is still unclear then please see the video above to understand why).

Lemma 2: The fourth person is not a random. This is because :

a) The third person themselves is a random and chose to say no randomly. ( And since we know that at least one person between the first and the second person is a random, then this means that the fourth person cannot be the other random) or,

b) The third person is a truthteller and if they are saying no then that means that the fourth person is surely not a random, or

c) The third person is a liar and their answer to the above question can be "no" only if the fourth person is not a random (again, it is easy to figure out why but if it is still unclear then please see the video above to understand why).

Therefore, now that we have figured out that the 4th person is not a random, we can simply ask them, "Is 2+2=4?". Based on their answer, we can find if they are a truth teller or a liar and then use them to find the identities of everybody else.

We can have the same approach for case 2. But I cannot figure out how to solve cases 3 and 4.

Answer 1

I think that

There is no minimum

with the following reasoning (please feel free to point out any flaws in my reasoning):

Label the four individuals as $A$, $B$, $C$, $D$ and consider the following alternative scenario, which I'll call Scenario 1

$A$ answers as though they are a truthteller, $B$ is a liar and $C$ and $D$ are random.
$B$ answers as though they are a liar, $A$ is a truthteller and $C$ and $D$ are random.
$C$ answers as though they are a truthteller, $D$ is a liar and $A$ and $B$ are random.
$D$ answers as though they are a liar, $C$ is a truthteller and $A$ and $B$ are random.

In this version of the problem, we can swap $A$ for $C$ and $B$ for $D$ and the problem remains the same. Hence, for any questions asked, there is no way to distinguish $(A,B)$ from $(C,D)$.

Now let us consider the following Scenario 2

Replace $A$ with a truthteller, $B$ with a liar and $C$ and $D$ in with randoms in Scenario 1 but all of the answers of $C$ and $D$ will be as if we are in Scenario 1 (for any finite number of questions this may always happen by chance).

And Scenario 3

Replace $A$ and $B$ in Scenario 1 with randoms but all of their answers will be as if we are in Scenario 1 (again, can happen by chance). Replace $C$ with a truthteller and $D$ with a liar.

Now note that

Given that we cannot distinguish the two cases in Scenario 1, it is also impossible to guarantee that we can distinguish Scenario 2 from Scenario 3 with any finite number of questions.

That is to say, for any finite number of questions, the responses in Scenario 2 can match up with the responses in Scenario 3 and we cannot guarantee to distinguish them.

Analogy to cases 3 and 4 in question

So suppose we call the "1st person" A and the "3rd person" C. Then the "No No" case, for example, can arise in either Scenario 2 or Scenario 3 so they are not distinguished here. Similarly, by changing the orientation, the "Yes Yes" case can also occur in both Scenario 2 or Scenario 3. The "Yes No" and "No Yes" cases break the symmetry which is why we can make more progress here.

Answer 2

I know its confusing, so if 2-3 people tell me that it would help them if I write a code where the computer finds the identities of the aliens, I will do so ASAP.

Answer:

The minimum number of questions required to guarentee knowledge of their identities is:

10 questions

Proof:

To be honest I have no idea how to even start proving that my answer is the lower bound for this problem. If you have a better answer, comment below; I will put a desclaimer acknoledging your supremacy 😂

Logic terminology:

Basic logic terminology is needed in order to understand my explanation.

• a and b --> is true if both a and b are true
• a or b --> is true is either (or both) a or b is true
• a xor b --> is true if either, but not both a and b are true
• a nand b --> is true when (a and b = false)
• a nor b --> is true when (a or b = false)
• a xnor b --> is true when (a xor b = false) Here is a picture that gives truth tables and explanations for these basic logic operators:

Explanation:

Ok this is gonna be extremely long so I'm gonna write cases such that (the letters are variables) Case A.B is a sub case of Case A, Case A.B.C is a sub case of A.B, etc. Sorry if its confusing.

Ask all 4 aliens an obvious question, such as "Is 1+1=2?" At least one person will tell the truth and at least one will lie, leaving us with 3 cases-- Case 1: 1 alien says yes and 3 say no, Case 2: 3 aliens say yes and 1 says no, or Case 3: 2 aliens say yes and 2 tell say no.

For the sake of being able to understand, we are going to give the names A, B, C, or D. The people who answered yes to the above question will get alphabetically higher names.

• Case 1:

(Cumulative question count: 4)
3 aliens (A, B & C) say yes and 1 (D) says no
D is the liar. Ask D "Is B a random?" and "Is C a random?"
(Yes, Yes) --> Not possible; (Yes, No) --> B is the truth teller, A & C are randoms; (No, Yes) --> C is the truth teller, A & B are randoms; (No, No) --> A is the truth teller, B & C are randoms
All identities were found in 6 questions

• Case 2:

(Cumulative question count: 4)
1 alien (A) says yes and 3 (B, C & D) say no
A is the truthteller. Ask A "Is B a random?" and "Is C a random?"
(Yes, Yes) --> D is the liar, B & C are randoms;
(Yes, No) --> C is liar, B & D are randoms; (No, Yes) --> B is the liar, C & D are randoms; (No, No) --> Not Possible All identities were found in 6 questions

• Case 3:

(Cumulative question count: 4)
2 aliens (A & B) say yes and 2 (C & D) say no
This leaves us with 4 possible line-ups: TRLR, TRRL, RTLR, RTRL. Ask all four of them "Are B xor C (either but not both) randoms?"
There are a list of 16 cases (listed below)

The cases are listed by a String of "y"s and "n"s, representing yes/no responses. The answers start with alien A, then B, then C and finally D. The results of the 16 cases:

1) nnnn: Not Possible
2) nnny: trrl
3) nnyn: rtlr
4) nnyy: trrl, rtlr
5) nynn: rtrl
6) nyny: trrl
7) nyyn: rtrl
8) nyyy: trrl
9) ynnn: trlr
10) ynny: trlr
11) ynyn: rtlr
12) ynyy: rtlr
13) yynn: trlr, rtrl
14) yyny: trlr
15) yyyn: rtrl
16) yyyy: Not possible

I am not going to explain every single case above as that would be a mess. However, I will explain a few and leave you the tools to check it.

Note the following properties, let's call it The Law of Pairs:

Either A or B is the truth teller
Either C or D is the liar
If A & B say the same thing, it is true
If C & D say the same thing, it is false

The other tool is:

Simply pluging in each possible answer and figuring out if there is a contradiction.

For example, in Case 3.3 (nnyn):

Rule of Pairs tells us that A&B are telling the truth. This means either both or niether B & C are randoms. This leaves rtlr or trrl. If we test trrl, the liar think (he said the opposite) B xor C is random. This is a contradition as both are random in this case. Therefore the answer would rtlr.

So with 14/16 above cases:

All identities were found in 8 questions

However there are two problem cases...

• Case 3.4 and 3.13

To solve this we are going to ask two more questions.

Ask A Is A nor C randoms? Ask B Are A nand C randoms?

The cases are listed by a String of "y"s and "n"s, representing yes/no responses. The answers start with alien A, then B, then C's earlier answer and D's earlier answer. The results of the 16 cases:

1) nnnn: rtlr
2) nnny: rtlr
3) nnyn: trlr
4) nnyy: trlr
5) nynn:
6) nyny: rtrl
7) nyyn: trlr
8) nyyy: trlr, rtrl
9) ynnn: trrl, rtlr
10) ynny: rtlr
11) ynyn: trrl
12) ynyy:
13) yynn: trrl
14) yyny: rtrl
15) yyyn: trrl
16) yyyy: rtrl

With 4 exceptions (we'll get there soon), all the results are a single answer, therefore giving you the correct answer. For example:

Case 3.4.16 Questions 5-8 give the possibilities of trrl, rtlr and 9-10 gives rtrl. The only one present in both is rtlr so that is the answer. All identities were found in 10 questions

But there are still exceptions:

• Case 3.4.8, 3.4.9, 3.13.8, 3.13.9

Interestingly enough, these cases are not possible. Actually, 3/4ths of the above cases are not possible because it is layed out as if 8 questions (ignoring 1-4) were asked, when in reality only 6 were asked.

• Case 3.4.8

This case is not possible because the possiblities from questions 5-8 (trrl, rtlr) do not match that from 9-10 (trlr, rtrl).

• Case 3.13.9

This case is not possible because the possiblities from questions 5-8 (trlr, rtrl) do not match that from 9-10 (trrl, rtlr).

• Case 3.4.9

This case is not possible because the answers to questions 7-8 from 3.4 (yes, yes) do not match the answers to to questions 7-8 from 3.4.9 (no, no)

• Case 3.13.8

This case is not possible because the answers to questions 7-8 from 3.13 (no, no) do not match the answers to to questions 7-8 from 3.13.9 (yes, yes)

So in the worst case scenario:

All identities were found in 10 questions

Edit 1

I just thought that my answer was a complete mess, so I took out a lot of explanations so that it makes more sense. I also changed a few questions to make it clearer. Sorry for any previous confusion.

Edit 2

I accidentally wrote "or" & "and" instead of "nor" & "nand" in the 3.4.y subcases (maybe autocorrect's fault?😂). Credit to @hexonimo for catching this mistake, thanks.

Sorry this took me so long to write out... I've had a long week. Thanks for the great puzzle