Prisoners, boxes, and beautiful graph theory

There are 1000 prisoners and the warden decides to play the following game.

The prisoners are numbered 1 through 1000.
There is a room with 1000 boxes, numbered 1 through 1000.
There are 1000 pieces of paper, each numbered 1 through 1000.

The pieces of paper are randomly distributed one per box. (That is, paper #445 is just as likely to be in box #445, box #1, or any other box.)

Each prisoner will be taken in turn into the room with the boxes. He will open boxes of his choice one-by-one until either he finds the piece of paper with his own number on it or he has opened 500 boxes. Then he must leave and the room is reset. No communication between the prisoners is allowed once the game has begun.

If every prisoner finds the piece of paper with his or her number, then they will all be released. If a single prisoner fails to find his or her paper, then all of the prisoners will be locked up forever.

The prisoners are allowed to form a strategy before the game begins. What is the optimal strategy for the prisoners?

Approximately what is this strategy's probability of success?

[Note: there is both a cool graph-theoretic approach to this problem and also a group-theoretic approach. The end result of both is very simple and very beautiful. Have fun.]

×