The best dozen or so puzzle books ever written are, without a doubt, the works of Raymond Smullyan. If you’ve never encountered these, stop right now and order yourself a copy of What is the Name of This Book?, which is brilliant on multiple levels. On the surface, it’s a book of particularly amusing little brain teasers. One level down, those brain teasers contain a proof of Godel’s Incompleteness Theorem — solve all the riddles and you’ll have painlessly understood the proof!
Smullyan’s books are heavily populated by Knights who always tell the truth, Knaves who always lie, and bewildered travelers trying to distinguish one from the other via their cryptic utterances. Today’s puzzle is Smullyan-like in its set-up but considerably more difficult than most. It’s been proposed and discussed in philosophy journals, but I’m suppressing the sources (and rewording the problem) to make it a little harder to Google. I’ll of course pay appropriate homage to the authors when I post solutions in the near future. Meanwhile, if you’ve seen this before, or if you’ve found the answer on line, please restrain yourself from posting spoilers. But do post whatever you manage to come up with on your own.
And now to the puzzle:
As so often happens in these puzzles, you find yourself on an island populated by three tribes: The Knights, the Knaves, and the Crazies. Each tribe dresses only in one color — a different color for each tribe. The islanders all know which tribe wears which color, but you, as an outsider, do not. When asked a yes/no question, a Knight will always answer truthfully if possible, or remain silent otherwise. (For example, if you ask him whether your next coin-flip will turn up heads, a Knight remains silent, because he can’t be sure of giving a truthful answer.) A Knave will always lie if possible, or remain silent otherwise. A Crazy will randomly tell the truth, lie, or remain silent.
And oh — one more thing. They answer in their own language, where “Cheech” means Yes and “Chong” means No — or perhaps it’s the other way around. You’ve lost your phrasebook and you can’t remember.
So you’re walking along the road, when you meet a group of three natives, one dressed in red, one dressed in blue, and one dressed in yellow. You can ask as many yes/no questions as you like, but each question must be directed to just one native.
Your goal, of course, is to figure out who belongs to which tribe.
How many questions do you need to be sure of achieving your goal?
It takes three questions.
There are six combinations, we need to extract 2.5849 bits of information in order to determine who is who.
One question is insufficient – there are only three possible answers, and there’s a 1/3 chance we asked the crazy. This is only 1.0566 bits of information, which is insufficient.
With two questions, if we target them at different individuals, that’s still only 2.1133 bits of information : 1.0566 from the 1 in 3 chance we don’t quiz the crazy, and 1.0566 from the 2 in 3 chance that we do. This is still insufficient. Targeting the same individual with two questions also yields only 2.1133 bits of information.
Only with 3 questions can we obtain a guaranteed 3.1699 bits of information, which is sufficient to identify who’s who.
The existence of such a set of 3 questions is left as an exercise to the diligent student.
I don’t think it’s true to say that Knaves always lie they just speak a language where Cheech and Chong mean the opposite things
If you ask either knight or knave what the crazy would say about anything, they will remain silent.
If you weren’t trying to minimise questions, you could keep asking one person the same question. If there was always the same answer, he is not the crazy.
Say you ask red what yellow would answer to the question “Are you a knight?” several times. We either get silence all the time (yellow = crazy) or random answers (red = crazy) or consistent “cheech” or “chong” (blue is the crazy).
Not efficient, but at least a start.
Question for Landsburg, when you say “They answer in their own language,…”, is “they” the collection of all Islanders together (i.e. they have their own language, but there is only one language on the island) or do you mean “they” as in each tribe may have their own language (therefore as many as 3 on the island)? Said another way, does “Cheech” necessarily translate as “yes” (or as “no”) to all islanders?
Question 1 should be: Do you know they’re giving away free beer and pizza to Crazies in the next village, but blocking access to anyone else?
It can be addressed to any one of them, as long as it is asked loudly enough. After the Crazy guy heads off in that direction, we’ve reduced the problem to a simple Knight/Knave problem.
eg Asking either of the remaining two “Are you a knight” will tell you what which of “Cheech” and “Chong” means “yes”.
Then asking any question to which the answer is known to all will tell you whether the person asked is a knight or knave.
This solution does, of course, rely on the crazy guy not being too crazy!
EricK- Hilarious!
If I had hair, I would wear it like that guy.
I’ll need 5 questions.
Will not post my questions for now not to spoil anyone’s fun or in case someone comes up with with a more efficient solution.
Is it valid to ask the same question more than once? If so, then I think you only need one question, but you have to ask it more than one time.
@9: That would not only be fair but good for style points I’d say.
I think that I have a good start, but I can’t seem to get past not knowing which of “Cheech” and “Chong” is “Yes” and “No”.
Q1-Q3) Ask each individual if he is wearing the color that he is wearing (e.g. ask person dressed in red if he is wearing red, etc.)
The answers to these questions will either definitively identify the Crazy (if he is silent) or identify a bloc of 2 that contains the Crazy (2 of the individuals will offer the same answer, if the Crazy does not remain silent[the crazy is one of the set of 2 offering the same answer]).
I’ve got a minimum of 6 questions, max of 7:
Questions 1-3: Ask each one of them individually, “Are you a Knight?” Regardless of how the Crazy answers, you will get at least 2 yes answers (from the Knight and Knave) and will have decoded their language.
Questions 4-6: Ask each of them individually, “Are you wearing an X colored robe?” X being whatever color they are actually wearing. Three scenarios:
Scenario 1: You get a Yes, a No and a Silent in response. In this case, the Yes is the Knight, the No is the Knave and the Silent is the crazy. So you are done.
Scenario 2: You get 2 Yes answers and one No. Now you know the No is the Knave.
To distinguish between the Knight and the Crazy you as the Knave 1 question: “How would the guy to your right answer the question, are you a Knight?” If the Knave answers, then the guy to the right is the Knight. If he remains silent, then the guy to the right is the Crazy.
Scenario 3: You get 2 No answers and one Yes. Now you know the Yes is the Knight.
To distinguish between the Knave and the Crazy you as the Knight 1 question: “How would the guy to your right answer the question, are you a Knave?” If the Knight answers, then the guy to the right is the Knave. If he remains silent, then the guy to the right is the Crazy.
“Without a doubt” seems a bit strong. Have you tried either of Peter Winkler’s books of Mathematical Puzzles? They’re probably my favourite.
I’m too lazy to spend much time on this but some observations
1. I suspect you need to ask some second-order questions, like “Would a man in red and a man in blue agree on …” or “what would he say about …” Questions about the reponses of others.
2. When checking your answer beware of ‘random’ The Crazy could perfectly mimic a Knight or a Knave and you have to be able to handle that.
3. If the island is on a frictionless surface and you throw inhabitants off the east end it’s a westward rocket.
Nice work; I figured we’d be looking at a lot of self-referential questions.
So you ask the first guy, “Are you a Knight?” and he says, “Cheech.” You ask the second guy and he says “Cheech.” You don’t really need to ask the third guy, right? So perhaps you can reduce the minimum number of questions to 5.
Nice Andrew
@Andrew,
Wouldn’t the minimum be four questions? If the crazy person stays silent or says no on the first round, you would know he’s the crazy person. Then you could ask one of the other two, is your shirt the color he’s wearing and you’d know who he was.
@Leo – if you ask a Knight or a Knave “is 2+2 equal to 4?”, the Knight will say “yes”, and the Knave will say “no”. But if you ask “If I were to ask you if 2+2 was 4, would you say ‘yes’?” or “Are you a Knight?” then both say ‘yes’. So it’s not just that they speak different languages. You can’t always find a Knight’s answer by reversing the Knave’s.
@ Andrew,
In fact I think the minimum is three depending on which order you end up asking the questions to. If the first or second person is the crazy person and he stays silent, you know he’s the crazy, and than using my question from 17 to either the knight or the knave, you’d know who is who.
The only remaining question I think is, is the max 7 or is there some smaller number of questions. Not really sure about that one yet.
loveactuary (#4): They all share one language.
Andrew (#12): Very nice.
Now can you either lower that maximum or prove it can’t be lowered?
@Daniel,
Good points. Just to think this through for myself here, assuming you luck out in round one and ask the crazy first and he stays silent, you’d still have to ask one other person “are you a knight?” to decode the language. Then ask that same person about the color of their robe and you’d have it with only 3 questions.
So, min of 3, max of 7 depending on the helpfulness of the crazy.
Andrew and Daniel, don’t you think you are getting a bit sidetracked with this “3 questions min” thing?
The question was “How many questions do you need to be _sure_ of achieving your goal?”, not “How many questions are enough if you are extremely lucky”… The answer to this question would really be just 0 – if you are sure of your luck you will simply guess everyone’s tribe…
Meanwhile – is 7 your last word? Going once..
@14 Ken B
My 5 question solution is not relying on any second-order questions – but who knows, maybe you can arrive a a more efficient solution using them?
Starting a thread: I ask the man in Yellow about the man in the Red shirt, “If I ask the man to your left if his shirt is Red, what would he answer?” Then I ask the man in Yellow, “If I ask the man to your right if his shirt is Blue, what would he answer?” If the answer is anything but Silence and Cheech or Silence and Chong, then I know he is the Crazy, because the Knight and the Knave would both answer Silence and No.
I’m not totally certain of this proof and it relies on the fact that we definitely need 3 questions to know the language. The following proof makes the assumption that for the first three questions we can only be certain to ascertain the language, and not necessarily any other information.
We know that no matter what we ask the knight or the knave in the second round of questions, the crazy person could mimic either the knight or the knave in this round of questions. So we would need at least one more question, after we know which person isn’t the crazy person to figure out which person is the crazy person.
@Dmitry Kolyakov,
You’re right, but it’s still an interesting question. Asking 0 questions wouldn’t make you sure of anything. It’s possible after 3 questions you would be sure. That was our only point.
@Steve – Thanks.
I think I can get the max down to 6.
First, ask two of the three guys, “Are you a Knight?”
Scenario 1: You get two different answers (Cheech and Chong).
So, then you have to ask the third guy to figure out the translation. However, in this case, the Crazy has exposed himself by answering differently than the other two. Simply ask one of the others about their robe and you have all of their identities in 4 questions.
Scenario 2: You get two of the same answers.
So, you have the translation. Then follow the second set of questions in #12 above (questions 4-6 and the resulting scenarios in that case) to get all of their identities in a maximum of 6 questions this time.
Here however, one might be tempted to ask the third guy, “are you a knight?” just to see if the crazy exposes himself.
Scenario 3: Explained in #23. 3 questions.
I think the answer is three questions, as long as you can ask really long questions.
You ask each islander. “I have a procedure that will identify which of you is a Knight, which is a Knave, and which is a Crazy.” Explain this procedure to the islander (e.g., one of the ones mentioned in a previous post). “After implementing this procedure, I will ask the islander to your immediate right a question whose correct answer is Cheech if they are a Knave, and Chong otherwise (if you are speaking to the right-most islander, ask them about the left-most islander). How will they answer?”
The Knave will answer Cheech if the Knight is to his right, and will be silent otherwise. The Knight will answer Chong if the Knave is to his right, and be silent otherwise. Since one of them will be silent, that pins down which islander is a Crazy. The remaining islander essentially tells us what he is, and we’re done.
Presumably there is a more elegant way of doing this.
@ 28
Sure, I was not implying you were somehow mistaken, just getting sidetracked a bit.
It is indeed possible to be sure after only 3 questions, but to achieve that, I believe you will have to ask your questions in a sub-optimal order that will drive your total up if you are less lucky (hence, sidetracking)
@25:
I look forward to it. Andrew’s does.
Here’s my rationale. There is a bit of flab in pinning down cheech/chong FIRST rahter than as part of a more complex structured answer where you get the identities together with (or even better without!) knowing cheech and chong. Otherwise the cheech/chong is just a pre-pass and so this fails the good puzzle theorem.
My second thought is this. We can ask about uncertain events to which people must be sient, and we can ask about implications. Questions like “Would Andrew’s approach in 12 identify the islanders?” or “Would Andrew’s questions lead the other two to say cheech?” Using implications should allow us to reduce the number of questions. I suspect we can use questions like this to make Andrew’s more “efficient”. Just an intuitive thing, I have no answer in mind.
In any case I would bet heavily that 7 is NOT the best answer possible.
If I have established that the man in Yellow is the Crazy, then I ask the man in Blue, “If I ask that man if his shirt is Red, what would he answer?” Whatever he answers I know means No, so then I can ask him if his shirt is Blue to establish his identity.
If, on the other hand, the man in Yellow answerss Silence and Cheech (or Chong), then I know that he is Crazy, or that the person about which he didn’t respond is the Crazy. So, let’s hypothesize that Yellow answers Silence and Cheech. Next I ask the man about whom Yellow responded Cheech (Blue in this example), “If I ask that man if his shirt is Red, what would he answer?”
If Blue is silent, I know that Red is the Crazy, and that Cheech means No. Now I can just ask him the color of his shirt to determine if he is Knight or Knave.
If Blue answers Chong, then Yellow is the Crazy and Chong means No. Again, I can just ask Blue’s shirt color to determine who is Knight/Knave.
You can definitely answer in 5. I’m not sure if it can be determined in 4.
I think it’s three. Spoilers ahead (under the dubious assumption that I got this right).
Question 1: Ask blue what red would say if I asked red if he were a knight. If yellow is crazy, then the yes/no answer reveals all identities. If blue is crazy, I know nothing. If red is crazy, blue would remain silent.
So let’s say I get an answer. That means that either blue or yellow is crazy. So I ask red what yellow would say if I asked yellow if he were a knight (Question 2, given red is not crazy). If red is silent, then yellow is crazy. If red answers, blue is left as the crazy one, and red’s yes/no answer tells me the last two identities.
If I didn’t get an answer from blue in the first place (red is crazy), I ask blue what yellow would say if I asked yellow if he were a knight (Question 2, given red is crazy). The yes/no answer gives me the identities of blue and yellow.
So within 2 questions, I can ascertain the identity of the crazy as well as a Cheech/Chong answer that – once translated – gives me the other two identities. So I ask either of the non-crazies Question 3: Are you a knight? He will surely answer with the island’s word for “yes.”
Extending #32, if Blue answers Cheech, then I know that Cheech means No, and that Yellow is Crazy. Thus, I can just ask Blue if his shirt is Blue to determine if he is Knight or Knave. So, it can definitely be done in 4 every time.
@ Dmitry Kolykov,
Now I see where you’re going with that. Andrew illustrated that point in #29. I’ll try to see if I can get the maximum down to 5 then.
“Your goal, of course, is to figure out who belongs to which tribe.”
There are 3! = 6 possible assignments so intuitively you need 2 and a bit bits, or 3 questions. That may not be achievable with the cheech/chong thing but my hope is that there is a solution in 3 questions that leaves undecided what cheech means. THAT would be pretty!
@Ken B, right. There are 12 possible combinations: the 6 that you include, times the 2 Cheech/Chong possibilities. Thus, 4 questions are required.
@Pete, I’m not sure I follow. If Blue answers Cheech to question 1, that doesn’t mean he is not crazy – Cheech could be a random answer.
@34
Wow! Liked that one!
But still:
You write: “If I didn’t get an answer from blue in the first place (red is crazy)” – But what if you did not get answer because the blue was crazy?
Disregard #40. I misread. However, if Blue answers Cheech, then Red answerss Cheech, how do I know if Red or Yellow is the Knight?
@ 30 Tom,
So, you asked you incredibly convoluted question to all 3 of them, and, assuming you did not get eaten for such an abuse, got 2 silences and 1 “Chong”. So, what are your next actions?
@ 38 and 39
Are you incorporating the randomness element introduced by the crazy person in your calculations?
@ 43 Dimitry
Since I got two silences, the Crazy must have been silent.
That means the islander who answered Chong is the Knight, and that the person to his right cannot be Crazy (or the Knight would not have answered). So he must be the Knave, and the last one is Crazy.
@Pete, if Blue is silent to Q1, he could be crazy.
@39: Not necessarily. You are NOT asked for cheech/chong only tribal membership.
@45
“…That means the islander who answered Chong is the Knight” – And why is that? Why not a Knave?
@KenB: I considered that in paragraph 4. Did I miss something?
I can find a solution with max 5 questions, but I’m not sure there isn’t a more efficient one.
Questions:
1. Ask Red: What would Blue say if asked whether Red is crazy?
2. Ask Yellow: What would Blue say if asked whether Yellow is crazy?
3. Ask Blue: What would Red say if asked whether Blue is crazy?
4. Ask Yellow: What would Red say if asked whether Yellow is crazy?
If the answers to 1 and 2 are silence, Blue is crazy.
If the answers to 3 and 4 are silence, Red is crazy.
If neither of the above, then Yellow is crazy.
If the answers to 1 and 2 are silence, the answer to 4 means Yes.
If the answers to 3 and 4 are silence, the answer to 2 means Yes.
If neither of the above, the answers to 1 and 3 are the same and mean Yes.
5. Ask any non-crazy: Is your shirt [the color of the shirt]?
If the answer to 5 is yes, he is the knight and the remaining non-crazy is the Knave. Otherwise, reverse that.
I’m pretty sure it takes max 4 questions to identify the crazy. If you ask them right, you’ll also learn the language. The last question identifies the Knight/Knave.
Sorry KenB, that was intended for AlV.
If Blue answers Cheech, then Red answers Cheech, I know that Red says “Cheech” when asked what Yellow would say if I asked Yellow if he were a knight. In other words, I’m simplifying the problem to a truthteller/liar case because Blue is clearly the crazy one. I don’t know what Cheech means until after I ask the third question. Then I can go back and use my newfound translation to find out what Red REALLY said about Yellow. If Red says “yes,” Yellow WOULD claim to be a knight, then Red is the knight; he is truthfully claiming that Yellow would lie about being a knight. If Red says “no,” Yellow would say that he is a knave, then Red is the knave; nobody but the crazy would claim to be anything but a knight. The key is that I don’t obtain my translation until after I’ve identified the crazy. This way, I only have to ask “are you a knight?” once.
To summarize my posts (26, 33, 36), I use the shorthand X=Cheech, Z=Chong, S=Silence. I ask Yellow, (1) “If I ask [indicate man in Red] if his shirt is Red, what would he answer?” and (2) “If I ask [indicate man in Blue] if his shirt is Blue, what would he answer?”
If answers are S-S, X-Z, Z-X, X-X, or Z-Z, go to (A). If answers are S-X, S-Z, X-S, or Z-S, go to (B).
(A) Yellow must be Crazy. Ask Blue (3) “If I ask [indicate man in Red] if his shirt is Red, what would he answer?” and “Is your shirt Blue?” If his answers match, he is the Knave [both Knight and Knave would answer No to (3)]. If his answers are different, he is the Knight.
(B) Ask the man about whom Yellow responded X or Y, (3) “If I ask that man [not Yellow, so let’s use Red for argument’s sake] if his shirt is Red, what would he answer?” If he is silent, go to (C). Otherwise, go to (D).
(C) We know Red is Crazy. Ask Blue, “Is your shirt Blue?” If he answer is the same as Yellow answered to (1) or (2), then he is the Knave and Yellow is the Knight; otherwise, vice-versa.
(D) Yellow is Crazy and Blue’s answer to (4) means No. Ask Blue, “Is your shirt Blue?”, which will tell if he is Knight or Knave.
@45 I am sorry, I missed that you linked your Chong to the knight. Make it 2 silences and a Cheech please.
Ah, AlV and Dmitry: I see the problem. Definitely have to think on that one. Might need a fourth question.
Sorry, typo in 52. (B) should read: Ask the man about whom Yellow responded X or Y, (4) “If I ask that man [not Yellow, so let’s use Red for argument’s sake] if his shirt is Red, what would he answer?” If he is silent, go to (C). Otherwise, go to (D).
Anyway, can be done in 4. Could be done in 3 if there is a way to determine identity without knowing whether Cheech or Chong means No.
@ 48
If I set up my questions right, a Knight will only ever answer Chong, and a Knave will only ever answer Cheech. They may not answer if a Crazy us to their right, but if they do answer. Thanks for pointing out I forgot to cover this case.
@ 1
I found your post helpful, but I’m puzzled by something. Suppose all three islanders wear the same colour. Then there are only three combinations, but no finite number of questions can identify which group you are speaking to with certainty. So how do you reconcile this with your bit calculations?
Ok, As I see Al V. has found a quicker 4-question solution (but I am still not yet convinced by the 3-question ones), here is my 5-step solution not using questions of second order:
1. First 3 questions: Ask everyone a question with has an obviously affirmative answer: “Are you an islander?”, “Is 2*2=4”, “Aren’t questions of second order mind-boggling and disgusting?”, etc.
Two options here:
1a. The Crazy shows himself by remaining silent. In that case:
question 4a – ask one of the non-crazies “Are you a knight?” (the answer will have to mean “yes”) If his answer is the same as to the first question he answered, he is the knight, and we already know the crazy so the third is the knave. Same logic for the knave who would answer differently from his first question.
1b. The Crazy does not remain silent and joins either the knight or the knave. So we have 2 similar and 1 different answers. (3 similar are not possible, as the knight and the knave will have to differ). Then we know that the different one is not crazy. So we ask:
question 4b: “Are you a knight?” Again, as in 4a, if the answer is the same as in his fist question, we know he is the knight, if different, the knave. We also learn the language as, the knight’s answer to the first question will mean “yes” and the knave’s “no”. Now that we know both the language and if our friend is the truthful one, we ask the same islander
question 5b: “Is this man crazy?”, pointing at one of his friends. Once we have his answer, knowing his trustworthiness and the meaning of his words we can see who is crazy and feel in the gaps.
Of course there are variations to this approach (validating apparently false statements, asking “are you a knave” and so on).
Thanks to Professor Landsburg for posting!
@57
What do you mean “if you set up them right”? Do you have in mind some questions different from what you wrote?
Based on your questions as you presented them however do you believe that if someone says Cheech and the remaining 2 are silent, this person would be the knave?
Why not the knight who would truthfully say that his neighbor the knave would’ve said Cheech to your hypothetical question?
@Dmitry, the only reason for including the possibility of silence is to require second order questions. Therefore, I don’t see how there can be any efficient first order only solutions.
@60
I am not sure I understand – maybe I am using a different definition of “second order”?
For me a second order question is one where a respondent is required to predict some other person’s future answer to a hypothetical question (hence the second order) as opposed to validating a fact. What is your definition?
So you do not accept my solution or do not accept that it does not include questions of second order?
” the only reason for including the possibility of silence is to require second order questions” – I am not sure how you arrived at this. The possibility of silence (and craziness) is added for another level of complexity which makes solutions (both involving and not involving unnatural convoluted questions) more varied and interesting.
@ 59
“Do you believe that if someone says Cheech and the remaining 2 are silent, this person would be the knave?” Yes.
The Knight would not say Cheech because, if the Knight was answering, the person on his right must be a Knave. The Knave will answer Chong to a question whose correct answer is Cheech, and the Knight will report that.
#61, Our definitions of second order are the same. What I mean is that it would be challenging to ask a first order question that has three possible responses (Cheech, Chong, or Silence) A first order question such as “Is your shirt blue?” could only receive a Yes or No response. A first order question that would be answered with silence would have to ask something like, “Will it rain tomorrow?” or “Is there a God?”, but then the alternate answers would not be all that useful – a response of Cheech or Chong would tell you that the person is the Crazy, but Silence would tell you nothing.
So, we know that the problem can be solved in 4 questions, but in theory could be solved in 3. @Ken B points out that this could work in theory, so long as we can determine the identities without needing to know whether Cheech means Yes or No. The problem with my solution above is that it is dependent on first determining if someone is telling the truth or not, and then using that information to determine the identities.
It seems to me that Pete was on the right path by asking second order questions about identity. Only in that way can we reduce the solution to 3 questions.
@ 62
Unfortunately I was totally confused by the wording of your original post.
So to put your idea more simply, you would ask the following question:
“If I managed to ask you neighbor to the right a question to which he would have to answer “Chong” unless crazy, what would he say?”
If that is what you meant, and we allow questions relying on subjects’ predictive logic (apparently we do), than my hat off to you! This is brilliant!
There have been a lot of clever answers in the thread. Some of
them, however, are invalid because they violate the stated
restrictions of the problem. “What would Blue say…” is not a
valid question because it’s not a yes/no question. “Would Blue
say chong” is a yes/no question, but it limits your flexibility.
@ 64
But what is wrong with Tom’s 3-question solution? I think we have a winner!
@66
Actually a very valid point! If you see thing from this prospective, maybe I was too quick to congratulate people on their 4 and 3 question solutions :)
@ 62 Yes. Sorry for the confusion. Your wording is clearer. I was worrying about what would happen if the islanders did not believe such a question could be asked, in which case their answers would be odd.
@ 66 Very good point. I think you can still get away with asking three questions if you condition your question on whether Cheech means true or not, as follows.
“If Cheech means true, I will ask your neighbour to the right a question to which he would answer Chong whether or not he is a Knight or a Knave. If Chong means true, I will ask your neighbour to the right a question to which he would answer Cheech whether or not he is a Knight or a Knave. Will he answer Chong?”
If Cheech is true, a Knight will answer this question with Cheech, because the Knave will answer the question Chong, and so my guess is correct. A Knave will answer with Chong because my guess is correct and the Knave must lie. If Chong is true a Knight will answer this question with Cheech, because my guess that the Knave will answer the question with Chong is incorrect. But the opposite must be the case if the Knave answers
So regardless of which term means true, the Knight will be the one who answers Cheech and the Knave Chong.
Scalia solves three problems like every day before breakfast, btw.
We don’t need to find out their language to find out who they are. Suppose you ask “X” and get an answer ‘Cheech’. There are five possibilities :
1) You were asking the Knight, and ‘Cheech’ means ‘Yes’
2) You were asking the Knave, and ‘Cheech’ means ‘Yes’
3) You were asking the Knight, and ‘Cheech’ means ‘No’
4) You were asking the Knave, and ‘Cheech’ means ‘No’
5) You were asking the Crazy, and ‘Cheech’ means nothing at all.
You could, instead, have asked “Here I have a coin, on whose faces I have written ‘Cheech’ and ‘Chong’. Suppose I asked you ‘X’, and placed the coin showing your answer face up – or if you remained silent, I tossed the coin. Would the coin show ‘Cheech’?”
In case 5, nothing has changed.
In case 1, the Knight thinks ‘I would answer Cheech which means “yes”, because the truthful answer to X is “yes”. So the coin would show Cheech, so the answer is yes, or in my language, Cheech’ “Cheech!”
In case 2, the Knave thinks ‘I would answer Cheech which means “yes”, because the truthful answer to X is “no”. So the coin would show Cheech, so the answer is yes, or in my language, Cheech’ “Chong!”
In case 3, the Knight thinks ‘I would answer Cheech which means “no”, because the truthful answer to X is “yes”. So the coin would show Cheech, so the answer is yes, or in my language, Chong’ “Cheech!”
In case 4, the Knave thinks ‘I would answer Cheech which means “no”, because the truthful answer to X is “yes”. So the coin would show Cheech, so the answer is yes, or in my language, Chong’ “Chong!”
Note that in all these cases,
* the Knight or Knave answers ‘Cheech’ if the correct answer to X is ‘Yes’
* the Knight or Knave answers ‘Chong’ if the correct answer to X is ‘No’
You can check this still holds if the answer given to X is ‘Chong’. For example, if the truthful answer to X is ‘No’, and you ask the knight (for whom ‘Chong’ means ‘No’) “Suppose I asked you ‘X’, and placed the coin showing your answer face up – or if you remained silent, I tossed the coin. Would the coin show ‘Cheech’?” Then he would think :
“The truthful answer is ‘No’, so I would say ‘Chong’, so the coin would show ‘Chong’, so the answer to this complicated question is ‘no’, which in my language is ‘Chong’.” Chong!
Again, we find the truthful answer to X.
If X has no answer, both knights and knaves think “If he asked X, I would remain silent, so he would toss the coin – I don’t know what it would show. I’d better remain silent”
In summary:
For any question X, let Q(X) be the question “Here I have a coin, on whose faces I have written ‘Cheech’ and ‘Chong’. Suppose I asked you ‘X’, and placed the coin showing your answer face up – or if you remained silent, I tossed the coin. Would the coin show ‘Cheech’?”
Then, as long as we are asking a Knight or Knave,
* the answer to Q(X) is Cheech if the truthful answer to X is ‘Yes’
* the answer to Q(X) is Chong if the truthful answer to X is ‘No’
* the answer to Q(X) is silence if X has no truthful answer.
It’s surely easy to construct a three question solution, using questions fo the form Q(X).
Note, however, that the questions can’t all be ‘yes/no’ questions, or we only get 2/3 of a bit of information per question. To reach 2.58 bits of information with only two more yes/no questions, we’d need to be sure we identified the crazy with the first question – and we can’t be sure of that, since we might have asked the crazy something. At least one of the questions must be a ‘yes/no/silence’ question.
@Tom #57 So how do you reconcile this with your bit calculations?
Not sure. Perhaps my bit calculations only give a lower bound? I only studied information theory for 1 week, and didn’t pay attention because I thought it wouldn’t be in the exam. On the other hand, the basics are simple enough. I used bit calculations and information entropy as the backbone of the AI in my online mastermind game : http://bit.ly/15h9oCo
@Dimitry
#61 For me a second order question is one where a respondent is required to predict some other person’s future answer to a hypothetical question (hence the second order) as opposed to validating a fact.
#58 here is my 5-step solution not using questions of second order: …… “Are you a knight?”
When you ask “Are you a Knight”, are you not asking the respondent to “predict [their] future answer to hypothetical [as yet unspecified] questions”, as well as asking them to validate a fact?
I am not convinced that the order of a question is not a slippery concept to pin down.
A somewhat controversial observation: all the second-order question solutions are dependent on the implied assumption that the islanders are perfectly logical (as opposed as simply answering about facts they know).
This assumption is not validated anywhere in the problem. The problem says that the islanders will answer according to their tribe if possible. If they are not capable of understanding or processing syllogisms (and given that some questions suggested here need to be re-read several times even by non-islanders to be understood, it is quite possible) they will remain silent.
Formal logic and syllogisms in particular were only developed in ancient Greece and are virtually unknown in many tribal cultures. As our problem defines the islanders as “tribes”, one clearly can not take their logical prowess for granted. (heck, even not all Nobel laureates are always logical)
So in reality I guess all the clever second-order questions will be met with an awful lot of silence from the natives…
@73 Mike H
You wrote: “When you ask “Are you a Knight”, are you not asking the respondent to “predict [their] future answer to hypothetical [as yet unspecified] questions”, as well as asking them to validate a fact?”
No. I am asking them about a fact they know, full stop. Then I proceed to make _my_ logical inferences from that fact as opposed to asking _them_ to engage in any logical exercises.
3 question solution:
Assign them an arbitrary cycle in your mind. Ask each one a question about what the next guy would say that, when asked to a Knight about a Knave or vice versa, tells you whether they’re a Knight or a Knave without knowing the language. The Crazy is identified because the Knight and Knave must remain silent when asked about him.
Concretely, ask each one:
Would [next guy] say “Cheech” if I asked him, “Are you a Knight?”?
At least one will remain silent, when you ask a non-Crazy what the Crazy would say. They will not all remain silent, because the question is well-posed to a Knight about a Knave or vice versa, and they will not both be asked about the crazy. There are only three, so there will be a unique one who answers non-silently about one who remains silent.
Arbitrarily, call them:
A: answers “Cheech” or “Chong” about B
B: remains silent about C
C: doesn’t matter
C is Crazy. If A were crazy, B would not have been silent about C. If B were crazy, A would have remained silent.
When asked, “Are you a Knight?”, both a Knight and a Knave will say yes in their language.
Suppose “Cheech” means yes. Then it is true that B would say “Cheech” if asked, “Are you a Knight?”. Thus, if A is the Knight he will respond to your question with yes, or “Cheech”, and if he is the Knave he will respond with no, or “Chong”.
Suppose “Chong” means yes. Then it is false that B would say “Cheech” if asked, “Are you a Knight?”. Thus, if A is the Knight he will respond to your question with no, or “Cheech”, and if he is the Knave he will respond with yes, or “Chong”.
In either event, A is the Knight if he said “Cheech” and the Knave if he said “Chong”.
Obviously, you’ll be able to stop after two questions if you happen to ask the Knight and Knave first, but that can’t be guaranteed.
12 possibilities eg (cheech = yes, blue = knight, yellow = knave, red = crazy). Whilst the meaning of cheech is not an explicit part of the solution set, I think it is part of the solution space because the definition of a knight is someone who says cheech|chong to a true statement.
Each question has three answers so can at best be a trifurcation of options.
At least 3 questions required as 3^2 < 12 < 3^3.
So, am I left to believe that their names are in no way whatsoever correlated to the appearance associated with any of their societal titles?
Do the knights bear swords, ride horses and wear armor?
Do the knaves have stained aprons and a generally unkempt appearance?
Are the crazies not unequivocally crazy, and therefore don’t suffer schizophrenic, psychopathic, or whatever strange episodes crazies generally suffer from to be identified as crazy?
If yes, then you might not need to ask a question at all. If no, then this brain-teaser should be upgraded to “brain-tormentor” because it’s not very fun, Professor. =[
Dmitri 74
I like this BUT it is not right. We are told we get truth from knights, falsehood fom knaves. Nothing subjective there; they are specified to be oracular.
I will remark snakily that if you read much here or at a few sites on the blog roll you will see the truth of Dmitry’s observation!
Ken B 79:
Actually, the puzzle specifies “…if possible”. If, for example, a particular Knight is mute, then it would not be possible for him to answer truthfully — he would just remain silent to all questions.
JaredS:
Very nice, but I think there’s a step missing; let me try to fill it in.
We put them all in a circle and ask each guy: Would the guy on your right say “Cheech” if I asked him, “Are you a Knight?” If one guy is silent, the crazy is to his right. If two guys are silent, the crazy is the one just right of the other.
This makes it sound like I have to query all three of them to identify the crazy. Because (writing A for “answered” and S for “silent”):
If the first two answer AA, the first guy is Crazy.
if the first two answer AS, the third guy is crazy.
If the first two answer SS, the second guy is crazy.
If the first two answer SA, I don’t yet know what to think.
So I want to avoid “SA”. The way to do this, if the first guy is Silent, is to proceed *left* around the circle, turning the first guy into the second guy. Then I’m sure to have either AS or SS.
This allows me to identify the Crazy in two steps *provided* I make my decision about which way to proceed around the circle *after* I get one answer.
Now you can use your third question to separate the Knight from the Knave.
@Steve, if I am following you and @JaredS correctly, JaredS’s solution requires an average of 2.44 questions to determine the solution. Yours requires an average of 2.11, because only in the situation where the first question is directed to the Crazy, AND he is silent, do you require 3 questions.
Al V: My variant of JaredS’s solution always requires three questions.
@John w 80
Yes, but possible is a strong word. The stipulation is not if he knows but truth if possible. Take a frequent example here Goldbach’s conjecture. Steve would burn a question asking the knight, and get an answer …
So, if each question provides 1.58 bits of information, then 2.11 questions provides 2.64 bits of info, which is just above the 2.58 minimum. There is no way to do better, I think.
@Steve, I don’t think it does. The way JaredS phrased the questions, the Knight always answers Cheech, or is silent. The Knave always answers Chong, or is silent.
So, I ask the first person the question. If he answers Cheech, he is either the Knight or crazy. If he answers Chong, he is either the Knave or crazy. In either case, I proceed to the right. If the second person is silent, I am done, as the third person must be crazy. If the second person responds Cheech or Chong, then the second person is Knight or Knave based on his answer, and the first person was crazy. In either case, I am done in two questions.
If the first person is silent, I proceed to the left (thus asking the third person the second question). If the second response is silence (1/9 of the time), I need a third question. If the second response is Cheech or Chong, then that person is Knight or Knave, depending on the response, and the unquestioned person is crazy.
There are 18 possible scenarios, and only two require a third question.
Steve:
My method doesn’t require that I know who the crazy is after 2 questions, because once I know who the crazy is, I know retrospectively who the Knight and Knave are based on the answers they already gave. The question plays a dual role in separating Knight from Knave and finding the crazy. The last half on my explanation isn’t about a new question, it’s about why A’s answer to the question he was already asked tells us whether he’s a Knight or a Knave.
Suppose the first two answer SA.
If the third answers S, the first person is crazy and the second is a Knight iff the answer he already gave was Cheech.
If the third answers A, the second person is crazy and the third is Knight iff the answer he just gave was Cheech.
Your ordering change improves the number of questions in expectation, of course, to the point that it’s doubtful you can do better on information theoretic grounds, as Al V observes.
Jared S (and Al V): Yes, you’re right.
Pete (#35): Sorry for the delayed response; I haven’t had time to read all of these carefully as they were posted:
I like the way you start off, but I lose you here:
If I didn’t get an answer from blue in the first place (red is crazy)
This does not seem to follow. If you didn’t get an answer from blue in the first place, maybe blue is crazy.
Edited to add: And now I see that Al V. mentioned this in 46.
My fourth question will be to the knight : “Is there a proof that all the non-real complex roots of the analytic extension of sum 1/n^s have real part 1/2?”
My fifth and succeeding questions will be devoted to extracting the shortest possible proof or the simplest possible description of a counterexample.
Now that JaredS has solved the problem without knowing whether Cheech means yes or no, I wonder what the most efficient solution is that also provides the meaning of Cheech and Chong. We see it can be done in 4 questions (restating my questions as “If I asked the man to your left if his shirt was Red, would he agree?”), but following MikeH’s model, doing so requires 3.58 bits of information, and in theory that could be answered with 2.78 questions.
@79 Ken B
I know it’s sort of nerdy, but I’d still like to defend my assertion.
You wrote: “We are told we get truth from knights, falsehood from knaves. Nothing subjective there; they are specified to be oracular.”
I am sorry I missed any references to the oracular in the original problem – pardon me, it must be my eyesight :)
Here is what we are literally told:”…Knights who always tell the truth, Knaves who always lie”
So if you ask me something like “Are there freshwater fjords in Europe?” and I say “I do not know” (or keep silent, if I were an islander), am I not telling you the truth? I believe I am. I really do not know (at least for sure).
I might be again misled by my non-native English, but to me to tell the truth means to adequately and fully communicate what one knows without deliberate distortion. It is not the same as “know everything possible, possess perfect logic and impart that knowledge on those interested every time” – the second would indeed be oracular and would be obviously different.
A comparable example: If you say that I always give to the poor, you do not mean that I own unlimited resources, do you? You most likely mean that I donate (communicate a fact) when I am approached for it (asked a question) and have the means (know the answer)
Dmitry Kolyakov 92:
I agree. The phrasing could be improved. How about something like this:
Members of the Knight tribe will always answer your question correctly if a logically and unambiguously correct answer exists.
Members of the Knave tribe will always answer your question incorrectly if a logically and unambiguously incorrect answer exists.
@AlV #91 that sounds like a nice puzzle…
@92: The none of the solutions works. Because this particular knight just daydreams all day and knows nothing. He can’t even answer if he’s a knight, just so clueless.
The problem is really about statements known to be true or false, or indeterminate.
Let Y be “is the answer to X ‘cheech'”. If the answer is ‘cheech’, that’s equivalent to saying ‘yes’ to X, and if the answer is ‘chong’, that’s the equivalent of saying ‘no’ to X. This is the case even if they said ‘yes’ or ‘no’ because they lied.
“Tell me whether the correct answer to Y is the truthfulness of your answer to this question” will produce the answer to Y from anyone (knight, knave, or crazy). You can ask it three times (with X being various ‘are you a ___’) and get correct yes/no answers all three times, which is enough to tell 6 combinations apart.
If you want to do better than that you need more than one bit per answer, which is possible by asking a question that a crazy cannot answer with either a yes or a no. Use a disjunction. “Tell me, in the case that you are not a crazy, whether the correct answer to Y is the truthfulness of your answer to this question, and in the case that you are a crazy, whether your answer to this question is the negation of the truthfulness of your answer to this question” will get an answer to Y from a knight or knave, and no answer from a crazy. If X is ‘are you a knight’ and Y is the cheech version from above, then the entire question will be answered ‘cheech’ by a knight, ‘chong’ by a knave, and not at all by a crazy. This provides an obvious way to do it in 2 questions.
I’m sure there are more elegant formulations.
(There is a common solution ‘if I were to ask you if you were X and your two friends gave the same answer, what would you answer?’ This doesn’t work because a false proposition such as ‘if (impossible thing)” implies any proposition.)
@ 95 Ken B
This is somehow not like your usual logical self :)
The problem says explicitly: “The islanders all _know_ which tribe wears which color”
So if you are genuinely afraid a knight is not sure if he is a knight you can mitigate it by asking “Are islanders wearing (his color) knights?” instead.