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, what is the minimum number of questions I need to ask to find the identities of all the 4, and what should the questions be?
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.
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?"
Case 1: 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, that is, 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.
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.