Prisoners and Urns

Here’s another interesting problem I received from one of my friends:

A Prison Warden is facing an overcrowding problem in his prison. Specifically, there are $N$ prisoners and he wants to play a game with them to reduce the overcrowding problem.

The game works as follows: the Warden will set up $N$ urns and place slips of paper with the prisoners’ $N$ unique names one per urn. Then he’ll bring one prisoner in at a time and let him look at up to $\frac{N}{2}$ urns sequentially, trying to find his name. If he finds his name, the warden will bring in the next prisoner. If he doesn’t find his name, the warden will execute all of the prisoners. The warden will explain the rules of the game to the prisoners and allow them to converse on a strategy, but after that, they are all separated and are thereafter not allowed to communicate with each other.

A na├»ve strategy is to have all $N$ prisoners look randomly at urns. However, this strategy would give the prisoners a survival rate of $\frac{1}{2^N}$. In a standard case of $N=100$, this gives a survival rate of about $7.89 \cdot 10^{-29} \%$… Not a good rate of survival at all.

Given that there are $N$ prisoners, and that each prisoner plays optimally:

  1. What is the optimal strategy the prisoners can use for survival?
  2. What would the expected survival rate be?

show