100 Prisoners, 100 Boxes

The numbers 1–100 are randomly placed into 100 closed boxes, one per box. Each prisoner (numbered 1–100) enters alone and may open at most 50 boxes, seeking their own number, then leaves without communicating. All prisoners succeed or all die. Random guessing gives success probability (1/2)^100, but the optimal strategy (each prisoner opens their own box number, then the box matching the number found inside, following the cycle) does astronomically better. To the nearest whole percent, what success probability does it achieve?

• permutations

Source: Strategy first published by Anna Gal and Peter Bro Miltersen, 'The Cell Probe Complexity of Succinct Data Structures' (2003); popularised as a puzzle by Peter Winkler. Statement written for AxiomIQ.