Lee WA hundred prisoners, a hundred drawers and odds that look hopeless until they aren’t.
A hundred prisoners are numbered 1 to 100. In a room are 100 drawers, each holding one of their numbers, shuffled at random. One by one, each prisoner goes in alone and may open 50 drawers looking for his own number, then leaves everything as he found it. If every prisoner finds his number, they all go free. If even one fails, they all die. They can plan beforehand but can’t talk once it starts. Roughly what chance of freedom can they give themselves?
Let the number you find in each drawer tell you which drawer to open next.
Each prisoner opens the drawer with his own number on it, then the drawer numbered with whatever he finds, and so on round the loop. They all succeed unless the shuffle holds a loop longer than 50, and that happens only about 69 per cent of the time.
Open drawers at random and the chance is a half to the power of 100, which is as near nothing as makes no difference.
Source: Anna Gál and Peter Bro Miltersen, 2003, in the form told by Peter Winkler