Problem bank

Problem 23 of 333MediumBrainteaserP023

100 prisoners and boxes

  1. 100 prisoners are numbered 1-100. In a room there are 100 boxes with each prisoner's number inside, in random order. Each prisoner enters alone, may open 50 boxes, must find their own number, and leaves without communicating. If all 100 succeed they go free. With a naive strategy P(all succeed)=(1/2)100P(\text{all succeed}) = (1/2)^{100}. Is there a strategy with much higher success?