Undergrad What is the Best Strategy for the 100 Prisoner Problem?

[hutchphd]

TL;DR

There is a new Veritasium post: https://www.youtube.com/watch?v=iSNsgj1OCLA Anybody got a great solution?Amazing problem

I am sure this is a well known problem but not to me. I am having trouble getting happy with it: where is Monte Hall when I need him.
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 his number in one of the drawers, all prisoners are pardoned. If just one prisoner does not find his 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?

 

[.Scott]

They all agree that from the fourth prisoner on, every prisoner will look into drawer #1.
The first prisoner looks into drawers 50 to 1 leaving all of those numbers in the first drawer. The second prisoner looks into draws 99 to 51 and then drawer 1, leaving them all in drawer 1. The third prisoner looks in drawer 100 and 1 and leaves them in 1. The chance of success is roughly 49.5%.

 

[hutchphd]

Sorry. They are not allowed to move numbers. The only choice is which drawer to look into as they search for their number..

 

[jedishrfu]

The solution is quite brilliant. Basically tracking the string of cell numbers from box to box by noticing the fact that randomly distributing the cell numbers into the boxes creates chains of numbers of varying length. That is treating the contents of each box as a pointer to the next box. Programming-wise it reminds me a bit of a sorting algorithm.

 

[mfb]

Anybody got a great solution?

The video has the solution. It's the solution because nothing else comes close, unless it's just a rephrased version of the same solution.

 

[hutchphd]

On second look the solution makes much more sense to me. I was totally unaware of this interesting "problem" and I guess I am still amazed by range of possible outcomes. One reason for the post was just to highlight the problem for folks equally unaware.

 

[jedishrfu]

A related buy of course differernt problem, is the Josephus problem of where to stand in a circle of people so that you are the last one standing.



Not to be discussed in this thread.