|
This month's IEEE GlobalSpec Newsletter Challenge is:
The names of 100 prisoners are placed in 100 wooden boxes, one name to a box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; each may look in at most 50 boxes, but must leave the room exactly as he found it and is permitted no further communication with the others.
The prisoners have a chance to plot their strategy in advance, and they are going to need it, because unless every single prisoner finds his own name all will subsequently remain in prison for life.
Find a strategy for them which which has probability of success exceeding 30%.
[A comment: If each prisoner examines a random set of 50 boxes, their probability of survival is an unenviable 1/2100 ∼ 0.0000000000000000000000000000008. They could do worse—if they all look in the same 50 boxes, their chances drop to zero. Achieving 30% seems ridiculously out of reach—but yes, you heard the problem correctly.]
And the answer is:
This problem, inspired by a 2003 paper written by Danish computer scientist Peter Bro Miltersen, has become known as the "100 prisoners problem."
To solve it, the prisoners must first agree on a random labeling of the boxes by their own names. (The point of making it random is that it makes it impossible for the warden to place names in boxes in such a way as to foil the protocol described next.)
When admitted to the room, each prisoner inspects his own box (that is, the box with which his own name has been associated). He then looks into the box belonging to the name he just found, and then into the box belonging to the name he found in the second box, etc. until he either finds his own name, or has opened 50 boxes.
That’s the strategy; now, why on earth should it work? The process which assigns to a box’s owner the name found in his box is a permutation of the 100 names, chosen uniformly at random from the set of all such permutations. Each prisoner is following a cycle of the permutation, beginning with his box and (if he doesn’t run over the 50-box limit) ending with his name on a piece of paper. If it happens that the permutation has no cycles of length greater than 50, this process will work every time and the prisoners will be spared.
In fact, the probability that a uniformly random permutation of the numbers from 1 to 2n contains no cycle of length greater than n is at least 1 minus the natural logarithm of 2—about 30.6853%.
To see this, let k > n and count the permutations having a cycle C of length exactly k. There are 2n/k ways to pick the entries in C, (k−1)! ways to order them, and (2n−k)! ways to permute the rest; the product of these numbers is (2n)!/k.
Since at most one k-cycle can exist in a given permutation, the probability that there is one is exactly 1/k. It follows that the probability that there is no long cycle is
1 − (1/n+) − (1/n+2) − · · · − (1/2n = 1) − H2n + Hn
where Hn is the sum of the reciprocals of the first n positive integers, approximately ln m. Thus our probability is about 1 − ln 2n + ln n = 1 − ln 2, and in fact is always a bit larger. For n = 50 we get that the prisoners survive with probability 31.1827821%.
| 
5
Re: Bewildering Boxes: Newsletter Challenge (December 2019)
Good Answers:
"Almost" Good Answers: