Logic Puzzle: The Locker Puzzle

[Matterwave]

TL;DR

Also called the 100 prisoners problem, a fun but difficult puzzle to think through.

Disclaimer: This is not the first time this topic was discussed here on PF. From my search, it was discussed lightly in 2022. Further, a solution to this puzzle was covered by the Youtuber Veritasium and various other youtubers.

I still feel like the puzzle is a very fun one! So I thought I'd present it here for those interested in thinking through it.

When I first heard it, I spent maybe an hour thinking about it and got nowhere. Then I looked up the solution and it took another couple of hours for me to just understand the solution. Once I fully grokked the solution, it seems easy like all good puzzles do after the fact.

The puzzle is solved and the solution is proven to be optimal in this paper: https://www.cl.cam.ac.uk/~gw104/Locker_Puzzle.pdf

I understand the solution and why it is good. I have not read the proof that the solution is the optimal one.

Because I struggled through understanding the solution, I think there are maybe 3-ish big leaps of logic (at least for me) in the solution of this puzzle.

Anyways, without further ado, here is the puzzle as given by Philippe Flajolet and Robert Sedgewick, taken from Wikipedia (https://en.wikipedia.org/wiki/100_prisoners_problem):

The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a last chance. A room contains a cupboard with 100 drawers. The director randomly puts one prisoner's number in each closed drawer. The prisoners enter the room, one after another. Each prisoner may open and look into 50 drawers in any order. The drawers are closed again afterwards. If, during this search, every prisoner finds their number in one of the drawers, all prisoners are pardoned. If even one prisoner does not find their number, all prisoners die. Before the first prisoner enters the room, the prisoners may discuss strategy — but may not communicate once the first prisoner enters to look in the drawers. What is the prisoners' best strategy?

Anyways, if you already know and fully grok the answer, maybe don't spoil it (put answers in spoilers). Let some folks have fun thinking through the puzzle.

 

[.Scott]

This isn't the answer - but it's a very significant clue. It basically tells you why the solution works without saying what that solution is.

Spoiler

By randomly placing the pardons in the drawers, the director necessarily divided them into groups, with each group having an interesting feature. In doing that, he may have dealt the prisoners an intrinsically "loosing hand" or "winning hand". The prisoners best shot is to presume that they have have been handed a win, and to take advantage of this grouping.

 

[Matterwave]

This isn't the answer - but it's a very significant clue. It basically tells you why the solution works without saying what that solution is.

Yep! This is a very significant clue indeed. It is the main reason behind the method. I suspect that even if one reads this clue though, it will still be difficult to solve this problem!

But if one wants to solve the problem entirely on their own, one should not read this spoiler.

 

[Matterwave]

Nobody wants to try?

It is possible this puzzle is simply too difficult as a puzzle. The logical leaps are quite great..

 

[haruspex]

The best strategy I can find gives them a mere one in $^{100}C_{50}$ chance, but at least that’s better than the $2^{-100}$ chance without a strategy.
It does not use @.Scott's hint, and I confess I do not see how any particular arrangement of the numbers gives a better chance than any other without presuming the prisoners' strategy.

 

[Hornbein]

I've seen this before. It's very ingenious. I didn't try to solve it and am pretty sure I wouldn't have been able to.