Either you guys took THC off your RSS readers or last week was too abstract for the first time back. This should be more concrete, which is not to say easier. If nobody answers this one, we’ll try easier.
Remember Labyrinth the tour de force by Jim Henson, George Lucas and David Bowie? At one point, the heroine was faced with two guards, one who always lied and another who always told the truth.
Imagine that you find yourself in the following, similar situation. Three guards block your path and will bar your way unless you can name them. You know that their names are Godel, Escher and Quine and that Godel always answers correctly, Escher always lies and Quine answers randomly. However, you do not know which is which. You may ask three yes/no questions, sequentially, to guards of your choice.
What do you do?
Bonus: There is an even better version of this on Wikipedia with the title the hardest logic puzzle ever. In that problem, the guards answer in an unknown language with “da” or “ja” and you don’t know which is “yes” and which is “no”.
Solution:
No Title
- Let Tn be the statement, “Person n always tells the truth.”
- Let Fn be the statement, “Person n always lies.”
- Let Xn be the statement, “Person n answers randomly.”
- Let 4 be a universally true statment, e.g., “2 + 2 = 4”.
- Let D be the statement, “ `Da’ means `True.’ “
- For any statement S, S? denotes the question, “Is S true?”
Consider the question = “4 if and only if D?.” If “da” means “false”, then the statement is false and therefore the answer (if put to the honest person) would be “da.” If, on the other hand, “da” means “true,” then the statement is true and the answer will still be “da.”
Now consider the question “ 4 if and only if D?” If “da” means “true”, then the statement is false and the honest answer would be “ja.” If, on the other hand, “da” means “false”, then the statment is true and the answer would still be “ja.”
You can see that if we ask “S? if and only if D?”, we can pretend that we simply asked S? and interpret “da” to be “true” and “ja” to be “false.” Hitherto, I will strip this and assume that the people answer in English.
What makes the problem tricky is that you might ask your first question to the random guy. So it would be logical to assume that our second question will be to somebody different than the first question. It would be nice if the second question were surely put to someone other than the random guy. That would be some question, the answer to which has the following truth table. Assume that we ask the first person.
| 1 | 2 | 3 |
| T | F | X | T |
| T | X | F | F |
| F | T | X | T |
| F | X | T | F |
| X | T | F | T/F |
| X | F | T | F/T
|
If the answer is “True,” then we know that the second person is not random and if it is “False,” we know that the third is not random. Now let’s try to come up with such a question.
Consider the statement “F
2 and X
3.” hitherto abrevieated F
2X
3.
Consider also the statement X
2T
3. Finally consider “F
2X
3 or X
2T
3“ hitherto abreviated F
2X
3+X
2T
3.
| 1 | 2 | 3 | F2X3 | X2T3 | F2X3+X2T3 |
| T | F | X | T | F | T |
| T | X | F | F | F | F |
| F | T | X | T | T | T |
| F | X | T | T | F | F
|
Which is that for which we were looking.
So now we’ve identified a person who is surely not random and we still have two questions left. It should be pretty easy from here. We can simply ask the non-random person X
1? and 4? and that will unambiguously identify the case.
For completeness, let’s write out what I would actually say for the first question.
Is it the case that,
- person two is the liar and,
- person three is random
or,
- person two is random and,
- person three is always truthful
if and only if
Liz came up with a terse and elegant version of the same question, “If asked [4], would person three be more likely to say `da’ than person two?” As a result, she is now tied for second place with 4 points.
File translated from
TEX
by
TTH,
version 3.85.
On 2 Feb 2009, 15:30.
