Are you ready for a new brain teaser? This time, you have to help a bunch of prisoners.
1000 prisoners are in jail. There’s a room with 1000 lockers, one for each prisoner. A jailer writes the name of each prisoner on a piece of paper and puts one in each locker (randomly, and not necessary in the locker corresponding to the name written on the paper!).
The game is the following. The prisoners are called one by one in the room with the lockers. Each of them can open 500 lockers. If a prisoner finds the locker which contains is name, the game continues meaning that he leaves the room (and leaves it is the exact same state as when it entered it, meaning that he cannot leave any hint), and the following prisoner is called. If anyone of the prisoners fails to recover his name, they all lose and get killed.
Of course they can agree before the beginning of the game on a common strategy, but after that, they cannot communicate anymore, and they cannot leave any hint to the following prisoners.
A trivial strategy where each prisoner opens 500 random lockers would lead to a winning probability of 1/2^1000. But there exists a strategy that offers a winning probability of roughly 30%.
Can you figure it out?