# The 100 prisoner riddle - counterintuitive puzzle **URL:** \ **Category:** The Game Room\ **Created:** [July 1, 2022, 5:49pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259 "2022-07-01T17:49:12Z")\ **Posts on this page:** 20\ **Page:** 4
**Author:** ![hajario](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hajario/32/171_2.png) [@hajario](https://boards.straightdope.com/u/hajario)\ **Post date:** [July 8, 2022, 1:50pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/61 "2022-07-08T13:50:48Z")
> [@Chronos](#): > > It’s not like someone came up with the puzzle on a lark, and then someone else came up with the solution. Rather, some mathematician was studying permutations, and the probability of having loops of various lengths, and then came up with the puzzle (to which he already knew the solution) based on that. That’s not how the video described it. Do you have a cite for that? ---
**Author:** ![Cheesesteak](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/cheesesteak/32/3694_2.png) [@Cheesesteak](https://boards.straightdope.com/u/Cheesesteak)\ **Post date:** [July 8, 2022, 1:56pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/62 "2022-07-08T13:56:34Z")
In terms of loops it HAS to be a loop when using this strategy. 1. Once you pick a starting point, your path is completely deterministic. Each box leads to one and only one box. 2. You can’t run out of numbers. There are no empty boxes. 3. You can’t re-enter the path at a different place than you started, that requires 2 boxes to have the same number inside. If we accept that the 100 boxes are grouped into a discrete number of separate loops, the only way to guarantee that your number is in the loop you select is to start with your numbered box. It’s really elegant. ---
**Author:** ![3AxisCtrl](https://avatars.discourse-cdn.com/v4/letter/3/ecd19e/32.png) [@3AxisCtrl](https://boards.straightdope.com/u/3AxisCtrl)\ **Post date:** [July 8, 2022, 2:24pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/63 "2022-07-08T14:24:10Z")
> [@Cheesesteak](#): > > If we accept that the 100 boxes are grouped into a discrete number of separate loops … Which is easy to accept, as it’s impossible for them to be grouped so that this isn’t true. > [@](#): > > … the only way to guarantee that your number is in the loop you select is to start with your numbered box. Another way to say the same thing: The only number that’s certain to be in the loop you choose is the one on the box you first open. ---
**Author:** ![Railer13](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/railer13/32/9742_2.png) [@Railer13](https://boards.straightdope.com/u/Railer13)\ **Post date:** [July 8, 2022, 2:41pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/64 "2022-07-08T14:41:16Z")
> [@Cheesesteak](#): > > If we accept that the 100 boxes are grouped into a discrete number of separate loops Knowing, of course, that the number of separate loops could be anywhere from 1 to 100, inclusive. ETA: I guess there couldn’t be 99 separate loops. ---
**Author:** ![Railer13](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/railer13/32/9742_2.png) [@Railer13](https://boards.straightdope.com/u/Railer13)\ **Post date:** [July 8, 2022, 2:42pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/65 "2022-07-08T14:42:20Z")
Nevermind ---
**Author:** ![3AxisCtrl](https://avatars.discourse-cdn.com/v4/letter/3/ecd19e/32.png) [@3AxisCtrl](https://boards.straightdope.com/u/3AxisCtrl)\ **Post date:** [July 8, 2022, 2:48pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/66 "2022-07-08T14:48:08Z")
> [@Railer13](#): > > I guess there couldn’t be 99 separate loops. I think there could be. One example: Boxes 1 through 98 contain their own number. Box 99 contains 100; box 100 contains 99. ---
**Author:** ![k9bfriender](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/k9bfriender/32/3283_2.png) [@k9bfriender](https://boards.straightdope.com/u/k9bfriender)\ **Post date:** [July 8, 2022, 2:51pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/67 "2022-07-08T14:51:41Z")
> [@Cheesesteak](#): > > If we accept that the 100 boxes are grouped into a discrete number of separate loops, the only way to guarantee that your number is in the loop you select is to start with your numbered box. Hmmm, so does that mean that if you, and the rest of the prisoners, decide to open the box that corresponds to your number +5, then you could be on a loop that _doesn’t_ include your number? I think it does. It’s still a valid strategy if you know the warden set up the boxes to contain a greater than 51 sized loop, as that guarantees failure, but it would be less successful than the vanilla setup. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [July 8, 2022, 3:00pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/68 "2022-07-08T15:00:43Z")
I am not sure it makes any difference what the warden did, since the prisoners, assuming they are allowed to pick a strategy in advance, can apply their own random permutation, essentially randomly renumbering the boxes. ---
**Author:** ![k9bfriender](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/k9bfriender/32/3283_2.png) [@k9bfriender](https://boards.straightdope.com/u/k9bfriender)\ **Post date:** [July 8, 2022, 3:12pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/69 "2022-07-08T15:12:59Z")
The point is that if we know that the warden has manipulated the numbers so that there is a loop of 60, we know that we all fail (and are executed.) The strategy that gave us hope is now doomed. So, we decide to change up our strategy and add 5 to the number of each box. I _think_ it makes a difference that everyone follows the same strategy. If everyone picks their own random permutation, then it’s not much different from everyone just picking 50 boxes at random. In the simplest case, I have a 7. I add 5 to it, and get 12. I go to box 12, and it has in it the number 12. I am on a loop that does _not_ contain my number, and will have to change strategies. ---
**Author:** ![Great\_Antibob](https://avatars.discourse-cdn.com/v4/letter/g/e47c2d/32.png) [@Great\_Antibob](https://boards.straightdope.com/u/Great_Antibob)\ **Post date:** [July 8, 2022, 3:15pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/70 "2022-07-08T15:15:29Z")
> [@k9bfriender](#): > > Hmmm, so does that mean that if you, and the rest of the prisoners, decide to open the box that corresponds to your number +5, then you could be on a loop that _doesn’t_ include your number? Absolutely. I gave an example of such above. If you have 4 boxes instead: ``` 1 - 3 - 2 - 4 ``` If prisoner 1 starts with any other box than their own, they are in a loop that doesn’t contain their own. The worst case would be if all boxes contained their own number: 1 - 2 - 3 - 4 In this case, if every prisoner picked their number +1 (or + anything other than 0), no loop will contain its own number. The malicious warden setup is to reduce failure for artificially long loops, with the understanding that the strategy of adding +5 (or +whatever) is suboptimal otherwise - but in a situation where the ‘best’ you can do is still terrible. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [July 8, 2022, 3:35pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/71 "2022-07-08T15:35:01Z")
I don’t mean everyone picks their own random permutation, rather that everyone agrees on a single random permutation. This is equivalent to randomly re-labelling all the boxes at the outset. This will probably not be “adding 5”, more like: the box originally labelled “1” is now 37, box 2 becomes 58, box 3 becomes 65, box 4 becomes 5, box 5 becomes 15, etc. ---
**Author:** ![k9bfriender](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/k9bfriender/32/3283_2.png) [@k9bfriender](https://boards.straightdope.com/u/k9bfriender)\ **Post date:** [July 8, 2022, 3:45pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/72 "2022-07-08T15:45:32Z")
> [@DPRK](#): > > I don’t mean everyone picks their own random permutation, rather that everyone agrees on a single random permutation. This is equivalent to randomly re-labelling all the boxes at the outset. I guess I misunderstood, sorry. > [@DPRK](#): > > This will probably not be “adding 5”, more like: the box originally labelled “1” is now 37, box 2 becomes 58, box 3 becomes 65, box 4 becomes 5, box 5 becomes 15, etc. I don’t see how this gets any different result from “add 5” and seems far more complicated. Now of course, in all these problems, the prisoners are all geniuses with perfect logic capabilities\*, so complicated isn’t a non-starter, but I don’t see any reason to make it more complicated than it needs to be. \*there was a “logic” puzzle I saw, I think on Stand up maths, a few years ago, where there was a key hidden under a coin on a chessboard. All the spaces had coins, randomly flipped. One prisoner enters, sees where the key is, and then can flip one coin. The next prisoner now needs to work out where the key is based on that flip. When they did the puzzle, both the first and second “prisoner” spent a fair amount of time with pen and paper doing math to work it out. ---
**Author:** ![EllisDee](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ellisdee/32/4531_2.png) [@EllisDee](https://boards.straightdope.com/u/EllisDee)\ **Post date:** [July 8, 2022, 3:45pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/73 "2022-07-08T15:45:35Z")
> [@k9bfriender](#): > > Hmmm, so does that mean that if you, and the rest of the prisoners, decide to open the box that corresponds to your number +5, then you could be on a loop that _doesn’t_ include your number? In that case you’re not looking for the box with your number on it. You’re looking for the box with (your number - 5) on it. And once again I have no way to conceptualize what the result of that would be. ---
**Author:** ![hajario](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hajario/32/171_2.png) [@hajario](https://boards.straightdope.com/u/hajario)\ **Post date:** [July 8, 2022, 5:16pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/74 "2022-07-08T17:16:54Z")
> [@Chronos](#): > > It’s not like someone came up with the puzzle on a lark, and then someone else came up with the solution. Rather, some mathematician was studying permutations, and the probability of having loops of various lengths, and then came up with the puzzle (to which he already knew the solution) based on that. Here is the History section of the Wiki article about the puzzle. Do you have reason to dispute it? ---
**Author:** ![hajario](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hajario/32/171_2.png) [@hajario](https://boards.straightdope.com/u/hajario)\ **Post date:** [July 8, 2022, 5:44pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/75 "2022-07-08T17:44:35Z")
Link: [100 prisoners problem - Wikipedia](https://en.wikipedia.org/wiki/100_prisoners_problem#History) ---
**Author:** ![Little\_Nemo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/little_nemo/32/3120_2.png) [@Little\_Nemo](https://boards.straightdope.com/u/Little_Nemo)\ **Post date:** [July 8, 2022, 6:36pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/76 "2022-07-08T18:36:14Z")
The advantage of opening your own number’s box and following the loop from there is that everyone is guaranteed to be on a path that leads to their goal, even if some of the paths might be too long. This is not true of the +5 strategy. So my question is whether the +5 strategy offers any real advantage or is it just an elaborate equivalent of random guessing? ---
**Author:** ![EllisDee](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ellisdee/32/4531_2.png) [@EllisDee](https://boards.straightdope.com/u/EllisDee)\ **Post date:** [July 8, 2022, 6:37pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/77 "2022-07-08T18:37:20Z")
The video claims that it is true of the +5 strategy. ---
**Author:** ![Dr.Winston\_OBoogie](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.winston_oboogie/32/2945_2.png) [@Dr.Winston\_OBoogie](https://boards.straightdope.com/u/Dr.Winston_OBoogie)\ **Post date:** [July 8, 2022, 6:42pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/78 "2022-07-08T18:42:05Z")
> [@Little\_Nemo](#): > > This is not true of the +5 strategy. Sure it is If you’re number 23, you’re not picking 28 then picking whatever is in 28, you’re picking 28 then whatever is in 28 + 5; then whatever is in that + 5 etc. Logically, you have to have a loop there. Somewhere. And, it doesn’t have to be the same loop or even the same count. I played around, trust me, it works. ---
**Author:** ![Little\_Nemo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/little_nemo/32/3120_2.png) [@Little\_Nemo](https://boards.straightdope.com/u/Little_Nemo)\ **Post date:** [July 8, 2022, 6:44pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/79 "2022-07-08T18:44:36Z")
> [@k9bfriender](#): > > The point is that if we know that the warden has manipulated the numbers so that there is a loop of 60, we know that we all fail (and are executed.) The strategy that gave us hope is now doomed. If the warden wants to be a real bastard, he would manipulate the numbers in two ways. First, he would arrange the papers so there is a loop of at least fifty-one boxes. This would would foil the standard strategy. Then he would place one of the remaining papers inside the box that has the same number. This guarantees that the +5 strategy or any other strategy that depends on displaced numbers will fail. ---
**Author:** ![Dr.Winston\_OBoogie](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.winston_oboogie/32/2945_2.png) [@Dr.Winston\_OBoogie](https://boards.straightdope.com/u/Dr.Winston_OBoogie)\ **Post date:** [July 8, 2022, 6:49pm UTC](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259/80 "2022-07-08T18:49:28Z")
> [@Little\_Nemo](#): > > Then he would place one of the remaining papers inside the box that has the same number. This guarantees that the +5 strategy or any other strategy that depends on displaced numbers will fail. Nope, you’re wrong. Let’s say you’re number 29 and he puts “29” in box “29”. you’re going to grab 34, which leads to something which leads to… which leads to 24, which leads to 29. Still works. [Previous page](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259.md?page=3) [Next page](https://boards.straightdope.com/t/the-100-prisoner-riddle-counterintuitive-puzzle/967259.md?page=5)