5
$\begingroup$

You come across two peculiar aliens: Alice and Bob. You know the following about them:
-Alice is either a "truthteller" (she always tells the truth) or a "liar" (she always lies).
-Bob is a "random" (he randomly says yes or no).

For whatever reason, you must figure out who is who by individually asking them questions. What is the optimal strategy (fewest questions) to guarantee that you know which one is Alice and which is Bob?

You can assume the following:

  • Alice and Bob can only reply Yes or No
  • Alice and Bob look/sound exactly the same
  • Bob knows if Alice is a truthteller or liar
  • Alice knows that Bob is a random
  • Alice and Bob can hear questions directed at the other, as well as their answers.

Note that this question has been edited multiple times to clarify the author's intent. Please keep this in mind when reviewing answers as some may have been added when the puzzle was new.

$\endgroup$
  • 1
    $\begingroup$ Two things, firstly are the two people only able to answer yes or no, or can they for instance say I don't know? And secondly does the non-random know whether the random will answer truthfully or not, or do they not know $\endgroup$ – Beastly Gerbil Aug 27 at 23:53
  • 2
    $\begingroup$ They only answer yes/no . Ask something whose answer is not yes/no and you are killed. The random can say yes or no randomly. Nobody can predict what he will say. This is known to the non-random. Btw, my question is inspired by the hardest logic puzzle ever. This is an excellent video that explains the question and then the solution of the hardest logic puzzle ever : youtu.be/LKvjIsyYng8 $\endgroup$ – Hemant Agarwal Aug 28 at 0:01
  • 2
    $\begingroup$ @HemantAgarwal Please edit the question with the fact that Bob says "yes" or "no" at random. $\endgroup$ – NomadMaker Aug 28 at 5:59
  • 2
    $\begingroup$ @Ankit Yes, I agree with you, and the way the question is phrased, your answer is correct but OP seems to be contradicting things in the comments. $\endgroup$ – hexomino Aug 28 at 16:37
  • 1
    $\begingroup$ Yes, Hemant has contradicted himself multiple times... Thanks. @hexomino $\endgroup$ – Ankit Aug 28 at 16:39
16
$\begingroup$

Update

Please read first: The question has had a recent edit which, although looks similar, is a subtle change which makes a big difference. I believe my answer below is the correct answer to the question in its current form.

However, the question previously stated that Bob randomly tells the truth or lies, that is to say, Bob cannot make a series of statements which result in a logical paradox. This is different to Bob being able to say "yes/no" at random where logical paradoxes are possible.

To see the answer to the question in its original form, please refer to Ankit's excellent answer.

To see a nice lateral-thinking solution, see user3294068's answer.


I think that the answer is

There is no minimum

Reasoning

We'll consider the two scenarios separately.

Suppose, first that Alice is a truthteller.
Now, additionally, suppose that all of Bob's answers will be as if Bob is a truthteller and Alice is a random (because Bob answers randomly, this can always happen by chance for any finite number of questions).
Let's say I come up with a strategy to distinguish the two people (person 1 and person 2) in $N$ questions. Some of these questions will be to person 1, the others will be to person 2, and at the end I will have a set of "yes/no" responses $a_1, a_2, \ldots, a_N$.
Now, let's go back to the beginning of the questions and swap person 1 with person 2. Ask the same $N$ questions again. The responses $a_1, a_2,\ldots, a_N$ will be exactly the same as before because Bob and Alice mirror each other.

Suppose instead that Alice is a liar.
In this case, additionally, suppose that all of Bob's answers will be as if Bob is a liar and Alice is a random (because Bob answers randomly, again, this can always happen by chance for any finite number of questions).
Using the argument from before, any set of $N$ questions will have the same set of answers when we swap the two answerers. Therefore, there will be no way to distinguish them.

Notes

The difference here between this and The Hardest Logic Puzzle Ever is that, in that problem, there is an inherent asymmetry between the liar/truthteller group and the random group (2:1) which we can exploit whereas here, there is a symmetry and it seems that for any $N$ it would be possible to switch the labels of the participants in some scenarios so that the logic is consistent.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Even though there is no minimum, there can still be an optimal strategy that terminates with probability 1. As an example, rot13(Nygreangryl nfx Nyvpr naq Obo jurgure be abg gurl ner n gehgugryyre. Gur svefg bar jub fnlf ab vf gur enaqbz.) Not sure if this is optimal, though... $\endgroup$ – Jeremy Dover Aug 28 at 2:07
  • $\begingroup$ Unfortunatly, this is incorrect. There is an optimal solution. Please read my answer. @JeremyDover & @ hexonimo $\endgroup$ – Ankit Aug 28 at 2:43
  • 1
    $\begingroup$ @Ankit Ah, yes, I see where I went wrong. $\endgroup$ – hexomino Aug 28 at 8:53
  • $\begingroup$ The clarification by OP indicates that this is the correct answer: "The random can say yes or no randomly" $\endgroup$ – user3294068 Aug 28 at 14:19
  • $\begingroup$ @user3294068 Yes, I see what you mean. The information in the comment seems to contradict the information in the question. Strictly, as the question is currently written, my answer is wrong so I will leave it as is and ask OP to clarify. $\endgroup$ – hexomino Aug 28 at 15:22
16
$\begingroup$

DISCLAIMER:

THIS QUESTION HAS BEEN CHANGED IN ORDER TO MAKE MY ANSWER INCORRECT!

Previously the question said "Bob is a random (randomly tells the truth or lies)". 15 hours after my answer (and after a discussion in the comments) the question was changed to say "Bob is a random (he randomly answers yes or answers no)". This can be verified by reviewing the timeline and content of the question's edits.

Firstly, This is against the rules of Stack Exchange and I will be reporting this question. Secondly, it doesn't even make sense, as in this case the truth teller should always say "Yes" and the liar should always say "No"... Hemant took a really great puzzle and spoiled it.

But that being said, here is my answer (to the original):

The number of questions to guarantee is:

2 questions

So lets call them X and Y since we don't know their identities.

Strategy:

Ask the following questions to X: "Are you a random?" Then ask "Does the truthfulness of your previous answer match the truthfulness of your answer to this question?"

  • In short, the answers that X gives indicate the following:

(Yes, No) = liar (Alice); (No, Yes) = truth teller (Alice); (No, No) = random (Bob); (Yes, Yes) = random (Bob)

Full explanation of why this works:

  • If X is Alice (truth teller/liar):

The truthfulness of the the truth teller/liar is always the same. A truth teller always tells the truth, a liar always lies. That means the outcome for Alice is one of the following depending on if she is the liar or not:

Truth Teller Alice: "Are you a random?" No (truth) "Does the truthfulness of your previous answer match the truthfulness of your answer to this question?" Yes (truth; the first answer was true, and so is the second == consistent truthfulness between the two answers which makes the "Yes" the truth)

Liar Alice: "Are you a random?" Yes (lie) "Does the truthfulness of your previous answer match the truthfulness of your answer to this question?" No (lie; the first answer was a lie, the second is now true == inconsistent truthfulness between the two answers which makes the "No" a lie)

  • If X is Bob (the random):

There are multiple permutations possible for Bob due to the fact that his answers are random. Let's go case by case.

Case 1: "Are you a random?" Yes (X intends to tell the truth) "Does the truthfulness of your previous answer match the truthfulness of your answer to this question?" Yes (X intends to lie; inconsistent truthfulness between the two answers which makes the "Yes" a lie)

Case 2: "Are you a random?" Yes (X intends to tell the truth) "Does the truthfulness of your previous answer match the truthfulness of your answer to this question?" Yes (X intends to tell the truth; consistent truthfulness between the two answers which makes the "Yes" true)

Case 3: "Are you a random?" No (X intends to lie) "Does the truthfulness of your previous answer match the truthfulness of your answer to this question?" No (X intends to lie; consistent truthfulness between the two answers which makes the "No" a lie)

Case 4: "Are you a random?" No (X intends to lie) "Does the truthfulness of your previous answer match the truthfulness of your answer to this question?" No (X intends to tell the truth; inconsistent truthfulness between the two answers which makes the "No" the truth)

Conclusion:

We were tasked with finding Bob the random. If X is a truth teller/liar, then Y is the random. If X is the random, we don't care what Y is. (And if you want to find what Y is, ask "Does 1+1=2").

Proof that this is optimal:

As there are 3 people and only 2 answers sets, you cannot decipher. While it is true that you could try to map truth teller and liar to one answer, and random to the other answer, this only works half of the time. The only way to do this would be to ask a question where if the random tries to strategically lie, he will get stuck in a paradox. However, there is no way to do this without forcing a paradox from either the truth teller or the liar. So it would work half of the time but fail the other half.

Very good puzzle, I thoroughly enjoyed it.


EDIT 1:

Response to comments: You guys are not understanding my point... Bob is still answering randomly. There are two ways of thinking of it.

1) Bob cannot create a logical paradox... It is not even physically possible to create a paradox as shown in Case 2 above. But regardless, the question says "randomly tells the truth or lies". A paradox is neither a truth nor a lie so Bob does not even have that ability. Therefore there was only one answer choice for the constant truthfulness in the first place. Randomly picking from one choice means you are "forced" so pick that...

2) As explained by Jaap Scherphius's comment, it is not physically possible to create a paradox. Bob doesn't randomly say yes or no, he randomly tells the truth or lies. Therefore the analogy to flipping a coin and saying yes/no is invalid. Rather it's like you flip coins for true/false for both the first and second answer. (truth, truth) --> (yes, yes); (truth, lie)-->(yes, yes); (lie, truth) --> (no, no); (lie, lie) --> (no, no) None of these scenarios are paradoxical.


EDIT 2:

A response to the "Bob can't tell the future" argument.

Originally I had the order of the questions switched; "Are you a random?" was originally the second question. Saying that Bob must reply "I don't know" when asked "Does the truthfulness of your previous answer match the truthfulness of your answer to this question?" is like saying if someone asks "Are you going to eat out for dinner", you must say "I don't know" because you might get hit by a car and never reach the restaurant. And it's not even that, because there's nothing stopping Bob from telling the truth/lying. So it works. However, as this entire confusion can be averted by switching the questions, I edited it to do that. This was originally suggested by Jaap.

Old Cases:

(Yes,No) = truth teller (Alice); (No,Yes) = liar (Alice); (No, No) = random (Bob); (Yes, Yes) = random (Bob)

  • If X is not the random (Alice):

The truthfulness of the the truth teller/liar is always the same. Therefore a truth teller would respond, yes (truthfulness will be the same) and then no (I am not a random). A liar would say no (truthfulness will not be the same) and then yes (I am a random).

  • If X is the random (Bob):

The first question can be either yes or no so lets go case by case.

Case 1: X answered yes (truthfulness will be the same), which is true. X told the truth, so the next answer must also be true. X would reply Yes (I am the random) to the second question.

Case 2: X answered yes (truthfulness will be the same), which is a lie. As the first answer was a lie, X must tell the truth on the next question. Again X would reply Yes (I am the random) to the second question.

Case 3: X answered no (truthfulness will not be the same), which is true. This means their next answer would be a lie, so they would say no (I am not the liar) to the second question.

Case 4: X answered no (truthfulness will not be the same), which is lie. This means the truthfulness must be the same: a lie. They would say no (I am not the random) to the second question.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Do we know whether rot13(Obo xabjf ubj gehgushy ur jvyy or arkg)? $\endgroup$ – Graylocke Aug 28 at 2:32
  • 7
    $\begingroup$ Very nice. It all depends upon the fact that Bob does not randomly answer yes or no, but randomly tells the truth or lies, and even keeps to that principle retrospectively. You could swap the questions around, and then it wouldn't need to be retrospective - only one possible answer to the second question will be a definite truth or falsehood while the other possible answer will be neither. $\endgroup$ – Jaap Scherphuis Aug 28 at 3:26
  • 1
    $\begingroup$ @Ankit I think the bit I am confused about is rot13("Nf gur svefg nafjre jnf n yvr, K zhfg gryy gur gehgu ba gur arkg dhrfgvba." Vs ur vf gehyl enaqbz gurer vf ab "zhfg" orpnhfr ur qbrfa'g xabj gur nafjre gb gur dhrfgvba..?) $\endgroup$ – Graylocke Aug 28 at 4:09
  • 2
    $\begingroup$ The problem is that Bob is a random and can use "yes" or "no" randomly: "The random can say yes or no randomly." from a comment. $\endgroup$ – NomadMaker Aug 28 at 5:57
  • 1
    $\begingroup$ @Graylocke lol don't worry, i understand, believe me i doubted myself like three or four times and erased my answer thinking "hold up, this doesn't make sense." It is very confusing to begin with and I am not very good at explaining myself, which added to the confusion lol. I must say-- thanks for disagreeing with me politely and trying to understand me rather than reading it with the preconcieved notion that I'm wrong. There have been a lot of people writing rude comments (they got flagged and deleted), and I really appreciate & respect someone like you who has consistantly been polite. $\endgroup$ – Ankit Aug 31 at 4:46
5
$\begingroup$

Depending on the details of how the Random answers, you can find out which is which with 1 question:

If the Random always just says "yes" or "no", at random, regardless of the question, then you can ask something like "Did I eat tacos for lunch?". The Random will randomly say either "yes" or "no". The true answer is "I don't know", so this would qualify as a question that will get you killed if you asked the other one. You may die soon, but until then, you'll know who the Random is.

Similarly,

If the Random always lies or tells the truth, but no one, not even them, can predict which, then you can use Ankit's first question "Will the truthfulness of your answer to the next question be the same as your answer for this question?" The truthteller/liar will say "yes/no". The Random would have to say "I don't know", but that's not a yes/no answer, so you'll die.

Either way,

you get the information with the answer to one question. You might die soon, but you will briefly know the answer.

However,

If you need to survive the process, then Hexomino's answer is correct.

| improve this answer | |
$\endgroup$
  • $\begingroup$ This answer is incorrect for multiple reasons. 1) The random will not say I don't know, because when they say that answer, they are deciding what they will do on the next question. 2) You can't simply ask a question that someone doesn't know. Thats instant death... $\endgroup$ – Ankit Aug 28 at 16:12
  • 1
    $\begingroup$ In the comment on the question, you clarify: "Nobody can predict what he will say." Since the random is somebody, that means they also cannot predict what they will say. Hence it states they cannot decide ahead of time whether they'll tell the truth, as if they did, they could then predict whether they would tell the truth. $\endgroup$ – user3294068 Sep 8 at 15:06
1
$\begingroup$

Jeremy Dover left a great comment that inspired this answer. I am only interpreting the question differently than he did, which very slightly changes the answer. He indicated that there is no minimum.

For history's sake, at the present moment the puzzle states: What is the optimal strategy (fewest questions) to guarantee that you know which one is Alice and which is Bob?

My interpretation: a "question" is defined as one singular query. But asking it more than once is still a single question :)

First up - the answer with the original version of "Bob"

Originally Bob could tell the truth or lie randomly for each question he was asked.

You can do it in 1 question (as defined above).

Ask one of the aliens "Are you the truth teller?". If the answer is "yes" ask the other alien. Keep asking the question, switching aliens each time, until the answer is "no". Whoever responded "no" is Bob! This is because Bob is saying he is not the truth teller, which is the truth. When he says "yes", he is lying.

Let's go through the possible outcomes where the aliens are represented by "left" and "right":

Case 1: Left alien says "no". Left alien can't be Alice, she wouldn't be telling the truth as the truth teller, and she wouldn't be lying as the liar. So it has to be Bob.

Case 2: Left alien says "yes". Left alien could be anyone. Right alien responds "no". By the same logic as Case 1, we have found Bob.

Case 3: Left alien says "yes". Right alien says "yes". Left alien says "yes" .... this happens N times until the left alien says "no". Hello Bob!

Case 4: Same as Case 3, only the right alien says no. Right alien is Bob.

The answer with the current version of "Bob"

Now Bob just responds "yes" or "no" to each question. He could be lying, truthful, intent no longer matters.

With the same definition of "question" above, the answer is the same. Alice is the key. She can't say "no" because she would be lying if she was a truth teller, and she would be telling the truth if she was a liar. She can only say "yes". So continue asking until you hear "no", and bingo!

| improve this answer | |
$\endgroup$
  • $\begingroup$ I think we all know that this is not what asking a question is... $\endgroup$ – Ankit Sep 10 at 14:58
  • $\begingroup$ @Ankit It wasn't clear in the puzzle, and I have seen plenty of riddles with sly interpretations. I'm pretty pleased with it, but thanks for the input. $\endgroup$ – mjjf Sep 10 at 17:24

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.