The Fourth Hardest Logic Puzzle Ever

Question

This is a beautiful variant of "The Hardest Logic Puzzle Ever". I learned it in high school math class a while ago. (I do not know if my teacher invented this variant.) I know the solution but I want to share with you.

Three gods A, B, and C are called, in no particular order, True, False, and Xor. True always speaks truly, False always speaks falsely, while Xor speaks by xor in his head the answer of True and False if the question asked of him had been asked of the other two. For example, if we ask Xor: "Are you True?" then if the question had been asked of True, he would have answered "Yes", the same for False, hence Xor answer "No". In other words, if the answers of true and false were in agreement Xor answer "No", otherwise Xor answers "Yes". Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English; but will answer all questions in their language, in which the words for yes and no you don't know a priori. However, you know that their language is based on the English alphabet, so they are distinguishable words.

No "paradoxical" question is allowed.

Answer 1

First, a bit of information-theoretic analysis:

We have three bits of information to work with. We want to distinguish between six arrangements, which takes log₂(6) bits - around 2.58ish. If we wanted to tell which word was "yes" and which was "no", we'd need another bit of information, which we don't have.
This is interesting! It means that, whatever strategy we choose, we won't always be able to tell which answer is yes and which is no - that would distinguish between twelve different scenarios, and we only have 8 possible outcomes.

This means that to construct an answer, we will have to actively hide the information of which word means what. We can't let ourselves figure that out, because if we do, it means we've wasted a bit and can't distinguish between the 6 orderings.

And that has a bizarre implication: we cannot start with a question that doesn't refer to their language! If we did, then we would be able to figure out whether that answer was "yes" or "no" simply by figuring out what the first answer should've been.

So, how can we ask a question at all with that restriction?

The key is this: "their language is based on the English alphabet, so they are distinguishable words." This means that we can still ask questions about the words, like "does your word for 'yes' start with a vowel"!

...Of course, that question is useless if both words start with a vowel, or if neither do. We need a way to make sure that doesn't happen - so we'll have to compare the words to each other. And one way to do this is to use alphabetical order! We can ask whether the word for yes comes before the word for no alphabetically. If we use the trick of XORing our intended question with "does 'yes' come before 'no', then we can extract information without accidentally revealing which is which.

---

This is the point where I stopped looking for a 'clean' solution, and went for the more algorithmic method. I started with a diagram of one possible setup for answers:

(Note that the columns on the right are for the three questions, which will all be asked to the same god.)

Here, I chose to have "early-late" encode the liar, "late-early" encode the truthteller, and two of the same answer encode Xor.

And from here, I just bashed out a question that would give the appropriate answers.

For question 1, one possible configuration that will lead to the answers we want is:

So, we can use this table to build a question - simply force the truth-teller and the liar to answer the questions appropriately.

Question 1 (to god A): What is the result of evaluating the following?
(You are the liar AND the alphabetically-earlier word means 'true') OR (You are the truth-teller AND you are god A AND the alphabetically-earlier word means 'false') OR (You are the truth-teller AND you are god B)

For question 2, we simply get them to invert their answers in the cases where god A isn't XOR:

Question 2 (to god A): What is the result of evaluating the following?
(You are the liar AND the alphabetically-earlier word means 'false') OR (You are the truth-teller AND you are god A AND the alphabetically-earlier word means 'true') OR (You are the truth-teller AND you are god B)

Now, if we got two different answers, we know the first god's identity, and it's not Xor: it's [comparatively] easy to construct a question that tells you which way around the other two are. Say, something like...

Question 3a (to god A): What is the result of evaluating the following?

(You are the liar) XOR (the earlier word means 'true') XOR (B is Xor)

Here, the early word indicates "God B is not Xor" and the later word indicates "God B is Xor".

If we got two of the same answer, we know that the first god is Xor. Then, you can just get the other word from them.

Question 3b (to god B): What is the result of evaluating the following? (You are the liar XOR the later word means 'true')

Here, a later result means the configuration is Xor-False-True; an earlier result means the configuration is Xor-True-False.

And we've done it - that distinguishes between all six configurations! (And as a bonus, you never get all three of the same answer, so you always hear both of the words!)

Answer 2

Here my solution

Questions 1 and 2:

Questions 1 and 2 are asked to the same god, let's say god A. Let's denote with the symbol $<$ the lexicographic order. And let's say without loss of generality that the two words used by the gods are $X$ and $Y$. Note that we have $X<Y$ independently of their meaning.

Question 1: the word you use to say "yes" is smaller in the lexicographic order than the word you use to say "no"?

Question 2: the word you use to say "no" is smaller in the lexicographic order than the word you use to say "yes"?

Now let's see the different cases

Let's suppose that $X=$yes and $Y=$no. Then Yes < No

True answer $X$ to the first question and $Y$ to the second one.
False answer $Y$ to the first question and $X$ to the second one.
Xor answer $X$ to the first question and $X$ to the second one.

Let's suppose that $X=$no and $Y=$yes. Then No < Yes, but as before
True answer $X$ to the first question and $Y$ to the second one.
False answer $Y$ to the first question and $X$ to the second one.
Xor answer $Y$ to the first question and $Y$ to the second one.

Let's then denote by $R_1$ and by $R_2$ the answers we get by the first and the second question respectively, then we have three cases scenario:
Case 1) If $R_1 < R_2 $ then the god A is True.
Case 2) If $R_2 < R_1 $ then the god A is False.
Case 3) If $R_1 = R_2 $ then the god A is Xor.

Now the third question

In the following, we denote by $R$ any answer we heard in the previous questions and by $R_3$ the answer we will hear in the third question.

In case 1) A is True, then we ask the god A: "If I would ask you 'the god B is False?' You will tell me $R$?" If $R_3=R$ implies that B is False and C is Xor
If $R_3 \neq R$ implies that C is False and B is Xor

In case 2) A is False, then we ask the god A: "If I would ask you 'the god B is True?' You will tell me $R$?" If $R_3=R$ implies that B is True and C is Xor
If $R_3 \neq R$ implies that C is True and B is Xor

In case 3) A is Xor, then we ask the god B: "If I would ask you 'the god B is False?' You will tell me $R$?" If $R_3=R$ implies that B is False and C is True
If $R_3 \neq R$ implies that C is False and B is True

Answer 3

Minimum number of questions:

Let the words be X & Y to indicate true of false: Either X=true or Y=true. This is 1 bit of information. Hence we require 1 question to get that.

Let the 3 be A B C to which we have to assign T F X which has 6 possibilities. This is between 4 & 8 hence has 3 bits of information. Hence we require 3 questions to get that.

Minimum number of questions is 1+3=4

Questions:

Ask A:

Are you False?
True should answer NO
False should answer NO
XOR should answer NO

We can then know which word is NO. Let it be X=NO, hence Y=YES.

Ask B:

Are you XOR?
True should answer NO
False should answer YES
XOR should answer YES

Case 1: If we get NO, we know B is True.
Case 2: Else we know B is False or XOR.

In Case 2:
Ask C:

Are you XOR?
True should answer NO
False should answer YES
XOR should answer YES

Case 2.1: If we get NO, we know C is True.
Case 2.2: Else we know C is False or XOR. Hence we know A is true.

Either way, we know who is True by now, with either 2 or 3 questions.
Ask True:

Is [[A or B or C, whoever is not True]] XOR?
That is the truth hence we know who is XOR, hence we know who is False.

Hence, with either 3 or 4 questions, we know what we want.

Can we achieve it with 3 questions?

We have 6 possibilities of the ordering of ABC, which need 3 bits of information or 3 YES-NO Questions. We could skip knowing X=YES or X=NO, which will save 1 question hence it looks like 3 is possible .... But NOT!

Contrary to OP claiming that 3 is possible, I will give a "Proof" that it is not possible. When OP reveals the correct solution, I will revisit this "Proof" to check where I went wrong!

Let us ask 3 questions (to whichever characters, in which ever order) and hear the responses.

Suppose we hear XXX, then it could mean either YYY or NNN which is the exact same response YYY which could mean either YYY or NNN.

Suppose we hear XXY, then it could mean either YYN or NNY which is the exact same response YYX which could mean either YYN or NNY.

Suppose we hear XYX, then it could mean either YNY or NYN which is the exact same response YXY which could mean either YNY or NYN.

Suppose we hear YXX, then it could mean either NYY or YNN which is the exact same response XYY which could mean either NYY or YNN.

In short, we have only 4 Possible responses, but we have to choose 1 out of 6 Possibilities.

IMPOSSIBLE!