What is the Best Strategy for the 100 Prisoner Problem?

  • Context: Undergrad 
  • Thread starter Thread starter hutchphd
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around the 100 Prisoner Problem, a probability puzzle involving a group of prisoners who must devise a strategy to maximize their chances of survival by finding their assigned numbers in a set of drawers. The scope includes theoretical reasoning and strategic planning under constraints.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested

Main Points Raised

  • One participant expresses confusion about the problem and compares it to the Monty Hall problem, indicating a lack of familiarity with the 100 Prisoner Problem.
  • Another participant proposes a strategy where prisoners agree to look in specific drawers, suggesting a success rate of approximately 49.5% based on their approach.
  • A participant corrects the previous claim, clarifying that prisoners cannot move numbers and can only choose which drawers to open.
  • One participant describes a proposed solution involving tracking chains of numbers, likening it to a programming sorting algorithm.
  • Another participant requests a clear solution, implying that existing explanations may not adequately address the problem.
  • A later reply indicates a growing understanding of the problem and expresses amazement at the range of possible outcomes.
  • One participant introduces the Josephus problem as a related but distinct topic, noting it should not be discussed in this thread.

Areas of Agreement / Disagreement

Participants exhibit a mix of confusion, proposed strategies, and corrections, indicating that there is no consensus on the best approach or solution to the problem. Multiple competing views and interpretations remain unresolved.

Contextual Notes

Some participants express uncertainty about the rules and constraints of the problem, which may affect their proposed strategies. The discussion also highlights the complexity of the problem and the various interpretations of potential solutions.

Who May Find This Useful

Individuals interested in probability puzzles, strategic problem-solving, or mathematical reasoning may find this discussion relevant.

hutchphd
Science Advisor
Homework Helper
Messages
6,954
Reaction score
6,037
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?

 
  • Informative
Likes   Reactions: DaveE
Physics news on Phys.org
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   Reactions: Vanadium 50
Sorry. They are not allowed to move numbers. The only choice is which drawer to look into as they search for their number..
 
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   Reactions: MevsEinstein
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   Reactions: MevsEinstein, malawi_glenn and jedishrfu
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.
 
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   Reactions: MevsEinstein and hutchphd

Similar threads

Graduate A game of seemingly mutually independent events
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad Optimizing Prisoner Strategy for the Hat Riddle: A Simple Solution
  • · Replies 35 ·
2
Replies
35
Views
8K
Undergrad Freedom or aligators use switches for code.
  • · Replies 20 ·
Replies
20
Views
5K
Undergrad Regression line with zero slope and average as best prediction
  • · Replies 2 ·
Replies
2
Views
2K
Challenge Math Challenge - April 2019
  • · Replies 83 ·
3
Replies
83
Views
22K
Graduate What Strategy Saves the Most Prisoners?
  • · Replies 14 ·
Replies
14
Views
7K
  • Poll Poll
Undergrad Choose Room for Maximum Reward in Game of 4 Rooms
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad The answer is 15! What is the problem?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Save 10 Prisoners: Strategy to Ensure Maximum Survival
  • · Replies 15 ·
Replies
15
Views
5K
Undergrad Colored hats, liars, and truth-tellers
  • · Replies 1 ·
Replies
1
Views
4K