Question 130
Suppose there are 100 prisoners, each of whom is given a number between 1 and 100. There is also a room with 100 boxes, labeled 1 to 100, and 100 pieces of paper with the numbers 1 to 100 on them. Each piece of paper is randomly placed inside one of the 100 boxes.
One at a time, each prisoner is allowed to enter the room and open at most 50 boxes to see the numbers inside. If every prisoner opens the box with his own number inside it, they will all be released. They are not allowed to communicate at all during this process, but they can come up with a strategy beforehand. Show that there is a strategy that gives them at least a $30\%$ chance of winning.
One at a time, each prisoner is allowed to enter the room and open at most 50 boxes to see the numbers inside. If every prisoner opens the box with his own number inside it, they will all be released. They are not allowed to communicate at all during this process, but they can come up with a strategy beforehand. Show that there is a strategy that gives them at least a $30\%$ chance of winning.