Printable PDF
##### Department of Mathematics, University of California San Diego

****************************

## Permutations and the Plights of Prisoners

##### Abstract:

200 prisoners, scheduled for execution, are given one chance for survival. Their 200 names are put in a row of 200 boxes, one name per box. Each prisoner will enter this room, one at a time, and open 100 boxes with the goal of finding his or her own name. If every prisoner does this successfully, all will go free. If any one fails to find his or her own name, all will be executed. The boxes will be closed after each prisoner and once a prisoner has entered the room, any attempt at communication with the others will be punished by execution. However, the prisoners are allowed to strategize beforehand. In fact, a strategy exists which gives, roughly, a $\frac{1}{3}$ probability of survival. Can you find it? No Googling! We'll consider this problem and the fate of other unfortunate hypothetical prisoners, mostly as an excuse to discuss some combinatorics of permutation enumeration.

### AP&M B402A

****************************