There are 100 prisoners each with a unique name. There are 100 boxes, each one containing a single prisoner's name such that every name is in exactly one box. Each prisoner has to select and open up to 50 boxes and if his name is not in any of these 50 boxes then all the prisoners are executed. They go through this process one at a time, each prisoner finishing before the next begins. They can communicate to come up with a strategy before beginning, however, they cannot communicate in any way after the process has begun.
What is the best strategy that results in the prisoners' greatest chance of survival? Hint: It is greater than 30%. And if that's too easy, prove that this is the optimal strategy.
Posts
IOI 2023: Overtaking
11 months ago
Funnily enough I was trying to remember exactly how this puzzle was set up the other day. I first saw it at USAICO, and I managed to find the strategy, but I must still get around to showing that it is optimal.
ReplyDeleteAn important clarification: each prisoner opens boxes sequentially, and gets to see the name in the box before he has to select the next box.
ReplyDeleteDon't prisoners all get killed eventually anyway? In which case you can't have a >30% success rate - perhaps short-term but definitely not long-term! :D
ReplyDeleteNo, in South Africa they get given 2 years off in a blanket presidential pardon, then another 20 months off for "good behaviour", and then appointed to the NEC.
ReplyDeleteI'm stumped on proving the strategy is optimal. I can do it for 4 prisoners, but not in an generalisable way.
I did a little searching and it appears there is a paper discussing the proof. However, I cannot seem to find an electronic copy. It does suggest that the proof is rather nasty though.
ReplyDeleteMathematical Entertainments - THE LOCKER PUZZLE / Curtain, Eugene / Warshauer, Max
[It's been a year and a half since this post, but just in case you're still interested...]
ReplyDeleteThe proof is actually not very nasty, at least to understand — they reduce it to another game whose winning probability is easy to calculate. I have a sketch of the proof if interested.