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.

 

[.Scott]

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.

It's difficult to give a hint without just giving it away.
But here's another detail:

Spoiler

Way more than 99% of all arrangements of numbers will provide some advantage - but not necessarily enough to form a "winning hand" when each player only gets only 50 guesses.

Warning: This next spoiler comes close to giving it away. It pretty much walks you most of the way to the solution!

Spoiler

When you calculate the probability that every prisoner will find their number, the presumption is that there is no connection between prisoner J's luck and prisoner X's luck. In essence, you presume that each one is casting their own unique die - and the likelihood that both will succeed (pJX) is the product of their independent throws (pJ pX). You need to get around that.

 

[pbuk]

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

Possibly, perhaps also because the solution is similar to the one in this recent thread which seemed to me to deteriorate into a pissing contest.

 

[Matterwave]

Warning: This next spoiler comes close to giving it away. It pretty much walks you most of the way to the solution!

This spoiler is indeed the main insight for the solution. However, I'm not sure truly if it actually makes the answer that much easier to arrive at haha.

The fun part of this puzzle is even if you know the prisoner's strategy, it's still non trivial to reason out why it works.

 

[Matterwave]

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.

Yeah I'm pretty sure I wouldn't have been able to solve it either. At least not without weeks/months..years.. of thought lol.

 

[.Scott]

I think it's fair to let potential solvers know what the target solution looks like. The winning strategy yields a "win" about 31% of the time. Any other strategy will win far less than 1% of the time.
Here's the more telling spoiler version:

Spoiler

When the numbers are randomly dropped into the boxes, a "winning hand" will result about 31% of the time.
When the winning strategy is used, it will successfully exploit a "winning hand" 100% of the time.

 

[Matterwave]

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.

I wonder what strategy you found? Could you post it with spoilers? :)

 

[pbuk]

I do not see how any particular arrangement of the numbers gives a better chance than any other without presuming the prisoners' strategy.

The arrangement of the numbers only makes a difference if the prisoners all follow the correct strategy. Other than picking boxes at random, how many strategies can you think of?

Spoiler

Other than picking a box at random, which box might prisoner 1 choose first?

 

[.Scott]

I remember seeing this puzzle for the first time. I realized that I needed to somehow link each individual prisoner's odds with those of other prisoners. But given the rules (leaving the room exactly as you found it and not being able to tell anyone what you found, etc.), I could not see how that could be done.

On the other hand, when I read the answer, I knew immediately why it worked.

Here's why, to a software engineer, the answer might "click" immediately. And this is probably the most revealing spoiler yet:

Spoiler

If, as a software engineer, you ever looked into what it would take to do an in-place reordering of a list using only one extra list entry in memory to work with and do it most efficiently (only one move per item), then you should catch the reasoning behind the solution almost immediately.