Today's puzzle will be posed in two halves. The first half is a classic riddle – in fact, I suspect many of you will have heard it before. The second half, however, is an extension of the riddle that reveals its most common solution be be insufficient.
The classic riddle goes as follows:
A hunter walks a mile due south, turns and walks a mile due east, turns again and walks a mile due north, only to find herself back where she started. The hunter draws a bead on a bear and shoots it dead. What color is the bear? Why?
The bear you shoot will always be a polar bear, but the explanation for why this is – that the hunter must have started at the North Pole – is insufficient. While this is one possibility, the North Pole is not the only point of origin on Earth that satisfies the conditions presented in the problem. Can you think of any other point (or points) on the globe from which the hunter could begin her journey and find herself back at her original location?
We'll be back next week with the solution – and a new puzzle! Got a great brainteaser (original or otherwise) that you'd like to see featured? E-mail me with your recommendations (make sure you include "Sunday Puzzle" in the subject line)!
UPDATE: SOLUTION TO PART 2
Top image by Tara Jacoby
H/t to Ryan Hughes, for suggesting this riddle!
The solution to last week's puzzle is rather long, mainly because Boolos' puzzle is actually several puzzles bundled into one, and each of the constituent puzzles requires a fair bit of explaining. In his original presentation of "The Hardest Logic Puzzle Ever," Boolos "set out and solved three related, but much easier, puzzles," before tackling the big one. If you'd like to work through those puzzles, and read his solution, click here.
Below are two additional solutions to the riddle, helpfully provided by philosopher Brian Rabern, who helped me moderate comments on the Sunday Puzzle last week. The solutions he presents here are based off the ones provided in his 2008 publication, "A simple solution to the hardest logic puzzle ever."
Most of the difficulty with this puzzle is in concocting the first question. In the worst case scenario, we address Random with our first question, and Random's answers are useless. How can we make any progress? We'd like to be able to figure out that a certain god is not Random, so that we can address our next questions to him. As Boolos states: "Your first move is to find a god that you can be certain is not Random."
There are different ways to do this, but they all rely on reasoning of the following sort (to make things easier let's simplify the problem by assuming for now that the gods answer in English, and that none of the gods is a liar. We will add these challenges shortly.):
Let's address god B and ask "Is A Random?" B either answer "yes" or "no."
If he answers "yes," then either he is Random (giving us a useless answer) or he is not Random. If B is not Random, then the answer indicates that A is Random. If B is Random, then C is not Random; If B is a truth-teller, then A is Random, and thus C is not Random. So either way we know that C is not Random.
If instead he answers "no," then either he is Random (giving us a useless answer) or he is not Random. If B is not Random, then the answer indicates that A is not random. If B is Random, then A is not Random; If B is a truth-teller, then A is not Random. So either way we know that A is not Random.
So if B answers "yes," C is not Random; and if B answers "no," A is not Random. Thus, after this question we have found a god that we are certain is not Random. From here on out, we will only talk to him.
Ok. But all of our reasoning up to this point has been carried out under two simplifying assumptions:
- That the gods speak English, and
- That there is no lying god.
First let's deal with the fact that there is a liar in our midst, and then deal with the language barrier.
There is a well-known trick – popularized by Raymond Smullyan's "Knights and Knaves" puzzles, as well as the movie Labyrinth – that transforms liars into truth-tellers while preserving the honesty of the truth-tellers. What we can take advantage of is the fact that even liars are sensitive to the truth of a proposition, it is just that they track the truth-values in the opposite way from truth-tellers. David Lewis wisely stated that "[Liars] are as truthful in their own way as we are in ours. But they are truthful in Liarese... and Liarese is a language like [ours] but with all the truth values reversed." (Lewis 1980, "Index, context, and content", 80)
Consider asking False the following question:
"If I asked you, 'Is 2 even?' would you say 'yes'?"
Since False is a liar, if we were to ask him a question whose correct answer is "yes" – such as "Is 2 an even number?" – he would in fact say "no." So when we ask him about how he would respond to this question, he will lie and answer "yes." A double-negative makes a positive. But True will also answer "yes" to this question. He would tell us the truth about 2's evenness, and he would also tell us the truth about his truth-telling. A double-positive remains positive.
The upshot: Whether you adress the truth-teller of the liar, posing questions of the form "If I asked you Q, would you say 'yes'?" yields "yes" just in case the correct answer to Q is affirmative. Otherwise, it yields "no." (This is a very useful device on Smullyan's island of Knights and Knaves. A similar device, used by Boolos in his solution, is biconditionals of this form: "Are you are a truth-teller if and only if 2 is even?")
Still, we are faced with the problem that the gods answer in a foreign language that we do not understand. However, we do know something about the language: We know that the words for "yes" and "no" are "da" and "ja," in some order. So if "da" means yes, then "ja" means no, and if "ja" means yes, then "da" means no.
First notice that the following question – with "no" in place of "yes" – would be just as useful in overcoming the liar:
"If I asked you, 'Is 2 even?' would you say 'no'?"
True will answer "no," and so will False, since he would in fact say "no" to "Is 2 even?," so he will lie and say "no" to the question about how he would respond. So we can also conclude that asking either the truth-teller or the liar questions of the form "If I asked you Q, would you say 'no'?" yields "no," just in case the correct answer to Q is affirmative (and yields "no" otherwise).
But now we can see that it doesn't matter what "yes" or "no" mean. It only matters that one of them means yes and one of them means no. So, in fact, the embedded questions overcome both the liar/truth-teller problem and the language barrier all at once. This is what Rabern & Rabern (2008) call the embedded question lemma – when either True or False are asked "If I asked you Q, would you say 'ja'?", a response of "ja" indicates that the correct answer to Q is affirmative and a response of "da" indicates that the correct answer to Q is negative.
Now that we can handle a liar in our midst and we can overcome the language barrier we can return to the first question without the simplifying assumption that the gods speak English and that there is no lying god. We simply have to embed our question "Is A Random?"; the disjunctive reasoning is the same.
Question 1: Ask god B, "If I asked you 'Is A Random?', would you say 'ja'?". If B answers "ja," either B is Random (and is answering randomly), or B is not Random and the answer indicates that A is indeed Random. Either way, C is not Random. If B answers "da," either B is Random (and is answering randomly), or B is not Random and the answer indicates that A is not Random. Either way, you know that a particular god is not Random.
Now we know that we can talk to a non-random god. And given the embedding device it doesn't matter whether we address a liar or truth-teller.
Question 2: Go to the god who was identified as not being Random by the previous question (either A or C), and ask him: "If I asked you 'Are you False?', would you say 'ja'?". Since he is not Random, an answer of "da" indicates that he is True and an answer of "ja" indicates that he is False. (Note that other questions would also work here, e.g. "Does Da mean yes?"; if "da," then he is True, if "ja," then he is False.)
Question 3: Ask the same god the question: "If I asked you 'Is B Random?', would you say 'ja'?". If the answer is "ja," B is Random; if the answer is "da," the god you have not yet spoken to is Random. The remaining god can, then, be identified by elimination.
A natural thought that many people have when confronted with the puzzle is this: Are there questions that the gods can't answer? If so does that hold the key to a solution?
This is made especially salient when you start to wonder about how the truth-telling gods would answer questions about Random's future behavior. As was mentioned in the comments to last week's post, there are some interesting things here about how omniscient gods answer questions about random events.
One might reason as follows: Clearly an all-knowing god knows the results of all future coin flips, so why should there be a problem with True answering questions about how Random would answer things? That seems reasonable enough. But the answers are supposed to be completely "random," and this seems to imply that they could not be known or predicted in advance. How do we reconcile this problem? That depends on how we understand "random," and on more general issues relating to the foreknowledge of chancy events. If the gods are limited in this way, then indeed we can make use of this to solve the puzzle. ( See Uzquiano 2010 for a solution that makes us of these ideas.)
Besides, even if we think that the gods can answer any question about Random's behavior, there is another limitation – and this one is insurmountable.
Let me defend a bold claim: god does not exist. Well, at least, a god who always tells the truth does not exist. And we can easily prove it. To be precise, we can prove that a god with the following property does not and cannot exist; being such that one answers all yes-no questions truthfully with either "yes" or "no." We'll call such a god an "absolute truth-telling god."
Proof. Assume (to reach a contradiction) that an absolute truth-telling god exists. Ask her the following yes-no question: 'Are you going to answer 'no' to this question?' If she responds 'yes', then she affirms that she answers "no" but she did not answer "no." Thus, she did not tell the truth. If instead she responds "no," then she denies that she answers "no" but she did answer "no." Either way, we get a contradiction. Thus, an absolute truth-telling god is impossible.
NB: This is essentially Tarski's theorem, i.e. there is no truth predicate for a language, which has the expressive resources to talk about it's own sentences (while employing classical logic), that satisfies the T-schema where for a predicate to satisfy the T-schema is for a valid schema to result when this predicate is substituted for 'Tr' in 'Tr(ψ) <–> s' where instances of this schema are obtained by substituting sentences for 's' and substituting names of the corresponding sentences for ψ).
This shows that the truth-teller (and liar) will be unable to answer "yes" or "no" to some questions. Thus, there are not two but three possible reactions that a truth-teller might have upon being posed a yes-no question: "yes," "no," and head-explode. If so, then three possibilities can be distinguished with one yes-no question. Thus, using such questions allows for a two-question solution to the puzzle. (For the details see Rabern & Rabern 2008 and Uzquiano 2010).
This is why I introduced the new rule: If you are asking questions that, for whatever reason, gods can't answer (e.g. questions about Random's future behavior or paradoxical head-exploding questions), then you have to solve it with only two questions. Allowing yourself a third question is lazy and wasteful. You don't need it.
George Boolos – "The Hardest Logic Puzzle Ever"
Rabern & Rabern – "A simple solution to the hardest logic puzzle ever"
Gabriel Uzquiano – "How to solve the hardest logic puzzle ever in two questions"
- "The Hardest Logic Puzzle In The World"
- 100 Green-Eyed Dragons
- Can you figure our this parking lot's numbering system?