11
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ "their language is based on the English alphabet" - will we receive their words written down, then? (After all, having different spellings doesn't make words necessarily sound different!) $\endgroup$
    – Deusovi
    Nov 14, 2022 at 13:27
  • 1
    $\begingroup$ Do questions of the form ask A: "If I were to ask B whether they are True, what would they say?" permitted or is that the kind you refer to as paradoxical? $\endgroup$
    – quarague
    Nov 14, 2022 at 16:50
  • 1
    $\begingroup$ @3m0o I have cleaned up my comment and edited your clarification into the question. Feel free to edit further to address the other commenters' queries; I don't understand them nearly well enough to incorporate them into the question! This way, anyone trying to solve the puzzle will have all the information in the question, instead of having to dig through comments for clarifications $\endgroup$
    – bobble
    Nov 15, 2022 at 1:04
  • 1
    $\begingroup$ Clarification on the gods' words for "yes" and "no": initially we have no idea what either of them is, right? (It's not that we know the words but don't know which is which.) So in particular we can't ask questions that mention those words until we have actually heard a god use them? $\endgroup$
    – Gareth McCaughan
    Nov 15, 2022 at 3:37
  • 1
    $\begingroup$ @GarethMcCaughan Yes exactly! What are you saying is correct! We initially have no idea what either of them is! So in particular we can't ask question that mention those words in their language until we have heard a god use them $\endgroup$
    – 3m0o
    Nov 15, 2022 at 11:22

3 Answers 3

8
$\begingroup$

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:

12-row chart
(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:

answer config for T and L
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!)

$\endgroup$
1
  • 2
    $\begingroup$ I didn't check that your questions work because they are a bit tangled! You got the idea anyway. If you want I can post my 3 questions, in my humble opinion they are cleaner. $\endgroup$
    – 3m0o
    Nov 15, 2022 at 17:00
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ "each question must be put to exactly one god. " This is given as a condition in the original puzzle. But , in your solution, you are asking the same person, 2 questions. $\endgroup$ May 20, 2023 at 12:11
  • $\begingroup$ By "each question must be put to exactly one god" I meant that for each (singular) question only one god will answers to you, but for any question, you can choose freely the god who will answer to you $\endgroup$
    – 3m0o
    May 20, 2023 at 15:26
-1
$\begingroup$

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!

$\endgroup$
9
  • $\begingroup$ Okay but your solution require 4 questions, I'm asking to solve the problem in 3 questions ;) $\endgroup$
    – 3m0o
    Nov 15, 2022 at 11:24
  • $\begingroup$ I have given "3 or 4" which fits with the earlier calculations. I am not sure whether Exactly "3" is going to work in every Case. Do you have such a Solution ? @3m0o $\endgroup$
    – Prem
    Nov 15, 2022 at 12:02
  • 2
    $\begingroup$ Prem : It might be possible to discover for sure which God is whom, even if you still don't know which of the two words means yes or no. In that case 3 questions would be sufficient - although I don't know how to proceed. $\endgroup$
    – Evargalo
    Nov 15, 2022 at 12:56
  • 2
    $\begingroup$ You don't need to ask the three questions to different gods. It's also possible that you can figure out the words for yes and no only in some cases, which will keep you under the 8-option limit. $\endgroup$
    – Deusovi
    Nov 15, 2022 at 13:08
  • 1
    $\begingroup$ Your "proof" also proves the original impossible. $\endgroup$
    – Deusovi
    Nov 15, 2022 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.