The Hundred Boxes

Question

100 prisoners are numbered 1 to 100. A room contains 100 boxes; a uniformly random permutation assigns one prisoner's number to each box's interior. One at a time, each prisoner enters, opens at most 50 boxes of his choice, and must find his own number; boxes are restored before the next prisoner. No communication is allowed once the process starts, but the prisoners may agree on a strategy before

Accepted Answer

The strategy. Prisoner k opens box k, reads the number inside, opens that box next, and keeps following. The box-contents map is a permutation pi, and this walk traces the cycle of pi containing k, which necessarily passes through the box containing number k just before returning to box k. So prisoner k succeeds iff his cycle has length at most 50, and the whole group succeeds iff the permutation has no cycle longer than 50. The clever part: everyone's fate is welded to a single property of one shared permutation, replacing 100 near-independent coin flips with one event of constant probability. The probability. For k > 50, a permutation of 100 can contain at most one k-cycle, and the number of permutations containing one is binom100k(k-1)!,(100-k)!, so P(textsome cycle of length k) = fracbinom100k(k-1)!,(100-k)!100! = frac1k. These events are disjoint across k = 51, dots, 100, hence P(textfail) = sum_k=51^100 frac1k = H_100 - H_50 approx 0.6882, qquad P(textsuccess) approx 0.3118. As n to infty the failure probability tends to ln 2, so success tends to 1 - ln 2 approx 0.3069, bounded away from zero forever, against an unaided 2^-n. Why interviewers love it: the answer is secondary

The Hundred Boxes

Problem

Your answer

Hints

More Probability to train on