You are the most eligible bachelor in the kingdom, and as such the King has invited you to his castle so that you may choose one of his three daughters to marry. The eldest princess is honest and always tells the truth. The youngest princess is dishonest and always lies. The middle princess is mischievous and tells the truth sometimes and lies the rest of the time.
As you will be forever married to one of the princesses, you want to marry the eldest (truth-teller) or the youngest (liar) because at least you know where you stand with them.
The problem is that you cannot tell which sister is which just by their appearance, and the King will only grant you ONE yes or no question which you may only address to ONE of the sisters. What yes or no question can you ask which will ensure you do not marry the middle sister?
Let’s label the sisters UNITY, NEGATE, and RANDOM; being the eldest, youngest and middle sister respectively. These names reflect the operation each of them performs on the truth — UNITY simply reports the truth, NEGATE inverts the truth and RANDOM’s answers will be either true or false.
So: the problem is that we want a question that when asked to the middle sister will give a different answer from the other sisters – regardless of whether she tells the truth or not.
This is not a million miles from the two brothers problem: there are two doors, behind one door is certain death (D), the other is fabulous wealth (W). The doors are guarded by two brothers – one always tells the truth, the other always lies. Again, we are given one question. We ask:
Which door would your brother tell me contains fabulous wealth?
The liar would know that his brother would tell the truth, and would then lie about it. (let’s say door one is fabulous wealth). The truth teller would tell you that door one contains fabulous wealth, the liar would lie about that and tell you that his brother would tell you to choose door two.
The truth teller would konw that his brother would lie, and so would faithfully report that lie. The liar would tell you that door two contains fabulous wealth (which is a lie), and the truth teller would honestly tell you that fact.
Both brothers would answer door two. We would then choose door one (i.e. the opposite of what we are told)
Let’s call the question Q, and the real answer A. Brother one tells the truth, so
B1(Q) = A
Brother two always lies, so
B2(Q) = !A
or..
B2(Q) = !B1(Q)
However, our question is carefully chosen so that it is a question about what the other brother would answer to another question. We might call it a meta-question. Let’s call M our meta-question and N1 and N2 our meta-question answers (we need N1 and N2 because it’s a different answer depending on who we ask). Brother one will tell the truth..
B1(M) = N1
But, N1 is the answer that the other brother would give to our real question, Q.
B1(M) = B2(Q)
B1(M) = !A
Similarly, brother two will lie…
B2(M) = !N2
B2(M) = !B1(Q)
B2(M) = !(A)
Demonstrating in symbols that both brothers will answer !A when asked what there brother would answer to Q.
Now. How can we do a similar thing to the three sisters? S1(), S2() and S3() are the operations of the youngest, middle and eldest sister respectively on a question Q with true answer A.
S1(Q) = !A
S2(Q) = RAND(A,!A)
S3(Q) = A
We want to ask a single question, we know it must be a meta-question as we need to get the sisters to reveal their own knowledge to us about the sisters we are not questioning.
Now – we must face the problem that S2() never tells us anything useful. Given that she is the only one we don’t want to marry, we must choose our question such that it doesn’t matter what she answers, and the answers the other two give does tell us something. How about:
- Assume we’re asking a question of sister A and the two remaining sisters are B and C (and we don’t know which is which)…
Q: Is your sister B younger than your sister C? (for convenience we will list the answer as if it were: which of your other two sisters is younger)
(A=1, B=2, C=3) S1(Q) = C 3 (we want to marry A or C)
(A=1, B=3, C=2) S1(Q) = B 3 (we want to marry A or B)
(A=2, B=1, C=3) S2(Q) = B|C 1|3 (we want to marry B or C)
(A=2, B=3, C=1) S2(Q) = C|B 3|1 (we want to marry B or C)
(A=3, B=1, C=2) S3(Q) = B 1 (we want to marry A or B)
(A=3, B=2, C=1) S3(Q) = C 1 (we want to marry A or C)
From this, we can see that if we always married whomever we were told was the youngest of the other two, we are guaranteed to never end up with sister two. The youngest sister will always tell us that her oldest sister is the younger, the oldest sister will always tell us that the youngest sister is younger. The middle sister will tell us that either the eldest or the youngest is the younger.
The reason we were able to pull this trick is because we know in advance that the youngest sister always lies. This lie compensates for the difference in the questionee, since in sister one’s case we want the eldest sister, and in sister three’s case we want the youngest sister. The fact that she lies means that we can ask the same question and still get an answer we want.
There are three gods, True, False and Random. True will always answer truthfully, False will always lie, and Random will answer your questions randomly. The gods are standing before you, but you do not know which is which. Your task is to determine the identity of the gods, by asking them three questions. To make matters worse, the gods will answer your questions only with ‘da’ or ‘ja’, which mean true and false in their own language, but you don’t know which is which.
Now we’re getting into very difficult territory. Let’s call them T, F and R.
First let’s check that the solution is possible… There are three gods and three identies, plus two words and two meanings.
JA DA G1 G2 G3
--------------
Y N T F R
Y N T R F
Y N F T R
Y N F R T
Y N R T F
Y N R F T
N Y T F R
N Y T R F
N Y F T R
N Y F R T
N Y R T F
N Y R F T
This is what we would expect, there are 3! permutations of three items, and 2! arrangements of two items. 3! * 2! = 3*2*1 * 2*1 = 12. We have three questions available two us. There are two answers to each question, 2^3 = 8. Hmmm. However, we are only asked to identify the gods, not to translate their language. Therefore the problem is still soluble, because we actually only have the six arrangements of gods to contend with, if we sometimes learn the language then great, if we don’t we don’t care.
Let’s first try the puzzle having them speak English (i.e. no ja and da).
Q1: Which of the others will tell me the truth less often? We ask A and B, C are the other gods. (obviously we’d phrase this as a yes/no question). Paint the god you ask red.
(A=T, B=F, C=R) T(Q1) = B F
(A=T, B=R, C=F) T(Q1) = C F
(A=F, B=T, C=R) F(Q1) = B T
(A=F, B=C, C=T) F(Q1) = C T
(A=R, B=T, C=F) R(Q1) = B|C T|F
(A=R, B=F, C=T) R(Q1) = C|B F|T
Whatever we are told, that god cannot be Random. The above question is magical. Look what it did: when asked of a god who is not Random you are told the other god that is not Random. Now that we have found a god that is not Random we ask them Q1. So: Q2 is Q1, but with less possible cases:
(A=T, B=F, C=R) T(Q2) = B F
(A=T, B=R, C=F) T(Q2) = C F
(A=F, B=T, C=R) F(Q2) = B T
(A=F, B=T, C=R) F(Q2) = C T
Paint the god you ask blue. We have now found Random, since we know that the answer we are given is not-Random. If the blue god answered red, then the unpainted god is Random. Paint an R on him. If the blue god answered unpainted then the red god is Random. To recap:
We have found Random and he is not painted blue
The blue god is either True or False. Let’s switch god-speak back on…
Q3: Does ‘ja’ mean ‘yes’?
(A=T, ja=yes) ja
(A=T, ja=no) ja
(A=F, ja=yes) da
(A=F, ja=no) da
This is extra sneaky. We’ve relied on the fact that we’re asking a question about the language the question is being answered in. In more detail: if we ask the True god does ‘ya’ mean ‘yes’ and ‘ya’ does mean yes, then he will answer ‘yes’ (‘ya’). Similarly, if ‘ya’ means ‘no’, then True answers ‘no’ (‘ya’). i.e. he answers the same regardless of whether ‘ya’ means yes or no. False, on the other hand, always lies, so he always answers ‘da’, regardless of the actual meaning. So, we now know who is painted blue. And by extension, the other remaining unidentified god.
So; clearly we ar left with one problem: Q1 and Q2 relied on having the answer in English, not in god-speak. Q3 relied on having the answer in godspeak, which is fine.
Can we modify Q1 so that it works even when we don’t know the polarity of the answer? Yes. We can do so by using the trick that question three uses. It makes Q1 more complicated though. Let’s imagine that the gods are arranged in a line, we don’t know which is which. We ask the middle god:
Q1: I require you to exclusive-OR the answer to the following two questions
– a) Will the god to my left tell me the truth less often than the god to my right? – b) Does ‘ja’ mean ‘yes’?
So – we are still getting one answer, but that answer is obtained by combining the answer to two other questions.
(B=T, A=F, C=R, ja=no) T(Q1) = false XOR false = false = 'ja' (A == F)
(B=T, A=F, C=R, ja=yes) T(Q1) = false XOR true = true = 'ja' (A == F)
(B=T, A=R, C=F, ja=no ) T(Q1) = true XOR false = true = 'da' (C == F)
(B=T, A=R, C=F, ja=yes) T(Q1) = true XOR true = false = 'da' (C == F)
(B=F, A=T, C=R, ja=no ) F(Q1) =! true XOR false = false = 'ja' (A == T)
(B=F, A=T, C=R, ja=yes) F(Q1) =! true XOR true = true = 'ja' (A == T)
(B=F, A=R, C=T, ja=no ) F(Q1) =!false XOR false = true = 'da' (C == T)
(B=F, A=R, C=T, ja=yes) F(Q1) =!false XOR true = false = 'da' (C == T)
(B=R, A=T, C=F, ja=no ) R(Q1) = 'ja' | 'da' (A|C == T|F)
(B=R, A=T, C=F, ja=yes) R(Q1) = 'ja' | 'da' (A|C == T|F)
(B=R, A=F, C=T, ja=no ) R(Q1) = 'da' | 'ja' (C|A == F|T)
(B=R, A=F, C=T, ja=yes) R(Q1) = 'da' | 'ja' (C|A == F|T)
The trick of Q3 was to use the meaning of ‘ja’ to modify the answer. It was self inverting. The same trick is used here. An XOR operation inverts the answer when ‘ja’ is yes. thus it doesn’t matter whether ‘ja’ means yes or not – it’s effect has been cancelled out. From here we can proceed as above.
We use the answer to this question as follows:
- ‘ja’ means the god on the left is NOT Random
- ‘da’ means the god on the right is NOT Random
Once we have one god who is not random, we ask them the question again to find out the other god that is not random. Now we know who random is. Q3 then allows us to find out if this god is True or False.