Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. 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 own language, in which the words for yes and no are 'da' and 'ja', in some order. You do not know which word means which.
Wednesday, March 09, 2011
The Hardest Logic Puzzle Ever
Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. 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 own language, in which the words for yes and no are 'da' and 'ja', in some order. You do not know which word means which.
Subscribe to:
Post Comments (Atom)
10 comments:
Stolen without obfuscation; spoilers are a quick search away. The source has a subheading called "The Solution." The best I can do in three questions is determine how they say "yes."
Some clarifications:
It could be that some god gets asked more than one question (and hence that some god is not asked any question at all).
What the second question is, and to which god it is put, may depend on the answer to the first question. (And of course similarly for the third question.)
Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely.
Random will answer 'da' or 'ja' when asked any yes-no question.
A few things:
I take it that all three gods are Smullyanesque omniscient perfect logicians, yes?
Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely.
So then Random does take the truth or falsity of his response into account? His "coin flip" does not just determine whether he spits out a 'da' or 'ja', but rather he first decides what the answer is and then decides whether to lie about it. Right?
This is a real distinction, because if it's the latter then we have the same issue with him as we do for True and False, viz. how do they answer yes/no questions whose correct answer is indeterminate? One obvious example of such is "How would Random answer if I asked him if 1 + 1 = 2?" Your last clarification implies that Random will answer 'da' or 'ja', but how does he know which to choose? And if it's the case that he doesn't consider the question before spitting out his answer, there still remains the problem of how True would answer the above example.
Oh, wait, that's not quite a yes/no question, although it could be considered a "yes"/"no" question. Let me rephrase:
"If I asked Random whether 1 + 1 = 2, would he say 'da'?"
Or do they have knowledge of the future as well, including of random events?
Yes, I think we should assume that all three are SOPLs.
You raise an interesting point, and a potential chink in the armor. Let's make assumptions that will help us the most, to begin.
1) If True or False are asked a question with an indeterminate answer, they will remain silent and the question will not count.
2) Random always answers "ja" or "da" at random no matter what you ask.
So we ask all three your indeterminate question, and Random answers. Now we have two questions left.
If we ask one of the non-Random gods "Will you say 'ja' if I ask if you are honest?" True will say "ja" and False will say "da."
So that solves it in two. Maybe my assumptions above are too greedy. So let's say an unanswered question does count. Then we need at most three queries.
Wait, what?
So we ask all three your indeterminate question, and Random answers. Now we have two questions left.
How do we have two questions left? "each question must be put to exactly one god."
So that solves it in two.
How? we already knew we would get one 'ja' and one 'da', and so when that's exactly what we get, we get no new information. Even setting aside that it's 5 questions in total, not 2.
Oh, wait, I was thinking for some reason that we also needed to determine the corredct translations for "da" and "ja". So it would solve it in two, if it were two and not five.
How do we have two questions left?
Because by Assumption 1, questions that get no response do not count. But we can solve it even if unanswered questions count. The method is:
Ask A the indeterminate question. If he answers, he is Random.
If A didn't answer, ask B the indeterminate question. If he answers, he is Random. Otherwise, C is Random.
Now we know who Random is, and we have asked one or two questions.
Ask one of the non-Random gods "Will you say 'ja' if I ask if you are honest?" If he says 'ja' he is True, otherwise he is False.
And we're finished in two or three questions.
Right then. But a peek at the source (credited to George Boolos, inspired by Smullyan) doesn't seem to use the indeterminism trick. Alternatives for the first question use phrases like "if and only if" and "an odd number of the following statements."
Hmm, so we are. The only weak point is that we don't know if it's valid to assume that an indeterminate question receives no answer.
However, I think we can tweak our way around this.
Suppose you ask an indeterminate question. Then Random will answer da/ja. The problem statement does not say that True and False must answer da/ja, so we can assume that they will give some other answer. To avoid lying, True might say something like "It is impossible to know at this time", and False might say such as "I know the answer, but I choose not to reveal it". In either case the answer is not a simple da/ja, so even though we may not know what the response means, we can still identify Random as in your solution.
Post a Comment