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,560
5,661
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

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
    • General Discussion
2
Replies
35
Views
4K
Freedom or aligators use switches for code.
    • General Discussion
Replies
20
Views
5K
Challenge Math Challenge - April 2019
    • Math Proof Training and Practice
3
Replies
83
Views
17K
A A game of seemingly mutually independent events
    • Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
The Prisoner Who Knew: A Puzzling Tale
    • General Discussion
Replies
4
Views
8K
I The answer is 15! What is the problem?
    • General Math
Replies
1
Views
1K
I What is the role of geometry and dimensional operations?
    • General Math
Replies
3
Views
274
I Find Lowest Rung to Drop Bottles & Prevent Breakage - Problem Solving
    • General Math
Replies
26
Views
3K
MHB Two problems: linear distance and directed graph
    • General Math
Replies
16
Views
5K
Colored hats, liars, and truth-tellers
    • General Discussion
Replies
2
Views
3K

Hot Threads

Recent Insights

Back
Top