Here’s a logic puzzle for you: Suppose I offer you a million dollars, in return for which you agree to answer a certain yes/no question. You can answer either truthfully or falsely as you desire. That’s it. Should you accept that offer? Solution below the fold.
Those of you reading this who enjoy logic puzzles are probably familiar with Raymond Smullyan. I was pretty young, eight or nine I think, when I first discovered his writing. Somehow I noticed his book What is the Name of This Book? sitting in a bookstore, and I persuaded my parents to buy it for me. The book opened with some very elementary puzzles I was able to appreciate even as a young child. But pretty soon I came to one of his most famous creations, the island of knights and knaves.
On this island the knights always tell the truth and the knaves always lie. The inhabitants of this island are in the habit of gathering in small groups and making various statements, from which you are to determine who among them is a knight and who is a knave. Smullyan intended these puzzles as a device for teaching basic ideas in propositional logic, and I use them for that purpose in my discrete mathematics classes. Anyway, at some point little kid me came across the following problem:
Suppose you meet three people, who we shall call A, B and C. You ask A, “How many knights are among you?” A mumbles an answer, but you cannot understand what he said. So you ask B to tell you what A said. B says, “A said that there is one knight among us.” At this point C interrupts and says, “Don’t listen to B! He’s lying.” Can you determine anything about what type B and C are?
At the time I was not able to make heads or tails of this. So I brought it to my father. He glanced at it, and with seemingly no effort at all he tossed off something like the following: “Well, let’s suppose B is a knight. Then C must be a knave, since he lied when he said that B had lied. Very well. Since B is a knight, then A really did say there was only one knight among them. But if A were a knight, then he would have been lying, since we know B is a knight and that would then make two knights. So A would have to be a knave. But then his statement would be true, since there really was only one knight among the three of them. So this is impossible as well. The only conclusion is that B must be a knave, and C is a knight.”
I was impressed. I have a clear memory of thinking, “I want to be able to do that.” With some fatherly guidance I soon got the hang of it, and pretty soon I was able to solve some of the easier problems. At that age I still wasn’t able to work out the more complex puzzles Smullyan devised, since I would quickly lose track of the analysis tree and I absolutely refused to write anything down. But I was hooked, and I have been a big fan of Smullyan ever since.
Anyway, knights and knaves are hardly his only invention. He also developed the idea of “Coercive Logic,” by which he meant logic that compels a person to do something he would not otherwise do. The puzzle from the start of this post is an especially ingenious example.
Of course, you should not accept my offer. If you did accept, and if you adhered strictly to the rules of the game, then you would find yourself paying me two million dollars. You see, the question I would have you answer is, “Will you either truthfully answer no this question, or falsely answer yes, or pay me two million dollars?”
We shall analyze the consequences of your various answers momentarily, but first we need to clarify one of the rules of propositional logic. In everyday speech, when we make a statement of the form “P or Q” there are two different meaning we might intend. Sometimes we mean, “Either P is true or Q is true or both are true.” Other times we mean, “Either P is true or Q is true, but it is not the case that both are true.” In logic, we always intend the first meaning. Thus, a statement that consists of a bunch of propositions connected by “or” is deemed to be true as soon as at least one of the individual propositions is true.
Now let’s consider my question. According to the rules of the game, you must answer either truthfully or falsely. That probably didn’t seem like much of a restriction, but it does rule out a big possibility. It prohibits you from answering in a manner that entails a contradiction.
Now, my question is asking whether at least one of these three alternatives holds:
- You will truthfully answer “no” to my question.
- You will falsely answer “yes” to my question.
- You will pay me two million dollars.
By answering “yes” to my question you are affirming that one of these three possibilities holds. Now suppose that your “yes” answer were false. In that case the second item would hold, meaning that you answered truthfully after all. So this leads to a contradiction, and you cannot falsely answer &yes&rdquo. Thus, if you are adhering to the rules, and answer in a way that is either true or false, then your yes answer must be true. But in this case the first two items clearly do not hold. That means the only way your yes answer could be true is if you pay me two million dollars.
What happens if you answer “no”? If that answer is true then you’re asserting that none of the three items will hold. But by giving a true answer of no the first item holds, and we have another contradiction. So you cannot truthfully answer “no.” That means your “no” answer must have been false, which is tantamount to asserting that at least one of the three items does hold. But which of the three? Certainly not the first two (since you neither truthfully answered “no” nor falsely answered “yes.”) What does that leave? Again, only the third item.
Thus, you can truthfully answer yes and pay me two million dollars, or you can falsely answer no and pay me. The only other alternatives entail logical contradictions, meaning you did not answer either truthfully or falsely in those cases.
Clever! Smullyan’s books are chock-full of similar puzzles, so if you found this amusing then I recommend his work to you.