Blogosophy

The Adulterous Cannibals Puzzle

Since Richard Chappell kindly pointed out to me that there are subscribers to the blog such as himself who don't show up in site traffic reports, I've decided to go at least an extra yard and cross-post the puzzles from my other blog:

Here's the first of two puzzles that my mathematician friend presented me with when I was staying with him this weekend. We had been discussing evolutionary strategies and attribution of intensional states to other organisms, and from there to the I know that you know that I know kinds of thinking. A famous example is the Iocane scene in The Princess Bride, where Vizzini the Sicilian is trying to outreason The Man in Black as to which cup the of wine the deadly Iocane powder is in.
An interesting thing about this kind of reasoning, though, is that if you actually reason it out carefully it can have surprising results, and strategies that are not readily apparent.

Here's the first puzzle. The answer will be in the extended entry (btw, I needed a hint for this one).

Suppose there is a tribe of cannibals who have the following immutable law: if the husband knows the wife has committed adultery, he must put her to death the very next morning. However, nobody in the tribe feels at all compelled to inform a husband who has an adulterous wife. So everybody except the husband of the adulterous wife always knows that she's committed adultery, and everybody knows that everybody but the husband knows, but the husband is never told. As a result, although they have this law, no wife has ever actually been executed for adultery. A missionary comes to the village, and as always happens in stories about cannibals and missionaries, the cannibals pop him in the cooking pot. Before he dies, he says, "I have one thing to tell you: Adultery is being committed in this village!"
44 days later, 44 wives are executed for adultery. What happened?

Here's the hint that I needed: 44 is important because there were 44 wives committing adultery in the village; if the number had been different then the number of days and number of women would have that number instead.

Generally, the way to approach puzzles like this is to consider the simplist cases first.

What happens if there is only one adulterous wife in the village?

Well, if there is only one, everybody in the village except the husband knows. To everybody but the husband, the missionary's revelation is not news. Since he doesn't know, then up to that point he thinks that there's no adultery going on. When the missionary tells him that there is, he realizes that since he knows of none, it must be his wife that's committed adultery, so by law he must execute her the next day.

What happens if two women are adulterous? Everybody but the husbands of the adulterous women knows that two women are committing adultery, and each husband of the adulterous women knows of one case. So, since the cannibals are all very smart and realize the implications of this situation, each husband of an adulterous women expects that the woman he knows is committing adultery will be executed the next morning. When the next morning comes and that doesn't happen, he instantly realizes that husband of the adulterous wife hasn't realized it--but that can only be the case if there is an adulterous wife that husband does know about and he's expecting her to be executed. But if there's an adulterous wife that one husband knows about, but the other doesn't that means his own wife must be adulterous.

The rest is just induction. For each adulterous woman in the village the number of days that must pass before that woman's huband realizes that there is one case of adultery that he can't account for goes up by one. If the husband knows of N adulterous women, then he expects them all to be executed on day N. When day N passes without the executions occuring, there must be one and only one adulterous wife he doesn't know about--his own. Specifically if there are 44 adulterous women in the village, each husband of an adulterous woman knows of 43 and expects that on day 43 there will be 43 executions. When that doesn't happen he knows there are 44, and on day 44 all the women are executed.