Locker Problem

This is an instance of the "100 prisoners" problem . Regard the placement of hats into lockers as a permutation $\sigma$ on $\{1,\dots,2n\}$ so that locker $q$ contains hat $\sigma(q)$ . The goal of prisoner $p$ is to find locker $q$ such that $\sigma(q) = p$ . He can do this by following a cycle in $\sigma$ . Prisoner $p$ first opens locker $p$ , then locker $\sigma(p)$ , then locker $\sigma(\sigma(p))$ , and so on. This cycle is sure to contain $p$ , and if the length of the cycle is no more than $n$ , the prisoner is guaranteed to find his hat within the allotted number of turns. For all the prisoners to find their hats, $\sigma$ must contain no cycles with length greater than $n$ , and this happens with probability $1 - (H_{2n} - H_n),$ where $H_n$ denotes the $n$ th harmonic number. For large $n$ , this probability is approximately $1 - \ln 2 \approx 0.3069,$ so the desired value is $\lfloor 1000(0.3069) \rfloor - 1 = 305$ . The Wikipedia article linked above gives the derivation of this probability.