4.50 (2 votes)
Loading...
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?
The only information transfer that I can see is that if a prisoner gets called upon to open a locker, he knows that the previous prisoners were successful.
For the first prisoner to be successful, the chance is 50% at best. For the second prisoner, if he opens the half of the lockers, the chance is 500/999; for both to have found their names, the chance is only a tiny bit more than 25%. Thus, there can be no 30% strategy. (Well, bribe the jailer, I guess.)
solved by Monty Python with P=1. Just call every prisoner Bruce.
This is my favorite puzzle. The best thing is that the solution works also for infinite number of prisoners and then chance to succeed is 1-ln(2).
Ok, I deceived myself. Given the optimal strategy, the outcome is decided by the randomness in setting up the lockers – if they’re set up the right way, the prisoners will win, otherwise they’ll lose, and the chance that the setup is favorable to them is the cited ~30%.
Hint: the most favorable setup would be if each locker held its own name; the next most favorable would be if two of the slips of paper would be interchanged (how would you find your slip if that happened to your locker?); and from then on imagine the problem getting consecutively harder.