One truthteller/liar and one random person

Question

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.

Answer 1

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.

Answer 2

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.

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

The number of questions to guarantee is:

2 questions

So let's 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.

Answer 3

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.

Answer 4

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!

Answer 5

Even if Alice and Bob are omniscient, the number of questions required is:

1

The strategy is:

Ask one of them, "Is it the case either that you are a truthteller and you will answer "No" to this question, or that you are a liar and you will answer "Yes" to this question?"
Alice cannot answer this question with "Yes" or "No" - e.g. if she is a truthteller and answers "Yes" then she must be a liar, which is a contradiction; if she is a liar and answers "Yes" then she must be a truthteller, which is a contradiction; and so on.
So if the person you ask replies "Yes" or "No" then they are Bob; otherwise they are Alice.

Edit: Ankit suggests an interpretation where you are killed if you ask a question which the respondent cannot answer. In this situation we can instead ask:

'Of the statements "You are a truthteller", "You will answer this question with the word Yes", and "You will kill yourself immediately after answering", are either exactly one or exactly three of them true?'
If you ask Alice this question, then regardless of whether she answers Yes or No, she is forced to immediately kill herself.
(Of course, if we ask Bob, he might also immediately kill himself to trick us - but if the aliens are willing to commit suicide to prevent us identifying them, they could simply do so before any questions are asked.)