What is the Best Strategy for the 100 Prisoner Problem?

  • I
  • Thread starter hutchphd
  • Start date
In summary, the conversation discusses a well-known problem in which 100 death row prisoners must find their numbered drawers in a room in order to be pardoned. The prisoners devise a strategy where each prisoner looks in a specific set of drawers, resulting in a 49.5% chance of success. The solution involves treating the contents of each drawer as a pointer to the next one. The conversation also mentions a similar problem known as the Josephus problem.
  • #1
hutchphd
Science Advisor
Homework Helper
6,761
5,812
TL;DR Summary
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?

 
  • Informative
Likes DaveE
Mathematics news on Phys.org
  • #2
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%.
 
  • Like
Likes Vanadium 50
  • #3
Sorry. They are not allowed to move numbers. The only choice is which drawer to look into as they search for their number..
 
  • #4
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.
 
Last edited:
  • Like
Likes MevsEinstein
  • #5
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.
 
  • Like
Likes MevsEinstein, malawi_glenn and jedishrfu
  • #6
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.
 
  • #7
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.
 
  • Like
  • Informative
Likes MevsEinstein and hutchphd

FAQ: What is the Best Strategy for the 100 Prisoner Problem?

1. What is "The 100 prisoner problem"?

The 100 prisoner problem is a mathematical puzzle that involves 100 prisoners, each with a unique number, who are placed in solitary confinement and given a chance to win their freedom. The prisoners are allowed to communicate and collaborate, but only under certain conditions.

2. What are the conditions of the puzzle?

The conditions of the puzzle are that each prisoner is given a chance to visit a room with 100 boxes, each containing a different number. The prisoners must open a certain number of boxes, determined by their unique number, in a specific order. If all prisoners successfully open their designated boxes, they will all be set free. However, if even one prisoner fails, they will all be executed.

3. Is there a solution to this puzzle?

Yes, there is a solution to this puzzle. However, it requires a strategy and cooperation among the prisoners. The solution involves a specific order in which the prisoners must open the boxes and a way to communicate this order to each other.

4. How difficult is this puzzle to solve?

The 100 prisoner problem is considered a difficult puzzle to solve, as it requires critical thinking and collaboration among the prisoners. It has been compared to other famous mathematical puzzles, such as the Monty Hall problem and the Prisoner's Dilemma.

5. What is the significance of this puzzle?

The 100 prisoner problem is a thought-provoking puzzle that has real-world applications in fields such as computer science, game theory, and cryptography. It also highlights the importance of communication and cooperation in problem-solving.

Similar threads

Optimizing Prisoner Strategy for the Hat Riddle: A Simple Solution
2
Replies
35
Views
5K
Freedom or aligators use switches for code.
Replies
20
Views
5K
The Prisoner Who Knew: A Puzzling Tale
Replies
4
Views
8K
Challenge Math Challenge - April 2019
3
Replies
83
Views
19K
What Strategy Saves the Most Prisoners?
Replies
14
Views
7K
A A game of seemingly mutually independent events
Replies
7
Views
2K
I The answer is 15! What is the problem?
Replies
1
Views
2K
Save 10 Prisoners: Strategy to Ensure Maximum Survival
Replies
15
Views
5K
Colored hats, liars, and truth-tellers
Replies
2
Views
4K
5 Star Logic Problem (100 prisoners and a light bulb)
3
Replies
84
Views
97K

Hot Threads

Recent Insights

Back
Top