100 prisoners are given the sort of crazy deal they always get in these problems. Each prisoner gets a number. There's a room with 100 identical boxes in a row, each containing a random number from 1-100, with no repeats. Each prisoner, in turn and isolated from all the others, will get a chance to open 50 boxes of his choosing, one at a time. If each prisoner manages to find his own number in one of the 50 boxes he opens, all prisoners go free. The prisoners can make a strategy together at the beginning, but there can be no communication afterwards. The room is completely unmarkable, and will be reset to the exact same starting state for each prisoner.
Clearly if every prisoner picked randomly the probability that that prisoner would be successful would be 0.5 and therefore the probability they would all be successful would be 0.5^100 (read:practically zero, actually it's ~8*10^-31). What is the optimal strategy that the prisoners should use?
I'm just throwing out this completely random response. Each prisoner takes their Sharpie Marker in with them and marks each number in the boxes they picked on the bottom of the box. the first prisoner marks half the boxes then if the second prisoner doesnt see his/her number he opens the other half of the boxes. 😀 I know this isn't the right answer.
Can the prisoners communicate in a roundabout way by picking the boxes in order, then waiting a specified length depending on the numbers they pick? I haven't checked yet, but there must be some function that makes the amount of time spent a unique sum given a unique set of numbers. Eventually, the whole set of boxes should be mapped out guaranteeing success for the remaining prisoners.