|Current Contents||Answers, Editorials, & more||Subscription Information||Search for MH Articles||Award Winning Articles||MAA Student Webpage||Instructions for Authors||Inquiries?
As promised, you will find solutions to the Smullyan puzzles and further puzzle variations from the article Liars and Truthtellers: Learning Logic from Raymond Smullyan appearing in November (2005) issue of Math Horizons.
Knight and Knaves---The
Standard Fare; Adding Normals to
the Mix; the Planet Og; and
the Island of Dreamers.
Variations. A Question of Sanity; the Island of Questioners; Lefties and Righties.
Solutions to printed puzzles
(I) Suppose A really did say there was (exactly) one knight among the three. Then B must be a knight for accurately reporting what A said. Since C disagrees with B, C must then be a knave. Now, if A is a knave, we would have a knave, A, making a true statement. If A is a knight, then there would be two knights in the group, so A would never make such a statement. So it is impossible, no matter what type of person A is, for A to claim there is one knight among them. So B must be lying and C is telling the truth. Again, we don't know what type of person A is.
(II) The speaker can't be a knight claiming to be a knave. So the speaker is a knave. If the friend were a knight (as the speaker claims), then we would have a knave making a truthful statement. So the friend is also a knave.
(I) Suppose A is normal. Then A is telling the truth, B is agreeing, so B also telling the truth and hence is the knight. This makes C the knave--unfortunately a knave who is telling the truth.
Suppose A is knight. Then A is lying!
Thus, we have concluded that A is a knave. Since knaves lie and B is agreeing, then B is also lying. Therefore B can't be a knight, so must be the normal. C is the knight.
(II) If A is a knight, then B must be normal and C must be the knave. So C will lie and say that B is of higher rank than A.
If A is a knave (and lying), we can conclude that C is the knight and B is normal. C will tell the truth and say that B is of higher rank than A.
If A is normal and telling the truth, then B is a knight and C is a knave. But now we have a contradiction, namely a knight (B) telling a lie.
If A is normal and lying, then C is a knight and B is a knave. Again we have a contradiction, this time a knave (B) telling the truth.
So, in fact, A is not normal and in the only other possible cases, C's answer will be "B is of higher rank than A."
(I) One question that determines color is: Are you from the North? To see this, we just need consider how each of the four types of inhabitants would respond:
green northerner--tells the truth and says "Yes."
green southerner--lies and says "Yes."
red northerner--lies and says "No."
red southerner--tells the truth and says "No."
So a "Yes" response identifies the speaker as green while a "No" response identifies the speaker as red.
(II) The logic expert must have been speaking to a green inhabitant. If the expert were speaking to a red inhabitant, since it was broad daylight, the expert would know that the inhabitant was lying. If the inhabitant were red and lying, the logician would have been able to deduce that the speaker was a red northerner. Therefore, the logician was speaking to a green inhabitant.
(III) Suppose A is green. Then B is red and is also lying. So B must be from the north. But then A is a green truth-teller, and hence also from the north---a contradiction. So A is red. Therefore B is green and also telling the truth. So B is a green northerner while A is a red southerner (since A is also telling the truth).
(I) The inhabitant must be awake to believe he/she is diurnal, and must be nocturnal to believe he/she is asleep.
(II) Although we don't know exactly what the wife believed, we know that the husband believed both of them nocturnal. In particular, he believed he was nocturnal. So he must have been asleep, which implies that his wife must have been awake. And even though we can't determine the type of the husband and wife, we can conclude that they are of the same type. If they were of differing types, then, since one was awake and one was asleep, they would agree in their beliefs (i.e., opposite types in opposite conditions will agree, while same types in opposite conditions will disagree).
In a particular insane asylum, each individual is of one of two types--a doctor or a patient. Each individual is also either completely sane (totally accurate in his/her beliefs) or completely insane (totally inaccurate in his/her beliefs--that is, each true proposition is believed to be false and each false proposition is believed to be true). Everyone is totally honest--all say what they truly believe.
You meet two people in this asylum. Mr. Jones tells you that Mr. Smith is a doctor on the staff. Mr. Smith tells you that Mr. Jones is a patient. You become concerned that this asylum has a problem--either it's employing an insane doctor or it has admitted a patient who is totally sane. Prove that your concern is well founded.
Answer: Suppose Smith is really a doctor. Then Mr. Jones is sane. If Dr. Smith is also sane, then he correctly tells you that Smith (who is sane) is also a patient. The other possibility is that Dr. Smith is insane.
Now suppose that Smith is not a doctor. Then Mr. Jones is insane. If Mr. Jones is a doctor, then we have the situation of an insane doctor on the staff. If Mr. Jones is not a doctor, then what Mr. Smith has told you is true, so he is a sane patient. In all cases, we reach a troubling conclusion.
(I) Later you meet two individuals, A and B, and determine the following:
A: Believes B is insane
B: Believes A is a doctor.
One of these individuals doesn't belong in the asylum. Who and why?
(II) Provide a statement that, if you hear it spoken, you know the speaker is a sane patient (and hence should be released).
Solutions are provided below.
On this island, the inhabitants don't answer questions---instead they ask them. In fact, they communicate only by asking questions. Not surprisingly, there are two types of inhabitants---type "Y" and type "N". Type "Y" inhabitants only ask questions that can be correctly answered with "yes" while type "N" inhabitants only ask questions that can be correctly answered with "no".
An inhabitant asks you: "Am I of type Y?" What can you conclude?
I relate to you a time when an inhabitant asked me the following question: "Am I of type N?" What can you conclude?
In the first situation, we cannot conclude anything. A type Y inhabitant can ask that question because the correct answer is "yes" while a type N inhabitant can also ask that question because the correct answer is "no". In the second situation, you can conclude that I am lying. Such a statement cannot be uttered by an inhabitant, regardless of type. If uttered by a type Y, the correct answer is "no" and if uttered by a type N then the correct answer is "yes."
(I) Violet and Ethan are inhabitants of the island. You hear Ethan ask: "Are Violet and I both of type N?" Can you determine the types of either one?
(II) Arthur and Robert are brothers on the island. You hear Arthur ask Robert: "Is at least one of us of type N?" What can you conclude?
(III) A husband asks his wife: "Darling, are we of different types?" What can you conclude?
Again solutions are provided below.
Now imagine an island where every inhabitant is either right-handed or left-handed (no one is ambidextrous). Of course, on a "Smullyan island," we expect a logical twist and this island is no different. Here, whatever anyone writes with the stronger hand is true while statements written with the weaker hand are false.
You find a scrap of paper with a statement on it. You are able to deduce that the writer is left-handed. Give an example of a statement that betrays the writer's handedness.
Answer: "I wrote this with my left hand. "
A right-hander could not write such a statement. If written with the left hand it would be the truth but should be a lie, and if written with the right hand it would be a lie but should be the truth. On the other hand (pun intended), a left-hander could write such a statement with either hand.
(I) Give an example of a sentence that must have been written by a right-hander using the left hand. (See web site for solution.)
Suppose you are called in by the police to help with a criminal investigation. You are handed two scraps of paper with statements written by a suspect in a crime. The scraps read:
"I always write with my right hand."
"I sometimes write with my left hand."
The police need to know whether the suspect ever writes with his left hand. Does he?
Answer: Yes. Since the two statements contradict each other, one must be a lie and one must be the truth. In any case, both statements can't be written by the same hand. So the suspect does indeed use both hands in writing.
(II) In another case in which the perpetrator was known to be left-handed, the police found a notebook in the possession of a suspect. All parties agreed that the suspect was the author of the notebook. On page 1 was the statement: "The sentence on page 2 is false." On page 2 was the statement: "The sentence on page 1 was written with my left hand." Should the police hold the suspect?
Solutions provided below.
Solutions to the Variations
(I) Suppose A is sane. Then B is insane, and hence, incorrect in the belief that A is a doctor. So A doesn't belong, being a sane patient. Now suppose A is insane. Then B must be sane and correct in the belief that A is a doctor--an insane doctor who doesn't belong in the asylum.
(II) Here is a statement that works: "Either I am insane or I am a patient." A sane doctor wouldn't utter this incorrect statement while an insane doctor would not utter this correct statement. Similarly, an insane patient would not utter this correct statement, so the only possibility that does not lead to a contradiction is that the statement is spoken by a sane patient.
(I) If Ethan is of type Y, then the answer to his question must be "yes," but the correct answer is "no." So Ethan is of type N, the answer must be "no," and therefore Violet is of type Y.
(II) If Arthur is of type N, then the required answer of "no" leads to a contradiction. So Arthur must be of type Y, the correct answer must be "yes," forcing Robert to be of type N.
(III) While we can't determine the husband's type, we can conclude that the wife is of type N. If the husband is of type Y, then the "yes" answer implies that they are of different types. If the husband is of type N, the "no" response means they are the same type.
(I) Here is a sentence that works: "I am left-handed and I wrote this sentence with my right hand." A left-hander can't write this sentence with either hand--with the left hand it would be false and with the right hand it would be true. So the sentence must have been written by a right-hander. Since the sentence, authored by a right-hander is false (no matter which hand is used to write it), it must have been written with the left hand.
(II) The suspect is right-handed and should be released. We can determine this even though we can't necessarily determine whether the statements involved are true or false. If the sentence on page 1 is true, then the sentence on page two is false, which implies that the sentence on page 1 was written with the suspect's right hand. So the suspect wrote a true statement on page 1 with the right hand and so is right-handed. Alternatively, if the statement on page 1 is false, then the sentence on page 2 is true. So the suspect used his left hand to write a false statement on page 1, again making the suspect right-handed.
Posted 03 April 2006