Prisoners finding numbers

posted Jul 22 '12

aa1062
31 ● 4

A prison contains $n$ prisoners, labeled $1, 2, 3, \dots, n$.

One day the warden announces that he is going to set up a room with $n$ drawers in it, labeled $1, 2, 3, \dots, n$. He will then place, uniformly at random, $n$ pieces of paper with the numbers $1$ through $n$ in the $n$ drawers (each number is on precisely one piece of paper, each piece of paper has exactly one number, each drawer contains exactly one piece of paper).

Next, the prisoners will be let into the room one by one, where they will each be given the opportunity to open $n/2$ drawers of their choice (rounded up if $n$ is odd) and inspect the paper inside. Once the game has started the prisoners may not communicate with one another, although they are given the opportunity to strategize beforehand.

If every prisoner finds their number, all the prisoners are set free; otherwise they are all executed.

Devise a strategy for the prisoners which guarantees at least 30% chance of success, no matter how large $n$ is.

Note: observe that the first prisoner alone has only 50% (or 50% + $\epsilon$ if $n$ is odd)of success in finding his name, and that if the prisoners all choose the drawers they inspect at random, their chances of success are $(1/2)^n$ which is vanishingly small if $n$ is very large.