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.

 

[Matterwave]

Well it's been a month, so I think I will put up the solution in a spoiler haha.

Spoiler: Logic Puzzle Solution

The solution is actually an extremely simple strategy. It is really just understanding why this strategy works that is the interesting part.

The prisoners first agree on a way to label the drawers 1-100. So for example, they can choose, on a grid, the top left drawer as 1 and number them going left to right and then top to bottom. It doesn't matter the scheme they choose here, the only thing that matters is they all agree to the same labels.

After the drawers have been labeled, the prisoners follow the extremely simple strategy: each prisoner goes into the room and first opens the drawer they labeled with their own number (prisoner 57 opens drawer 57, and so on). They look at the number inside the drawer. If it is their number, they're done. If not, they go to the drawer of that number that was in the first drawer (prisoner 57 sees the number 65, so they open the drawer that they collectively labeled 65).

And that's it. This simple strategy has a ~31% chance of success with 100 drawers and limits to a ~30.7% chance of success with infinite drawers. Far superior to random chance which has a (1/2)^100 chance of success.

The way for me to visualize this solution is to visualize directed graphs. The numbers are randomly labeled 1-100 inside the drawers. Label those nodes. The random number inside the node tells you where to draw the arrow to the next node. So in our example where the number 65 was under drawer 57, we draw an arrow from the drawer labeled 57 to drawer labeled 65. Whatever number is under 65, we draw an arrow from drawer 65 to the drawer with that number as the label. We keep drawing these arrows until there are no more to draw. A drawer which has its own number underneath has the trivial "arrow to itself" relation.

Now we think about what kind of graphs we had to have drawn. It is not too difficult to convince oneself (though, it did take a decent amount of convincing for me lol) that all graphs drawn this ways are cyclic graphs (counting identity arrows as cyclic from itself to itself). There can't be dangling loose ends because a drawer has to contain *some number* from 1-100 under it. A drawer always points to some drawer (possibly itself). The graphs also can't cross since a drawer has exactly one number under it. You can't get a node with 2 (or more) arrows coming out or 2 (or more) arrows going in. Exactly 1 in arrow and 1 out arrow per node.

If the longest cycle in the graph is 50 or fewer drawers, then the prisoners will win. If not, the prisoners will lose. If you count how many possible arrangements of the random numbers have cycles > 50 and divide it by the total number of possible arrangements, that is your failure rate. One can show that as the number of drawers and prisoners grow (while always allowing prisoners to open half the drawers), the success rate in the limit is 1-ln(2).

The big conceptual leap that was very hard for me to grasp in this puzzle was to somehow tie the prisoner's chances of success together. I mean, the puzzle already does that (if each is successful they are all successful and if a single one fails they all fail) but to make the conceptual leap that says there's a strategy where there are no per-prisoner independent probabilities at all is tough.