{"id":468,"date":"2008-10-08T01:00:00","date_gmt":"2008-10-07T23:00:00","guid":{"rendered":"https:\/\/www.fussylogic.co.uk\/blog\/?p=468"},"modified":"2012-08-31T09:22:20","modified_gmt":"2012-08-31T08:22:20","slug":"three-gods-puzzle","status":"publish","type":"post","link":"https:\/\/www.fussylogic.co.uk\/blog\/?p=468","title":{"rendered":"Three Gods Puzzle"},"content":{"rendered":"
\n

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.<\/p>\n

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.<\/p>\n

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?<\/p>\n<\/blockquote>\n

\n

Let\u00e2\u20ac\u2122s 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 \u00e2\u20ac\u201d UNITY simply reports the truth, NEGATE inverts the truth and RANDOM\u00e2\u20ac\u2122s answers will be either true or false.<\/p>\n

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.<\/p>\n

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:<\/p>\n

\n

Which door would your brother tell me contains fabulous wealth?<\/p>\n<\/blockquote>\n

The liar would know that his brother would tell the truth, and would then lie about it. (let\u00e2\u20ac\u2122s 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.<\/p>\n

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.<\/p>\n

Both brothers would answer door two. We would then choose door one (i.e.\u00c2\u00a0the opposite of what we are told)<\/p>\n

Let\u00e2\u20ac\u2122s call the question Q, and the real answer A. Brother one tells the truth, so<\/p>\n

B1(Q) = A\n<\/code><\/pre>\n
Brother two always lies, so<\/p>\n
B2(Q) = !A\n<\/code><\/pre>\n
or..<\/p>\n
B2(Q) = !B1(Q)\n<\/code><\/pre>\n
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\u00e2\u20ac\u2122s call M our meta-question and N1 and N2 our meta-question answers (we need N1 and N2 because it\u00e2\u20ac\u2122s a different answer depending on who we ask). Brother one will tell the truth..<\/p>\n
B1(M) = N1\n<\/code><\/pre>\n
But, N1 is the answer that the other brother would give to our real question, Q.<\/p>\n
B1(M) = B2(Q)\nB1(M) = !A\n<\/code><\/pre>\n
Similarly, brother two will lie\u00e2\u20ac\u00a6<\/p>\n
B2(M) = !N2\nB2(M) = !B1(Q)\nB2(M) = !(A)\n<\/code><\/pre>\n
Demonstrating in symbols that both brothers will answer !A when asked what there brother would answer to Q.<\/p>\n
\n
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.<\/p>\n
S1(Q) = !A\nS2(Q) = RAND(A,!A)\nS3(Q) = A\n<\/code><\/pre>\n
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.<\/p>\n
Now – we must face the problem that S2() never tells us anything useful. Given that she is the only one we don\u00e2\u20ac\u2122t want to marry, we must choose our question such that it doesn\u00e2\u20ac\u2122t matter what she answers, and the answers the other two give does tell us something. How about:<\/p>\n
    \n
  • Assume we\u00e2\u20ac\u2122re asking a question of sister A and the two remaining sisters are B and C (and we don\u00e2\u20ac\u2122t know which is which)\u00e2\u20ac\u00a6<\/li>\n<\/ul>\n
    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)<\/p>\n
        (A=1, B=2, C=3)  S1(Q) = C    3    (we want to marry A or C)\n    (A=1, B=3, C=2)  S1(Q) = B    3    (we want to marry A or B)\n    (A=2, B=1, C=3)  S2(Q) = B|C  1|3  (we want to marry B or C)\n    (A=2, B=3, C=1)  S2(Q) = C|B  3|1  (we want to marry B or C)\n    (A=3, B=1, C=2)  S3(Q) = B    1    (we want to marry A or B)\n    (A=3, B=2, C=1)  S3(Q) = C    1    (we want to marry A or C)\n<\/code><\/pre>\n
    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.<\/p>\n
    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\u00e2\u20ac\u2122s case we want the eldest sister, and in sister three\u00e2\u20ac\u2122s 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.<\/p>\n
    \n
    \n
    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 \u00e2\u20ac\u02dcda\u00e2\u20ac\u2122 or \u00e2\u20ac\u02dcja\u00e2\u20ac\u2122, which mean true and false in their own language, but you don\u00e2\u20ac\u2122t know which is which.<\/p>\n<\/blockquote>\n
    Now we\u00e2\u20ac\u2122re getting into very difficult territory. Let\u00e2\u20ac\u2122s call them T, F and R.<\/p>\n
    First let\u00e2\u20ac\u2122s check that the solution is possible\u00e2\u20ac\u00a6 There are three gods and three identies, plus two words and two meanings.<\/p>\n
    JA DA G1 G2 G3\n--------------\nY  N  T  F  R\nY  N  T  R  F\nY  N  F  T  R\nY  N  F  R  T\nY  N  R  T  F\nY  N  R  F  T\nN  Y  T  F  R\nN  Y  T  R  F\nN  Y  F  T  R\nN  Y  F  R  T\nN  Y  R  T  F\nN  Y  R  F  T\n<\/code><\/pre>\n
    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<\/code>. 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\u00e2\u20ac\u2122t we don\u00e2\u20ac\u2122t care.<\/p>\n
    Let\u00e2\u20ac\u2122s first try the puzzle having them speak English (i.e.\u00c2\u00a0no ja and da).<\/p>\n
    Q1: Which of the others will tell me the truth less often?<\/em> We ask A and B, C are the other gods. (obviously we\u00e2\u20ac\u2122d phrase this as a yes\/no question). Paint the god you ask red.<\/p>\n
     (A=T, B=F, C=R)  T(Q1) = B     F\n (A=T, B=R, C=F)  T(Q1) = C     F\n (A=F, B=T, C=R)  F(Q1) = B     T\n (A=F, B=C, C=T)  F(Q1) = C     T\n (A=R, B=T, C=F)  R(Q1) = B|C   T|F\n (A=R, B=F, C=T)  R(Q1) = C|B   F|T\n<\/code><\/pre>\n
    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<\/em> 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:<\/p>\n
     (A=T, B=F, C=R)  T(Q2) = B     F\n (A=T, B=R, C=F)  T(Q2) = C     F\n (A=F, B=T, C=R)  F(Q2) = B     T\n (A=F, B=T, C=R)  F(Q2) = C     T\n<\/code><\/pre>\n
    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:<\/p>\n
    We have found Random and he is not painted blue<\/em><\/p>\n
    The blue god is either True or False. Let\u00e2\u20ac\u2122s switch god-speak back on\u00e2\u20ac\u00a6<\/p>\n
    Q3: Does \u00e2\u20ac\u02dcja\u00e2\u20ac\u2122 mean \u00e2\u20ac\u02dcyes\u00e2\u20ac\u2122?<\/em><\/p>\n
     (A=T, ja=yes)  ja\n (A=T, ja=no)   ja\n (A=F, ja=yes)  da\n (A=F, ja=no)   da\n<\/code><\/pre>\n
    This is extra sneaky. We\u00e2\u20ac\u2122ve relied on the fact that we\u00e2\u20ac\u2122re asking a question about the language the question is being answered in. In more detail: if we ask the True god does \u00e2\u20ac\u02dcya\u00e2\u20ac\u2122 mean \u00e2\u20ac\u02dcyes\u00e2\u20ac\u2122 and \u00e2\u20ac\u02dcya\u00e2\u20ac\u2122 does mean yes, then he will answer \u00e2\u20ac\u02dcyes\u00e2\u20ac\u2122 (\u00e2\u20ac\u02dcya\u00e2\u20ac\u2122). Similarly, if \u00e2\u20ac\u02dcya\u00e2\u20ac\u2122 means \u00e2\u20ac\u02dcno\u00e2\u20ac\u2122, then True answers \u00e2\u20ac\u02dcno\u00e2\u20ac\u2122 (\u00e2\u20ac\u02dcya\u00e2\u20ac\u2122). i.e.\u00c2\u00a0he answers the same regardless of whether \u00e2\u20ac\u02dcya\u00e2\u20ac\u2122 means yes or no. False, on the other hand, always lies, so he always answers \u00e2\u20ac\u02dcda\u00e2\u20ac\u2122, regardless of the actual meaning. So, we now know who is painted blue. And by extension, the other remaining unidentified god.<\/p>\n
    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.<\/p>\n
    Can we modify Q1 so that it works even when we don\u00e2\u20ac\u2122t 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\u00e2\u20ac\u2122s imagine that the gods are arranged in a line, we don\u00e2\u20ac\u2122t know which is which. We ask the middle god:<\/p>\n
    Q1: I require you to exclusive-OR the answer to the following two questions<\/em><\/p>\n
    – a) Will the god to my left tell me the truth less often than the god to my right? – b) Does \u00e2\u20ac\u02dcja\u00e2\u20ac\u2122 mean \u00e2\u20ac\u02dcyes\u00e2\u20ac\u2122?<\/p>\n
    So – we are still getting one answer, but that answer is obtained by combining the answer to two other questions.<\/p>\n
     (B=T, A=F, C=R, ja=no)   T(Q1) = false XOR false = false = 'ja' (A == F)\n (B=T, A=F, C=R, ja=yes)  T(Q1) = false XOR true  = true  = 'ja' (A == F)\n (B=T, A=R, C=F, ja=no )  T(Q1) =  true XOR false = true  = 'da' (C == F)\n (B=T, A=R, C=F, ja=yes)  T(Q1) =  true XOR true  = false = 'da' (C == F)\n (B=F, A=T, C=R, ja=no )  F(Q1) =! true XOR false = false = 'ja' (A == T)\n (B=F, A=T, C=R, ja=yes)  F(Q1) =! true XOR true  = true  = 'ja' (A == T)\n (B=F, A=R, C=T, ja=no )  F(Q1) =!false XOR false = true  = 'da' (C == T)\n (B=F, A=R, C=T, ja=yes)  F(Q1) =!false XOR true  = false = 'da' (C == T)\n (B=R, A=T, C=F, ja=no )  R(Q1) =                    'ja' | 'da' (A|C == T|F)\n (B=R, A=T, C=F, ja=yes)  R(Q1) =                    'ja' | 'da' (A|C == T|F)\n (B=R, A=F, C=T, ja=no )  R(Q1) =                    'da' | 'ja' (C|A == F|T)\n (B=R, A=F, C=T, ja=yes)  R(Q1) =                    'da' | 'ja' (C|A == F|T)\n<\/code><\/pre>\n
    The trick of Q3 was to use the meaning of \u00e2\u20ac\u02dcja\u00e2\u20ac\u2122 to modify the answer. It was self inverting. The same trick is used here. An XOR operation inverts the answer when \u00e2\u20ac\u02dcja\u00e2\u20ac\u2122 is yes. thus it doesn\u00e2\u20ac\u2122t matter whether \u00e2\u20ac\u02dcja\u00e2\u20ac\u2122 means yes or not – it\u00e2\u20ac\u2122s effect has been cancelled out. From here we can proceed as above.<\/p>\n
    We use the answer to this question as follows:<\/p>\n