The hidden solution
Apr. 23rd, 2020 08:16 pmI've had an interesting encounter with a logic puzzle.
Raymond Smullyan's book What is the Name of This Book? includes many puzzles with the premise of an island populated by knights, knaves, and normals. Knights always speak the truth, knaves always speak falsely, and normals sometimes do either.
A typical (if easy) example is problem 103: At a trial, you (an inhabitant of this island) must make a statement proving that you are a normal.
There are many possible solutions, but a clear and elegant one is, "I am a knave." Neither a knight nor a knave could say this, so you must be a normal.
Unstated but critical in the solution is the idea of "proof by contradiction" employed by the jury. They consider the possibility that you are a knight, but this quickly leads to the conclusions "You always speak the truth" and "Your statement is a lie." This is a contradiction; therefore, its premise (you are a knight) must be discarded as false. Similarly, the premise that you are a knave leads to a contradiction: You always speak falsely, but you just made a true statement. So they know you're not a knave. The premise that you are a normal is the only one that does not lead to a contradiction. Therefore, they know that you must be a normal. (I apologize if this is obvious. It'll be important shortly.)
Problem 106 inverts this: How many statements would it take to convince the king that you are not a normal? (Answer for both a knight and a knave.)
In case you want to think about that for a while, I'll leave some spoiler space.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Smullyan helpfully provides answers to his riddles, and for this one, he simply says: It can't be done. Even if you're truly not a normal, any statements you make to try to prove this could just as easily be uttered by a normal (who after all can say whatever they please). You can't prove you're not a normal.
That was not my solution.
My solution for the knight was a single statement, "I am a knight or this sentence is false."
A knave could instead state, "I am not a knave and this sentence is false."
In both cases, the premise that the speaker of this statement is a normal leads to a contradiction, regardless of whether the statement is assumed to be true or false.
Could a normal utter it anyway? Maybe. It is unclear in the book whether normals are free to tell only truths and falsehoods, or whether they are empowered to string together any words they wish, including self-contradictory statements. (Normals "sometimes lie and sometimes tell the truth". Can they also do other things? (Everyone, please no nitpicking about "lies" versus "falsehoods". It's beside the point.)) However, even if we generously grant that normals can say anything at all, I will note that the challenge was not to make a statement that a normal could not make, but rather to convince the king that you are not a normal.
The king, like the jury, employs logic with ruthless efficiency. Nowhere is it implied that we might count on the king to make a logical blunder, such as entertaining a premise that leads to a contradiction. That would undermine the entire challenge. Since you have just made a statement which results in a contradiction if you are anything but a knight, he must conclude that you are a knight, or he must abandon logic. (The knave's answer is just as powerful.)
Mr. Smullyan, I am prepared to claim from your ghost the five and a third Internet Points which I have just won in fair combat. (Also, I loved your book.)
--------------
p.s. On the same piece of paper where I had written my solution in a dentist's waiting room last year, I had also noted, with amusement, the following:
"This sentence is false" is contradictory. But "I am a knave" is not!
Raymond Smullyan's book What is the Name of This Book? includes many puzzles with the premise of an island populated by knights, knaves, and normals. Knights always speak the truth, knaves always speak falsely, and normals sometimes do either.
A typical (if easy) example is problem 103: At a trial, you (an inhabitant of this island) must make a statement proving that you are a normal.
There are many possible solutions, but a clear and elegant one is, "I am a knave." Neither a knight nor a knave could say this, so you must be a normal.
Unstated but critical in the solution is the idea of "proof by contradiction" employed by the jury. They consider the possibility that you are a knight, but this quickly leads to the conclusions "You always speak the truth" and "Your statement is a lie." This is a contradiction; therefore, its premise (you are a knight) must be discarded as false. Similarly, the premise that you are a knave leads to a contradiction: You always speak falsely, but you just made a true statement. So they know you're not a knave. The premise that you are a normal is the only one that does not lead to a contradiction. Therefore, they know that you must be a normal. (I apologize if this is obvious. It'll be important shortly.)
Problem 106 inverts this: How many statements would it take to convince the king that you are not a normal? (Answer for both a knight and a knave.)
In case you want to think about that for a while, I'll leave some spoiler space.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Smullyan helpfully provides answers to his riddles, and for this one, he simply says: It can't be done. Even if you're truly not a normal, any statements you make to try to prove this could just as easily be uttered by a normal (who after all can say whatever they please). You can't prove you're not a normal.
That was not my solution.
My solution for the knight was a single statement, "I am a knight or this sentence is false."
A knave could instead state, "I am not a knave and this sentence is false."
In both cases, the premise that the speaker of this statement is a normal leads to a contradiction, regardless of whether the statement is assumed to be true or false.
Could a normal utter it anyway? Maybe. It is unclear in the book whether normals are free to tell only truths and falsehoods, or whether they are empowered to string together any words they wish, including self-contradictory statements. (Normals "sometimes lie and sometimes tell the truth". Can they also do other things? (Everyone, please no nitpicking about "lies" versus "falsehoods". It's beside the point.)) However, even if we generously grant that normals can say anything at all, I will note that the challenge was not to make a statement that a normal could not make, but rather to convince the king that you are not a normal.
The king, like the jury, employs logic with ruthless efficiency. Nowhere is it implied that we might count on the king to make a logical blunder, such as entertaining a premise that leads to a contradiction. That would undermine the entire challenge. Since you have just made a statement which results in a contradiction if you are anything but a knight, he must conclude that you are a knight, or he must abandon logic. (The knave's answer is just as powerful.)
Mr. Smullyan, I am prepared to claim from your ghost the five and a third Internet Points which I have just won in fair combat. (Also, I loved your book.)
--------------
p.s. On the same piece of paper where I had written my solution in a dentist's waiting room last year, I had also noted, with amusement, the following:
"This sentence is false" is contradictory. But "I am a knave" is not!