To Mock a Mocking Bird

by Raymond M. Smullyan

  9 · The native’s statement is to the effect that he has made that very statement some time before. Suppose he is a knight. Then he really has made that statement before—say, yesterday. When he made the statement yesterday, he was also a knight, and so it was true, which means that he had made that same statement some time before that—say, the day before yesterday. We thus get an infinite regress; the only way the native can be a knight is if he has lived infinitely back into the past. Therefore the native is really a knave.

  Another way of looking at the problem, which some readers will find simpler, is this: Since the native has made the statement once, there must have been a first time he made it. Well, when he made it the first time, it was clearly false, hence he is a knave (and he can never make the same statement again, for it would be true).

  6

  Day-Knights and Night-Knights

  We will return to the Island of Knights and Knaves in a later chapter. Meanwhile I would like to tell you of an equally strange place called Subterranea. It is a city completely underground; the inhabitants have never seen the light of day. Clocks, watches, and all other timepieces are strictly forbidden. Yet the inhabitants have an uncanny sense of time; they always know when it is day and when it is night. Each inhabitant is of one of two types—day-knights and night-knights. The day-knights tell the truth during the day and lie during the night; the night-knights tell the truth during the night and lie during the day.

  Visitors to the city are allowed, but of course they may not bring any timepieces with them. Any visitor to the city is bound to become disoriented; after a few days he loses all sense of when it is day and when it is night.

  1 • How Many Questions?

  Suppose that you visit this city and after a few days, you lose all sense of time. At one point you would like to know whether it is day or night. You meet one of the inhabitants and are allowed to ask him as many questions as you like, but you may ask only questions whose answer is yes or no. What is the minimum number of questions you need ask to find out whether it is day or night?

  • 2 •

  Suppose that instead of wanting to know whether it is day or night, you want to know whether the inhabitant to whom you are speaking is a day-knight or a night-knight. What is the smallest number of questions you need ask?

  • 3 •

  When I visited this city, I also lost my time orientation after a few days. Once I came across an inhabitant who made a statement. Before he spoke, I did not know whether he was a day-knight or a night-knight, or whether it was day or night. After he made the statement, I knew that he was a day-knight and that it was then night. Can you supply such a statement?

  • 4 •

  On another occasion I came across an inhabitant who made a statement from which I could deduce that he was a day-knight and that it was then day. What statement would work?

  • 5 •

  On another occasion I met an inhabitant who said: “During the daylight hours I claim it is night.”

  Was it then day or night?

  • 6 •

  On another occasion a native said to me: “During the day I claim that I am a night-knight. I am really a day-knight.”

  I was happy that he made this statement because I could then deduce both his type and whether it was night or day. What is the solution? Note: In this and all other problems in this chapter, I am making the underlying assumption that it never changed from day to night or from night to day during the course of the conversation.

  • 7 •

  On one occasion an inhabitant said: “I am a night-knight and it is now day.” Was he a day-knight or a night-knight? Was it then day or night?

  • 8 •

  On another occasion I asked an inhabitant two questions: “Are you a day-knight?” and “Is it now day?” He replied: “Yes is the correct answer to at least one of your questions.”

  Was he a day-knight or a night-knight? Was it then day or night?

  • 9 •

  I once asked an inhabitant: “Is it true that twelve hours ago you claimed that you were a night-knight?” He replied: “No.” I then asked him: “Twelve hours ago, did you claim that you were a day-knight?” He replied: “Yes.”

  Was he a day-knight or a night-knight? Note: I am, of course, assuming that twelve hours makes the difference between day and night.

  THE DIFFICULTIES DOUBLE

  The next few problems that I encountered presented more of a challenge.

  10 • Two Brothers

  I once came across two brothers A and B and did not know the type of either, nor did I even know whether they were the same type. I also did not know whether it was day or night at the time. Here is what they said:

  A: At least one of us is a day-knight.

  B: A is a night-knight.

  I then knew the type of each and whether it was night or day. What is the solution?

  • 11 •

  On another occasion I came across two inhabitants A and B who made the following statements:

  A: Both of us are day-knights.

  B: That is not true!

  Which one should be believed?

  • 12 •

  At last I made friends with one of the inhabitants—Jim Hawkins—whom I knew to be a day-knight. At one point he told me that some time earlier he had overheard a conversation between two inhabitants A and B in which A said that B was a day-knight and B said that A was a night-knight.

  Was it during the day or during the night that Jim told me this?

  A METAPUZZLE

  • 13 •

  Inspector Craig of Scotland Yard also visited this city. Like every other visitor, he lost his sense of time after a few days. At one point he was desirous of knowing whether it was day or night. He came across a married couple, but he didn’t know whether the husband and wife were the same type or different types. One of the two said: “My spouse and I are different types; one of us is a day-knight and one of us is a night-knight.” Inspector Craig thought about this and said: “What I really want to know is whether it is now day or night. Which is it?” One of the two said: “It is now day.” Inspector Craig then knew whether it was day or night.

  Was it day or night?

  SOLUTIONS

  1 · There is a general principle that will prove helpful in many of these problems—namely that during the day, all inhabitants claim to be day-knights, and during the night, all inhabitants claim to be night-knights. This is true because during the day a day-knight is truthful and will truthfully admit to being a day-knight, whereas a night-knight will lie and also claim to be a day-knight. During the night, a night-knight will truthfully claim he is a night-knight and a day-knight will falsely claim he is a night-knight.

  Therefore, to find out whether it is day or night, you need ask but one question: Are you a day-knight? If you get yes for an answer, then it is day; if you get no for an answer then it is night.

  2 · Another useful principle is that day-knights always claim it is day and night-knights always claim it is night. This is because during the day, a day-knight will truthfully claim it is day and during the night he will falsely claim it is day. On the other hand, during the day, night-knights falsely claim it is night, and during the night, they truthfully claim it is night.

  Therefore, to find out if someone is a day-knight or a night-knight, just ask him whether it is now day. If he answers yes, then he is a day-knight; if he answers no, then he is a night-knight.

  3 and 4 · The solutions will emerge as a result of some subsequent problems.

  5 · He claims that he lies during the day, or what is the same thing, that he is a night-knight. Therefore it must have been night when he said that.

  6 · The native’s first statement was simply a lie—no one ever claims to be a night-knight during the day, as was explained in the solution to Problem 1. Therefore he was lying at the time, so his second statement was also a lie. Therefore he is really a night-knight. Since he is a night-knight and was lying at
the time, it must have been day.

  7 · Suppose his statement were true. Then he would really be a night-knight and it would really be day, but night-knights don’t tell the truth during the day. Therefore his statement must have been false. So he was lying, but since he is not a night-knight making the statement during the day, it must be that he is a day-knight and that it was then night.

  This, by the way, provides a solution to Problem 3.

  8 · He is in effect asserting that either he is a day-knight or that it is now day, and maybe both. Suppose his statement were false. Then he is neither a day-knight, nor is it day; this means that he is a night-knight and it is night. But night-knights don’t make false statements at night, so it is contradictory to assume that his statement was false. And so his statement was true. Therefore he is either a day-knight or it is day. If the first alternative holds—that is, if he is a day-knight—then it must be day, because day-knights tell the truth only during the day. If the second alternative holds—that is, it is now day—then he must be a day-knight, because only day-knights tell the truth during the day. And so each of the alternatives implies the other, which means that he is a day-knight and it is day.

  This, incidentally, provides a solution to Problem 4; he could have said: “Either I am a day-knight or it is now day.” An equally valid solution is: “If I am a night-knight then it is now day.”

  9 · His answers were either both truthful or both lies.

  Case 1: Both answers were truthful. Then his second answer was truthful, hence twelve hours ago he really did claim to be a day-knight. He lied twelve hours ago, since he is now truthful, so he is really a night-knight.

  Case 2: Both answers were lies. Then his first answer was a lie, hence twelve hours ago he did claim to be a night-knight. He was truthful then, so he is a night-knight.

  In either case he is a night-knight. It cannot be determined whether his answers were truthful or lies.

  10 · If it is night, we get the following contradiction:

  Suppose B is telling the truth. Then A is really a night-knight, hence A is telling the truth, since it is night, which means that at least one of them is a day-knight, hence B must be the day-knight and we have the impossibility of a day-knight telling the truth during the night. Suppose, on the other hand, that B is lying. Then A is really a day-knight, hence his statement is true—that is, at least one of them is a day-knight—which means that A, a day-knight, is telling the truth during the night. This is equally impossible. Therefore we know for sure that it is now day.

  Could B be a day-knight? If he were, then he is telling the truth, since it is day, hence A would be a night-knight, but then his statement would be correct, since at least one of them—namely B—is a day-knight, which would mean that A, a night-knight, is making a true statement during the day. Therefore B cannot be a day-knight; he must be a night-knight. Then, since it is now day, his statement is false, hence A is really a day-knight.

  And so the solution is that A is a day-knight, B is a night-knight, and it is now day.

  11 · This is quite simple: If A were telling the truth, both would be day-knights; B would be the same type as A and wouldn’t have contradicted A. And so A is lying and B is telling the truth.

  12 · Jim’s story cannot be true for the following reasons. Suppose A and B made their statements during the day. If A is a day-knight, then he is telling the truth, hence B is a day-knight and his statement is true, but B said that A is a night-knight, so B’s statement can’t be true. This is a contradiction. On the other hand, if A is a night-knight, then A is lying, which means that B is a night-knight. But since A is a night-knight, then B’s statement was truthful, which means that B, a night-knight, told the truth during the day. This proves that the remarks of A and B couldn’t have occurred during the day. A symmetrical argument, which the reader can supply, shows that A and B couldn’t have made these remarks during the night either. Therefore Jim’s story was simply false. Since Jim is a day-knight, he must have told this story during the night.

  13 · Let A be the one—husband or wife, as the case may be—who claimed that his or her spouse B was not the same type as A. If A’s statement was true, then A was then in the truth-telling state and B was really a different type than A, hence B was then in the lying state. If A’s statement was false, then A was in the lying state, B was actually the same type as A, and again B had to be in the lying state. So Craig could deduce from A’s statement that B was in the lying state, but Craig could not know whether or not A was in the truth-telling state. Therefore, if A had been the one who claimed it was day, Craig couldn’t have known whether it was day or night. And so it must have been B who claimed it was day, and Craig then knew it was night.

  7

  Gods, Demons, and Mortals

  Shortly after Inspector Craig returned to London from his strange experience in Subterranea, he had a curious dream. He had been browsing that day in a library specializing in rare books on mythology, another of his many interests. His head was filled with gods and demons, and so his dream was perhaps not so surprising.

  Time sometimes passes in unusual ways in the course of a dream. Craig dreamed that he spent nine days in a region in which dwelled gods, demons, and mortals. The gods, of course, always told the truth, and the demons always lied. As to the mortals, half were knights and half were knaves. As usual, the knights told the truth and the knaves lied.

  1 • The First Day

  Craig dreamed that on the first day he met a dweller of the region who looked as if he might be a god, though Craig could not be sure. The dweller evidently guessed Craig’s thoughts, smiled, and made a statement to reassure him. From this statement, Craig knew that he was in the presence of a god.

  Can you supply such a statement?

  2 • The Second Day

  In this episode of the dream, Craig met a terrifying-looking being who had every appearance of being a demon.

  “What sort of being are you?” asked Craig, in some alarm. The being answered, and Craig then realized that he was confronting not a demon, but a knave. What could the being have answered?

  3 • The Third Day

  In this episode, Craig met a totally nondescript-looking being who from appearances could have been anything at all. The being then made a statement from which Craig could deduce that he was either a god or a demon, but Craig could not tell which.

  Can you supply such a statement?

  4 • The Fourth Day

  Craig next met a being who made the following two statements:

  1. A god once claimed that I am a demon.

  2. No knight has ever claimed that I am a knave.

  What sort of being was he?

  5 • The Fifth Day

  A being made the following two statements to Craig:

  1. I never claim to be a knave.

  2. I sometimes claim that I am a demon.

  What sort of being are we now dealing with?

  6 • The Sixth Day

  In this episode, Craig came across two beings, each of whom made a statement. Craig could then infer that at least one of them must be a god, but he could not tell which one. From neither statement alone could Craig have deduced this.

  What statements could the beings have made?

  7 • The Seventh Day

  On the next day, Craig again met two beings each of whom made a statement. Craig could then infer that one of them was a knave and the other a demon, though he could not tell which was which. Again, from neither statement alone could Craig have inferred this. Can you supply two such statements?

  8 • Introducing Thor

  On the eighth day, Craig met a being who had every appearance of being the god Thor. The being made a statement, and Craig then knew he must be Thor.

  What statement could Thor have made?

  9 • A Perplexity Resolved

  Craig and Thor became fast friends. In fact, on the evening of the ninth day, Thor gave a magnificent banquet in Craig’s honor. �
�I propose a toast to our illustrious guest!” said Thor, as he raised his glass of nectar.

  After a round of cheers, Craig was asked to speak.

  “I am very perplexed!” said Craig as he rose. “I wonder if this may not all be a dream!”

  “Why do you think you may be dreaming?” asked Thor.

  “Because,” said Craig, “two incidents have occurred today that seem totally inexplicable. This morning I met someone who made a statement which no knight, knave, god, or demon could possibly make. Then this afternoon I met someone else who also made a statement which no dweller of this region could possibly make. That is why I suspect that I may be dreaming.”

  “Oh!” said Thor. “Be reassured; you are not dreaming. The two incidents have a perfectly rational explanation. You see, we have had two visitors here from another realm. Both of them are mortal. One is Cyrus, who always tells the truth, although he is not called a knight since he is not from this region. The other is Alexander, who sometimes tells the truth and sometimes lies. It must have been those two whom you met today. What statements did they make?”