Here's the second puzzle (which I was able to solve):
There's a group of pirates who have the following scheme for dividing booty: The pirates are ranked by ferocity. Starting with the most ferocious pirate, the pirate will propose a division of the loot (specifying exactly which pirate gets how much) and the pirates take a vote. If the majority vote for that division, it passes. In case of ties, it also passes. If it fails, then the pirates overpower the proposer and make him walk the plank, then repeat the whole process with the new most ferocious pirate proposing a division.
Suppose there are 100 pirates and the booty consists of 100 pieces of gold. What will be the winning proposal?
Again, start with the simplest case (let's number the pirates 1-100, with 100 being the most ferocious):
If there was only one pirate, he would propose that he keeps all 100, and that passes. Not too interesting.
What if there were two pirates? Well, since ties go to the proposer, the pirate 2 would propose the division 0 for 1, 100 for 2, and it would pass. Still not too enlightening.
How about 3 pirates? Well, pirate 3 knows that if his proposal doesn't pass, he walks the plank, and the pirate 2 will get 100. So pirate 2 will always vote against pirate 3's proposal if it gives him less than 100. But the pirate 1 gets 0 if pirate 2 has his way, so he'll vote in favor of anything that gives him more. So if 3 proposes, 1-0-99 it will be two votes to 1, and will pass. Now we're getting somewhere.
With four pirates, 1 and 3 will want the division 1-0-99 and won't accept less, but 2 will take anything better than 0, and since ties go to the proposer, 4 will win with the division 0-1-0-99.
5 will thus propose 1-0-1-0-98 to secure three votes, etc.
So with 100 pirates, the winning proposal will look like:
0-1-0-1-....-1-0-50
This result is, I think, pretty surprising. Not only is the distribution wildly uneven, but it depends on the parity of the number of pirates (which pirates benefit depends completely on whether there are an odd or even number of pirates). Which just goes to show that when you consider these sorts of I know that you know puzzles (the less ferocious pirates are only willing to accept piddling amounts like 1 because they can see that if they force a second vote it will go even worse), even simple rules can lead to complex outcomes.
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.
Foolippic: The Perspicacious Pirate Puzzle
I hardly update this blog any more...there's a vicious circle where I have few readers (based on site traffic), which makes it seem less worthwhile to blog here rather than in the blogs that have readers, even if it would be a suitable topic for this blog, which in turn causes fewer people other than spammers to stop by. Still I have two puzzles that I just learned about up at Foolippic, so I thought I'd mention it here just in case.