(This is a snapshot of my old weblog. New posts and selected republished essays can be found at raganwald.com.)
Friday, May 16, 2008
A Few Easy Ones from Raymond Smullyan
Many of you are familiar with the canonical ‘liar and truth teller’ puzzle. Raymond Smullyan
is a logician who has taken the basic idea and expanded it to produce an immense variety of challenging puzzles. He has even used variations on the theme to illustrate Incompleteness Theory and other logic esoterica.
Here are a few easy ones to give you a taste of his sumptuous banquet:
Dr. Tarr is a psychologist with the Department of Health. Her job is to inspect asylums to determine whether they are in compliance with the law. Asylums have Doctors and Patients. In a compliant asylum, all the doctors are sane and all the patients are insane. Clearly, an asylum with an insane doctor or a sane patient is Not A Good Thing.
Sane persons are correct in all of their beliefs. Insane persons are incorrect in all of their beliefs. Both sane and insane persons are scrupulously honest: they always state what they believe to be the case. Unfortunately, the asylums are very modern and do not use identifying devices such as uniforms, ID tags, or other devices to show which persons are doctors and which are patients. Nor is it possible to know whether a person is sane or insane by any means other than questioning them.
One day, after inspecting a number of asylums, Dr. Tarr was having a drink and cigar with her good friend Professor Feather. The professor found her work interesting and asked her to recount some of her findings.
“Well,” said Dr. Tarr, “at the first asylum I visited, I met an inhabitant who made a single statement. I immediately took steps to have them released.”
“Wait,” interjected the professor, “so you’re saying this person was not an insane patient?”
“Of course,” replied Dr. Tarr.
Professor Feather thought for a moment, then asked “How is that possible? This sounds like the old Liar and Truth Teller puzzle. This person either told the truth or they lied. But there are four possibilities for any person in an asylum: Sane Doctor, Insane Patient, Insane Doctor, or Sane Patient.
“Even if you knew whether they were lying or telling the truth, that would only narrow the matter down to two possibilities. For example, if they told a truth such as ‘two plus two equals four’, you would know that they were Sane. But how would you know that they were a Patient, not a Doctor?”
Dr. Tarr replied with a chuckle “I agree that I could not have deduced what to do based on an inhabitant saying ‘two plus two equals four’. But in this case, the patient was quite intelligent and thought of a single statement which could establish the fact that only a Sane Patient could make that statement.
“I’m sure if you think about it, you could construct such a statement. Name a statement which could only be uttered by a Sane Patient.”
…
Dr. Tarr and Professor Feather shared a chuckle over that one. Then the professor took a more serious tone. “But have you ever had to remove a Doctor from an asylum?”
“Yes,” said Dr. Tarr sadly, “it has happened. Doctors do go insane once in a while. Recently I had just such a case. As it happened, I was visiting an asylum for the very first time and the first inhabitant I met made a single statement. I immediately had the inhabitant transferred to a special institution for former Doctors.”
“Don’t say it!” exclaimed the professor, “I want to work it out for myself…”
…
“Another time,” continued Dr. Tarr, “I was visiting an asylum which had been placed on probation for irregularities such as Insane Doctors and Sane Patients. I asked an inhabitant ‘Are you a patient’, and she said ‘yes’.”
“What did you do next?” asked Professor Feather. “Did you need to do any more investigating?”
…
“I’m glad you worked that out. Another asylum was on probation and I decided to ask the very same question of the first inhabitant I met. This time, when I asked ‘Are you a patient,’ he replied ‘I believe so…’.” Do you think I knew enough to close the asylum?
Professor Feather thought about this one for a very long time.
Spoiler I: V nz abg n fnar qbpgbe.
Spoiler II: V nz na vafnar cngvrag.
Many of you are familiar with the canonical ‘liar and truth teller’ puzzle. Raymond Smullyan
is a logician who has taken the basic idea and expanded it to produce an immense variety of challenging puzzles. He has even used variations on the theme to illustrate Incompleteness Theory and other logic esoterica.Here are a few easy ones to give you a taste of his sumptuous banquet:
Dr. Tarr is a psychologist with the Department of Health. Her job is to inspect asylums to determine whether they are in compliance with the law. Asylums have Doctors and Patients. In a compliant asylum, all the doctors are sane and all the patients are insane. Clearly, an asylum with an insane doctor or a sane patient is Not A Good Thing.
Sane persons are correct in all of their beliefs. Insane persons are incorrect in all of their beliefs. Both sane and insane persons are scrupulously honest: they always state what they believe to be the case. Unfortunately, the asylums are very modern and do not use identifying devices such as uniforms, ID tags, or other devices to show which persons are doctors and which are patients. Nor is it possible to know whether a person is sane or insane by any means other than questioning them.
One day, after inspecting a number of asylums, Dr. Tarr was having a drink and cigar with her good friend Professor Feather. The professor found her work interesting and asked her to recount some of her findings.
“Well,” said Dr. Tarr, “at the first asylum I visited, I met an inhabitant who made a single statement. I immediately took steps to have them released.”
“Wait,” interjected the professor, “so you’re saying this person was not an insane patient?”
“Of course,” replied Dr. Tarr.
Professor Feather thought for a moment, then asked “How is that possible? This sounds like the old Liar and Truth Teller puzzle. This person either told the truth or they lied. But there are four possibilities for any person in an asylum: Sane Doctor, Insane Patient, Insane Doctor, or Sane Patient.
“Even if you knew whether they were lying or telling the truth, that would only narrow the matter down to two possibilities. For example, if they told a truth such as ‘two plus two equals four’, you would know that they were Sane. But how would you know that they were a Patient, not a Doctor?”
Dr. Tarr replied with a chuckle “I agree that I could not have deduced what to do based on an inhabitant saying ‘two plus two equals four’. But in this case, the patient was quite intelligent and thought of a single statement which could establish the fact that only a Sane Patient could make that statement.
“I’m sure if you think about it, you could construct such a statement. Name a statement which could only be uttered by a Sane Patient.”
…
Dr. Tarr and Professor Feather shared a chuckle over that one. Then the professor took a more serious tone. “But have you ever had to remove a Doctor from an asylum?”
“Yes,” said Dr. Tarr sadly, “it has happened. Doctors do go insane once in a while. Recently I had just such a case. As it happened, I was visiting an asylum for the very first time and the first inhabitant I met made a single statement. I immediately had the inhabitant transferred to a special institution for former Doctors.”
“Don’t say it!” exclaimed the professor, “I want to work it out for myself…”
…
“Another time,” continued Dr. Tarr, “I was visiting an asylum which had been placed on probation for irregularities such as Insane Doctors and Sane Patients. I asked an inhabitant ‘Are you a patient’, and she said ‘yes’.”
“What did you do next?” asked Professor Feather. “Did you need to do any more investigating?”
…
“I’m glad you worked that out. Another asylum was on probation and I decided to ask the very same question of the first inhabitant I met. This time, when I asked ‘Are you a patient,’ he replied ‘I believe so…’.” Do you think I knew enough to close the asylum?
Professor Feather thought about this one for a very long time.
Spoiler I: V nz abg n fnar qbpgbe.
Spoiler II: V nz na vafnar cngvrag.
Comments on “A Few Easy Ones from Raymond Smullyan”:
<< Home
That first one has me stumped, because as far as I can tell: any true statement made by the speaker about himself will be the same whether it's said by a sane patient or an insane doctor (eg "I am a patient") whereas any true statement made about any other subject will be the same whether it's said by a sane doctor or a sane patient. As far as I can see, that's an exhaustive set of all possible statements right there, so I'm stumped.
There's a clue in that Smullyan used these puzzles to illustrate Imcompleteness Theory -- a hospital denizen can make a statement about the logical rules of the system.
Aidan:
You are mistaken: I wrote that they were easy. That does not mean I found them easy, or that I solved them at all.
Some logic problems rely on an Aha! insight. if you get it, are you smart? It is impossible to tell from one problem. We tend to think that if someone consistently has Aha! insights into math and logic puzzles they are intelligent, but who can say from one puzzle?
Likewise, some puzzles have a basic structure. Perhaps you found them excruciatingly difficult or even impossible to solve them when you first saw them. Then you were shown the structure, and you learn how to solve them by applying rules or heuristics.
Now are you smart? Or is it just that you have acquired an algorithm?
Quite frankly, I consider recreational problems like this to be similar to rock climbing. If you have more skill and more experience, you could brag about climbing harder problems. But the benefit for me is that you have a wider variety of things you can climb for pleasure, because you can do the easy ones, the middling ones, and some of the hard ones.
Now having said all that, I will tell you the truth: I put "easy" in the title to encourage people to try them and not give up too quickly.
You are mistaken: I wrote that they were easy. That does not mean I found them easy, or that I solved them at all.
Some logic problems rely on an Aha! insight. if you get it, are you smart? It is impossible to tell from one problem. We tend to think that if someone consistently has Aha! insights into math and logic puzzles they are intelligent, but who can say from one puzzle?
Likewise, some puzzles have a basic structure. Perhaps you found them excruciatingly difficult or even impossible to solve them when you first saw them. Then you were shown the structure, and you learn how to solve them by applying rules or heuristics.
Now are you smart? Or is it just that you have acquired an algorithm?
Quite frankly, I consider recreational problems like this to be similar to rock climbing. If you have more skill and more experience, you could brag about climbing harder problems. But the benefit for me is that you have a wider variety of things you can climb for pleasure, because you can do the easy ones, the middling ones, and some of the hard ones.
Now having said all that, I will tell you the truth: I put "easy" in the title to encourage people to try them and not give up too quickly.
Does the solution have to do with two beliefs in one statement?
"I believe that 2+2=4, and I believe that I am a patient."
Two beliefs. One correct, one inferred correct.
Likewise, "I believe that 2+2=5 and I believe that I am a patient" indicates an insane doctor.
I haven't puzzled through the second few yet.
"I believe that 2+2=4, and I believe that I am a patient."
Two beliefs. One correct, one inferred correct.
Likewise, "I believe that 2+2=5 and I believe that I am a patient" indicates an insane doctor.
I haven't puzzled through the second few yet.
@Jake:
This doesn't work as Smullyan views a statement with an 'and' in it as a a single sentence where both clauses have to be true for the sentence to be true.
So, "I believe that 2+2=4, and I believe that I am a patient."
Could be said by both an insane doctor, and a sane patient.
For the insane doctor the second clause of the sentence, "I am a patient" would be false, so he would believe the whole sentence to be true.
As a slight spoiler for the first one, think how many people could make the statement "I am a sane doctor"?
This doesn't work as Smullyan views a statement with an 'and' in it as a a single sentence where both clauses have to be true for the sentence to be true.
So, "I believe that 2+2=4, and I believe that I am a patient."
Could be said by both an insane doctor, and a sane patient.
For the insane doctor the second clause of the sentence, "I am a patient" would be false, so he would believe the whole sentence to be true.
As a slight spoiler for the first one, think how many people could make the statement "I am a sane doctor"?
Could we get a source for these? I'd certainly like to see more. Is it a specific book or a number of them?
Art:
They are adapted from one of his books, I can’t remember which one right now, but I will flip through them a little later and find them.
They are adapted from one of his books, I can’t remember which one right now, but I will flip through them a little later and find them.
"What is the name of this book", by Raymond Smullyan, has lots of puzzles of this form. Generally, Knaves always lie and Knights always tell the truth, and it gets more and more complicated as the book proceeds.
What I'm wondering is who worded the puzzles in the post: If it's Smullyan, it's certainly not an excerpt from that book. If it's someone else, it was definitely done in Smullyan's style.
What I'm wondering is who worded the puzzles in the post: If it's Smullyan, it's certainly not an excerpt from that book. If it's someone else, it was definitely done in Smullyan's style.
r:
Raymond wrote many books of puzzles. The affiliate link above will take you to an Amazon search for his name, or you can browse for much more stuff.
What's the name of this book was just the tip of his creative iceberg: in some of his stories there are people who tell the truth during the day and lie at night while others tell the truth at night and lie during the day... and everyone is underground and never knows what time it is!
In this particular case, the puzzles are his but I reworded them slightly in an email in 2000 or so. I republished that email here to give folks something to laugh about on a Friday, my last couple of posts feel a bit on the heavy side, and I wanted to recapture some of the fun in life.
Raymond wrote many books of puzzles. The affiliate link above will take you to an Amazon search for his name, or you can browse for much more stuff.
What's the name of this book was just the tip of his creative iceberg: in some of his stories there are people who tell the truth during the day and lie at night while others tell the truth at night and lie during the day... and everyone is underground and never knows what time it is!
In this particular case, the puzzles are his but I reworded them slightly in an email in 2000 or so. I republished that email here to give folks something to laugh about on a Friday, my last couple of posts feel a bit on the heavy side, and I wanted to recapture some of the fun in life.
Eric:
I have posted a spoiler answering the first question.
If you want to continue to puzzle it out, here's a hint:
What you say is perfectly correct for most simple predicates: they only divide the possible search space in half. It is possible to find two predicates such that the intersection of the two searches identifies a single outcome.
I have posted a spoiler answering the first question.
If you want to continue to puzzle it out, here's a hint:
What you say is perfectly correct for most simple predicates: they only divide the possible search space in half. It is possible to find two predicates such that the intersection of the two searches identifies a single outcome.
@Chris,
I figured that might be the eventual flaw in my idea, but I also wasn't sure if there was a differentiation between a statement and a belief. Thanks for the description/hint!
I figured that might be the eventual flaw in my idea, but I also wasn't sure if there was a differentiation between a statement and a belief. Thanks for the description/hint!
I think I've found an alternative solution to 1 and 2 - given the assumption of self-knowledge:
Vs lbh nfxrq fbzrbar jvgu gur fnzr nggevohgrf nf lbh, "Ner lbh n fnar cngvrag?", jbhyq gurl fnl lrf?
3 was simpler for me, but I'm not sure I'm grokking the final idea about belief though.
Vs lbh nfxrq fbzrbar jvgu gur fnzr nggevohgrf nf lbh, "Ner lbh n fnar cngvrag?", jbhyq gurl fnl lrf?
3 was simpler for me, but I'm not sure I'm grokking the final idea about belief though.
If the riddles of Raymond Smullyan likes you, then this web ( http://4chests.blogspot.com) too. Sure.
Cu
Cu
<< Home
