7
$\begingroup$

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.


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:

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.

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.

$\endgroup$
0
6
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ Firstly, " A thinks that they are a truthteller, B is a liar and C and D are random" . Nobody needs to think that they are a truthteller/liar or random . They are what they are and they already know who they are and what kind of a person someone else is. Secondly, I am having a bit of a difficulty completely understanding your answer. Can you also include in your answer, why, if we encounter cases 3 and 4 in my attempt, then there is no minimum number of questions that can help us establish the identities of all the 4? $\endgroup$ Aug 31 '20 at 17:08
  • $\begingroup$ "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)." Can you explain why we cannot distinguish ? $\endgroup$ Aug 31 '20 at 17:18
  • $\begingroup$ I did not understand the following lines, 1. " Replace C and D in Scenario 1 with randoms but all of their answers will be as if we are in Scenario 1" ( replace C and D with whom) ? 2. "Replace A and B in Scenario 1 with randoms" ( replace A and B with whom) ? $\endgroup$ Aug 31 '20 at 17:21
  • 2
    $\begingroup$ Maybe it is easier to understand by framing scenario 1 instead of "thinks" as "answers as though". Then the answers are consistent with two states of the world (A, B) random or (C, D) random (scenarios 2 and 3). $\endgroup$
    – tehtmi
    Sep 1 '20 at 2:13
  • 1
    $\begingroup$ In short, if ABCD are TLRR or RRTL, then, to any question, T and L will answer as they must and the R's can accidentally answer as T and L would in the other case. Both cases will give the same answer to any question. $\endgroup$
    – Florian F
    Sep 8 '20 at 16:34
1
$\begingroup$

This problem shouldn't require more than

4

questions to completely characterize the four people (or gods, or aliens, or whatever characters are in your favourite version of the problem). The crucial piece of logic that makes this and the original question much easier to answer is to ask questions such as

"If you flipped a completely random coin, would the result be heads?" We will refer to this question as $Q_1$.

This answer seems to be similar to the one for the original problem as detailed in this article but may be simpler. The rationale is as follows:

Only a random speaker can provide an answer to nondeterministic questions; a truth teller and a liar will both be speechless. In terms of computation, it can only be answered by a probabilistic Turing machine, not by a deterministic Turing machine. There are lots of other questions that fit into this paradigm, such as "If I had a randomly-shuffled deck of cards, would the top card be the ace of spades?"

We can go through the various cases, labelling the people $A$, $B$, $C$, and $D$ and the arrangements by the letters $T$, $L$, and $R$ (such as $TLRR, TRLR$, etc.). In each case, the first step is:

Ask $Q_1$ to each of $A$, $B$, and $C$. Anyone who provides you with an answer must be $R$, anyone who does not must be $T$ or $L$.

There is only one more step, which we divide into two cases for clarity. Case 1:

Only one of $A$, $B$, and $C$ is $R$; the other two must be $T$ and $L$. Then $D$ is $R$ as well. To distinguish between $T$ and $L$, ask one of them a question that is obviously true or false (e.g., "Does $2+2=4$?"), learn from their answer whether they are $T$ or $R$, and assign the remaining possibility to the remaining person. See example below.

Case 2:

Two of $A$, $B$, and $C$ is $R$; the other one must be $T$ or $L$ and $D$ must be $T$ or $L$. To distinguish between $T$ and $L$, ask one of them a question that is obviously true or false (e.g., "Does $2+2=4$?"), learn from their answer whether they are $T$ or $R$, and assign the remaining possibility to the remaining person. See example below.

Example of case 1:

Ask $Q_1$ to $A$, $B$, $C$, and get a response from $C$ (the response can be yes or no, it does not matter). Then $C$ and $D$ must be $R$. Ask $A$ "Does $2+2=4$?" If $A$ says yes, then the arrangement is $TLRR$; if $A$ says no, then the arrangement is $LTRR$.

Example of case 2:

Ask $Q_1$ to $A$, $B$, $C$, and get a response from $B$ and $C$ (the response can be yes or no, it does not matter). Then $B$ and $C$ must be $R$. Ask $A$ "Does $2+2=4$?" If $A$ says yes, then the arrangement is $TRRL$; if $A$ says no, then the arrangement is $LRRT$.

$\endgroup$
2
  • 3
    $\begingroup$ We had a lot of discussion about this back in August but one of the implicit assumptions of the question is that all yes/no questions are answerable with 'yes' or 'no'. In the original linked problem, they allow this by saying each individual is a "god" and so would be able to predict the outcome of a coin flip. $\endgroup$
    – hexomino
    Mar 8 at 22:12
  • $\begingroup$ Ah, I see. This seems like an extra assumption, but it definitely makes the puzzle more intricate. Being a "god" does not help if one asks a question requiring truly random elements (e.g. a platonic concept of a coin flip). $\endgroup$ Mar 10 at 0:11
0
$\begingroup$

I know it's 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 guarantee 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 disclaimer acknowledging 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: logic operators description

Explanation:

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 plugging 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 neither 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 contradiction 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 laid 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 possibilities 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 possibilities 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. Credit to @hexonimo for catching this mistake, thanks.

$\endgroup$
15
  • $\begingroup$ @Ankit You say, for example, the answer set 3.4.9 is not possible but, of course, it is possible. It can happen in both the TRRL and RTLR cases. It doesn't matter that the answers don't match. I don't understand the line of reasoning here. $\endgroup$
    – hexomino
    Sep 7 '20 at 22:54
  • $\begingroup$ You seem to be arbitrarily ruling out cases as "not possible" by comparing to other cases, not sure why you would do this. $\endgroup$
    – hexomino
    Sep 7 '20 at 23:44
  • 1
    $\begingroup$ Your first table of 16 possibilities looks good, but the second one doesn't. It's only used for in case 3.4 and 3.13, right? Those two end with "yy" and "nn", so why are there any entries in that second table that end with "yn" or "ny"? Also, case 8 in the second table should be trrl or rtlr, and case 9 should be trlr or rtrl. You've only got two cases for which you're generating subcases, so at this point it should be simpler to handle them separately. $\endgroup$
    – Rob Watts
    Sep 8 '20 at 3:46
  • 1
    $\begingroup$ @Ankit I hope you're not spending a lot of time trying to find questions to make this work. I still believe hexomino's answer is correct in that you will always find a case where you can't tell between the two possibilities. Maybe now that you've spent some time working on this, you should review that answer and see if it makes more sense to you now. $\endgroup$
    – Rob Watts
    Sep 9 '20 at 16:00
  • 2
    $\begingroup$ The comments here are getting lengthy; may I recommend we move these comments to a chat where the refinement to Ankit's answer can continue? We can undelete the comments that have already been tidied up as well, so the back-and-forth contributions are not lost. Let me know. $\endgroup$
    – Rubio
    Sep 10 '20 at 12:33

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.