Re: Prisoners' Dilemma
So still no solutions.

It occurred to me that I don't have a proof that the following is optimal (though I'm pretty sure it is, as it stores useful data of length n into blocks of length n, in the sense that it allows every prisoner to infer the previous box by looking at any box). It's optimal for small numbers, anyway.

Before being called in, the prisoners number themselves arbitrarily without the warden knowing (in order to beat any tactics the warden may have). Prisoner i₁ enters the hall and opens box i from the left. He transforms the name in that box to the number i₂ of the prisoner with that name, and then opens box i₂. Repeat until name is found.

To compute the chance of success for this strategy, we need to appreciate that what we're doing is picking a random 1 to 1 map from {1, ..., n} to {1, ..., n}. In other words, a permutation. Permutations split into cycles of repeated application, for example {1 -> 2, 2 -> 3, 3 -> 1} is more normally written (1, 2, 3). Find the input number and output the number to its right to apply the map.

The prisoners must succeed if all cycles in the permutation are of length less than n/2. We just need to apply a counting argument. There's n prisoners, so n! permutations (number of ways of picking n objects from a stack of n, without repetition and with ordering). On a set of i objects, there's (i-1)! i-cycles.

To count the number of permutations with an i-cycle (i≥n), we need to pick i elements (n choose i, or n!/(i!(n-i)!)), then find the number of ways they can form an i-cycle ((i-1)!), and the number of permutations on the remainder ((n-i)!). Multiply them together and you get n!/i, so the probability of a permutation containing an i-cycle is 1/i. Since we're only talking about cycles larger than half the length, if such a cycle exists, it's also the largest, so the probability of the largest cycle being of length greater than n/2 is (for even n) the sum, from i=n/2 to n of 1/i.

The integration rule tells us that this is less than the integral from n/2 to n of 1/i, which basic integration tells us is ln(n) - ln(n/2) = ln 2, which is about 0.7. In other words, using this strategy, our prisoners can win just under a third of times they normally would, and by the arbitrary rules, survive.


It turns out that this is too much of a hassle for the warden, especially since his apparently mathematically minded victims aren't dying, so he's now picked a new problem (for which answers can be found online, as this also is not an original problem). He groups the prisoners into tables of 3, and places black or white hats on their heads. They have long peaks, so prisoners can't see their own hat colour. The challenge is that the prisoners around the table must either guess their hat colour or pass.

If they any prisoner guesses incorrectly, the warden will not feed any of them. If at least one guesses correctly and the rest guess correctly or pass, they get fed. If they all pass, the hats are re-picked randomly and they can have another go. Servings are reduced, so the prisoners will die if they don't eat strictly more than half of all mealtimes. Can they survive? If so, does the warden have a tactic to defeat this survival by picking hats in a nasty way?