If you failed to solve Wednesday’s problem on Knights, Knaves and Crazies, take comfort from the fact that this has circulated among philosophers under the title “The Hardest Logic Problem Ever”. MIT philosopher George Boolos discussed it in the Harvard Review of Philosophy back in 1996. In that version, Crazies are never silent. But Oxford philosopher Gabriel Uzquiano soon observed that this can’t be the hardest logic problem ever, because it gets harder if the Crazies can be silent. Uzquiano’s new “hardest logic problem ever” was solved by the philosophers Gregory Wheeler and Pedro Barahona — and then solved again, substantially more elegantly, I think, in Wednesday’s comments section right here.
A few more thoughts, on the problem, its solution, and how to make it harder:
1.You’ll find a lot of clever ideas in Wednesday’s comments section. The best solution, I think, came from our commenter JaredS. Here’s my version of it, including some small improvements:
First: Keep in mind that if you ask a Knight or a Knave to predict the behavior of a Knight or a Knave, you’ll always get an answer, whereas if you ask a Knight or a Knave to predict the behavior of a Crazy, you’ll always get silence. So if you ask (say) Red to predict the behavior of (say) Blue and get an answer, you can rule out Blue as the Crazy. If you get silence, you can rule out Yellow as the Crazy.
Second: In view of that, if you ask Red to predict the behavior of Blue and get an answer, and then ask Blue to predict the behavior of Yellow, either you’ll get an answer (meaning Red is crazy) or you’ll get silence (meaning Yellow is crazy).
Third: Likewise, if you ask Red to predict the behavior of Blue and get silence, and then ask Yellow to predict the behavior of Red, you’ll either get and answer (meaning Blue is crazy), or you’ll get silence (meaning Red is Crazy).
Fourth: So. First ask Red to predict Blue’s behavior. If you get an answer, ask Blue to predict Yellow’s behavior, but if you get silence, ask Yellow to predict Red’s behavior. Either way, after two questions, you’ll have identified the Crazy.
Fifth: Now that you know who the Knight and Knave are, all you need is one question that Knights always answer “Cheech” and Knaves always answer “Chong”. For example: “Would the other guy say ‘Cheech’ if I asked him whether he’s a Knight?”.
That solves the problem in three questions.
2.This raises the issue: Can we do better? That in turn raises the issue: What does better mean? Do we want to reduce the number of questions we need in the worst case scenario or in the average scenario? It’s not hard to prove that in the worst case scenario, we’ll always need three questions; you can find an information-theoretic argument in the paper by Wheeler and Baharona, and similar arguments in our Wednesday comments section. (Start with the first comment by Mike H.)
3.We can nevertheless do substantially better on average. The procedure above suggests that we can start by asking Red to predict Blue’s response to anything at all. We might as well ask: “Would Blue say `Cheech` if I asked him whether he’s a Knight?”. Anyone who answers this question with Cheech (or Chong), and is subsequently identified as non-Crazy, is known to be a Knight (or Knave), rendering the third question unnecessary. So if we get an answer (as opposed to silence) on Question 1 or 2, we don’t need Question 3.
The only case in which nobody answers either of the first two questions is the case where Red is both Crazy and chooses to remain silent. That happens 1/9 of the time (a 1/3 chance of being Crazy and a 1/3 chance that a Crazy remains silent). So we only need the third question in 1/9 of all possible scenarios. On average, then, we need only 2.11 questions, as observed by our commenter Al V. Al (inspired partly by Mike H.) also does a quick information-theoretic calculation suggesting that it’s very unlikely any other procedure can do better.
4.If I wanted to devise the hardest logic problem ever, I’d do it like this:
First, imagine $n$ different responses you could get from your islanders. (In the problem at hand, $n=3$, the responses being ‘Cheech’, ‘Chong’, and ‘Silence’). We might as well rename these responses 1,2,…,n. Next, for any triple of subsets S, T and U of the set {1,…,n}, let’s define an islander of type (S,T,U) to be one who randomizes his response over set S when asked a question to which he knows the answer is yes, randomizes over set T when asked a question to which he knows the answer is no, and randomizes over the set U when asked a question to which he does not know the answer. You are now presented with a set of m islanders and an (unordered) list of their types (perhaps with repetitions). Call a list of types “allowable” if it’s possible, with a finite series of questions, to match the islanders with their types.
What is the algorithm for converting an allowable list of types into the shortest possible series of questions necessary to identify all m of the islanders?
Answer first where “shortest” means “shortest in the worst case scenario” and then where “shortest” means “shortest in the average scenario”.
Let me know when you’ve got it.
Re. #3, I am reasonably confident that there can be no solution better than JaredS’s (congratulations!), as optimized by Steve. The calculated optimal average number of questions is 2.062… Given that there are 18 possible scenarios (6 sequences of islanders times 3 possible answers by the crazy), the JaredS/Steve solution answers in 2 questions in 16 of 18 scenarios, and in 3 questions in 2 of 18. To do better would require an average 2.056 questions or less, which is below the information theoretical minimum of 2.062.
Let me make sure I understand the question. There are exactly 3 types of islanders (S, T, and U), and I am given the count of each? For example, m=9, and I am told that there are 4 S’s, 3 T’s, and 2 U’s? I assume they don’t have colored shirts any more, because that would give things away.
Sorry, I think I understand, but I still have a question. There can be up to m types, where each type is defined by the set of set responses. So, taking the prior problem, m=3, and the Knight’s set is {S,T,U}; the Knave’s set is {T,S,U}, and the Crazy’s set is {W,W,W}.
In the original problem, we don’t know if Cheech means Yes or No. So, in the example above, is {S, T, U} equal to {{Yes}, {No}, {Silence}}, and I still don’t know the meaning of Cheech and Chong, or has that been discarded?
Al V:
There are exactly 3 types of islanders (S, T, and U), and I am given the count of each?
No, no, no.
There are, say, 10 possible responses: 1,2,3,4,5,6,7,8,9,10.
There are some islanders who randomize over {3,4,5} when they know the answer to a question is Yes, over {5,6,7} when they know the answer is No, and over {1,10} when they don’t know the answer. These are called {{3,4,5},{5,6,7},{1,10}} islanders.
There are others who randomize over {1,2,3,4,5,6} when they know the answer is Yes, always answer 3 when they know the answer is No, and always answer 2 when they don’t know the answer. These are called {{1,2,3,4,5,6},{3},{2}} islanders.
Now you meet, say, 8 islanders. You are told that one of them is of type {{1,2,3},{4,5,6},{4}}, that 3 of them are of type {{1,2},{2,3},{3,4}} and that 4 of them are of type {{1},{7},{8}}.
Or alternatively, you meet, say, 6 islanders. You are told that two are of type {{1},{2},{3}}, three are of type {{4},{5},{6}}, and the last one is of type {{7},{8},{9,10}}.
Or maybe you meet 3 islanders. One is of type {{1},{2},{3}}, one is of type {{2},{1},{3}}, and one is of type {{1,2,3},{1,2,3},{1,2,3}}. If you think of “1” as meaning yes and “2” as meaning no, these islanders are a Knight, a Knave, and a Crazy.
The problem is to find an algorithm which, for any number of islanders, and any list of types, either tells you that they can’t be identified in finitely many questions or produces the optimal list of questions that will identify them.
So some questions (for clarification) and some thoughts on questin 4 the new hardest puzzle ever.
1a. If I’m told someone is of type {{1}{2}{3}}. Does that mean 1=true, 2=false,3=unsure or does it mean 1,2 and 3 are a permuation of true,false and unsure?
1b. I’m willing to believe we could get rid f the permutation part in a way similiar to saying “would you say “chong” if I asked you…” i.e. some transformation phrase, but I don’t have one handy. Anyone?
2. Can we assume that the islanders all know each others types? And that they all know that they all know each others types etc? I presume so but I’m not sure if it’s automatically impossible if they all say know there own type and have the same list as you.
3. Our strategy yesterday was to find someone who wasn’t crazy, and then ask her questions. Seems like if there is someone with distinct true and false sets then our strategy should be find them (or at least one of them) and then only address questions to them. They’re effectively a knight who knows the actual answer so we can then draw up the other (n-1)! (assuming no repeats) possible ways people could be assigned to types and ask them if the “right one” is in this half of ways every time. This can always be turned into a reallly long convoluted single question. So we’d need (in this case by this method) K+ceilling(log(n-1!)/log(2)), where K is however many we need to get the knightoid out.
It seems to me that the question is under-specified. Specifically it seems that the answer will depend on the meaning of the n different responses that can be given. E.g. in the previous question, it was necessary that Cheech and Chong were known to mean “yes” and “no.” If “Cheech” and “Chong” meant “Heigh-ho, the derry-o the farmer in the dell” and “xxxxxxxxx” (but we didn’t know which meant which), wouldn’t the answer to that question be different?
Jonathans (Kariv and Campbell):
Right. One special case of this “hardest logic puzzle ever” is:
One islander always says “Cheech” for Yes, “Chong” for No, and stays silent for “I don’t know”. Another says “Chong” for Yes, “Cheech” for No, and stays silent for “I don’t know”. A third always randomizes over Cheech, Chong and silence. Figure out who’s who.
Now that’s not exactly the same as the original problem, because it doesn’t actually require us to identify the Knight and the Knave. I was thinking that this is pretty much as hard as the original problem, so we might as well specify it this way.
But if you have a better way to ultra-generalize the problem, I will be happy to yield to it.
As to Jon K’s second question, yes, all islanders know that all islanders know that all islanders know…..each others’ types. But maybe the problem gets even more interesting if we drop that!!
Here’s a concrete problem:
There are four tribes. The Knights always answer truthfully if they can and stay silent otherwise. The Knaves always lie if they can and stay silent otherwise. The Slugs always say “I know the answer” if they know the answer and stay silent otherwise. The Crazies always randomize among “Yes”, “No”, “I know the answer”, and silence.
Unfortunately, they answer in their own language, where “Yes”, “No” and “I know the answer” are represented by “Gup”, “Hup” and “Jup”, in some order which you don’t know.
Howe do you identify four travelers, one from each tribe?
As stated, your harder problem has a solution, at least for the worst case variant, that is technically correct but not especially interesting.
The first thing we need to need to be to reason about this at all is to figure out what distinct questions we can ask. Define a Formal Question as a function mapping the set of permutations of the islanders to {Yes, No, Unknown}. I claim that any question we can usefully ask is equivalent to a Formal Question. The permutation of the islanders captures all information that is unknown to us and known to the islanders (this is not true in the previous problem, where the islanders know not just who answers “Cheech” for yes, but who is a Knight and who is a Knave–and indeed the questions there are not equivalent to Formal Questions as defined here). A question that relies on information that is unknown to the islanders is equivalent to the constant function mapping to unknown. A question that relies on information known to us and the islanders can be reduced to a Formal Question by partial application using the known value of that information.
Furthermore, all Formal Questions can be stated as questions:
“If I were to flip a fair coin right now, would it either be the case that you islanders were standing in one of the following permutations [the preimage of Yes] or be the case that you islanders were standing in one of the following permutations [the preimage of Unknown] and the coin came up heads?”
Now we can give the algorithm. Define a Strategy as a tree with a branching factor of n (the response), where each internal node is labeled with a Formal Question and an integer from 1 to m (the islander to ask). In an unlabeled Strategy, the leaf nodes are not labeled, while in a labeled Strategy, they are labeled with either a permutation of islanders or Unreachable.
An unlabeled Strategy is valid if each leaf node can be reached by at most one permutation of islanders. To check whether a given leaf node can be reached by a given permutation is easy: work backwards from the leaf node to the root, checking whether the branch from our current node’s parent to our current node is a possible response when asking the parent node’s question to the parent node’s islander. Checking validity is just a matter of checking all combinations of leaf nodes and permutations, of which there are finitely many in a finite Strategy, and we can label the leaf nodes as we do.
For given m and n, the number of Formal Questions and in turn the number of Strategies of a given maximum depth is finite. The algorithm to find the shortest worst-case Strategy is just to check all possible unlabeled Strategies of depth 1, depth 2, etc., until we find a valid Strategy.
Asking a question multiple times doesn’t help with allowableness, as we could get the same answer every time, so to check whether the list of types is allowable we just check whether the Strategy that unconditionally asks every islander every Formal Question is valid.
And so we see the difference between computability and complexity theory. This problem is not just computable, it is “elementary”, which means it has an algorithm with k-exponential running time for some finite k (i.e., it’s quadruply-exponential if I counted right).
A harder problem would be to find an “efficient” algorithm, but what that means is up for debate. Any valid Strategy will have at least m! leaf nodes. Unless there’s some prohibition on varying questions in response to previous answers, there’s no guarantee that will be more a more succinct way of listing the questions than an exponentially large tree. For that matter, a Formal Question is itself doubly-exponential in size. Even a doubly-exponential algorithm might require some actual insight into the structure of the problem.
The problem with applying this technique to the shortest average-case is simply that there can be an infinite number of Strategies whose average depth is bounded by a fixed depth d, but it wouldn’t surprise me if there’s some simple trick to find the shortest average-case with an even more ridiculous run-time.
However, I see another technical issue with the shortest average-case solution. An infinite Strategy can have a finite average-case depth. For example, we could start off finding the Crazy in the previous problem by asking everyone “Does 2+2=4?” in a cycle until someone is silent. While this is not optimal in the average case for that problem, we need to prove that the optimal Strategy for an allowable problem is never infinite. It’s not enough to bar infinite Strategies, for surely if the optimal Strategy is infinite, then there is no best finite Strategy, but rather an series of finite Strategies of increasing size (number of nodes) and decreasing average-case depth that approach the optimal infinite Strategy in the limit.
In general, I would be wary of thinking that you’re making something harder by replacing “Do X in some specific case” with “Give an algorithm that does X in the general case”.
For an extreme example, compare “find the shortest proof that you can of Fermat’s Last Theorem” and “A mathematical statement is allowable if it has a proof or a disproof in ZFC. Give an algorithm that, given an allowable mathematical statement, finds the shortest proof or disproof in ZFC.” In the first case, one would normally approach the problem via insights in number theory. In the latter case, one would explain how to enumerate and check formal proofs in ZFC.
A little thought experiment :
My islanders each have a favourite number. They wear this number proudly on a badge on their robes.
My questions are all very simple, I just say “answer!”
Some islanders (the Priwinkles) always answer “1”. Others (the Cockles) answer an apparently randomly-chosen number between 1 and P-1 (inclusive, P being their favourite number).
In fact, I know that all the islanders get their answers via the same method : they choose a random number coprime to P, then raise this number to the power of P-1 modulo P.
What is the most efficient way to distinguish the Priwinkles from the Cockles?
To fit #11 into Landsburg’s formalism, just assume that for both tribes P and C, we have S=T=U. For p\in P, S=T=U={1}. For c\in C, S=T=U={n: n is coprime to c’s favorite number}.
If you can solve this puzzle, then try the harder version where we actually know their favorite numbers.
I didn’t realize answers were posted here so I put my answer in the other thread, just now, and came up with something completely different.
I misread it (I didn’t realize a Crazy could voluntarily remain silent), but even then, my two question version still should work:
X=”are you a knight”
Y=”is the correct answer to X ‘cheech'”
Z=”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.”
Z will be answered ‘cheech’ by a knight, ‘chong’ by a knave, and can only answered by silence by a Crazy. So asking it twice will tell you what type all three natives are.
(Note that “tells the truth, lies, or remains silent” is not the same thing as “says ‘yes’, ‘no’, or remains silent”).
I feel this comments thread is incomplete with a link to this:
http://xkcd.com/246/