The 100 Prisoner's problem

[Cecelia]

But a prisoner wouldn't know what the others chose or what pattern they saw. In this case the prison warden has a much higher chance of detecting what pattern the prisoners are using than the other way around.

I meant by the 20th box opened, you would figure out there's a pattern.

Example:

When box 1 has 2, box 2 has 3 and so forth until 20, you'd see the pattern.

[Aractus]

In fact if the director put the numbers in the boxes following this pattern (the number in the box is the number of the box plus 1, and the number in box 100 is 1) then he would guarantee that the first prisoner would not find their number, even if the first prisoner was chosen at random.

Only if the prisoners use the officially labelled numbers though. If they decide, for example, that they will count right to left and ignore the actual numbers on the lockers then they've rearranged the order. For example, in your example the top two rows would become:

Code:

Box 1: 11   Box 11: 21
Box 2: 10   Box 12: 20
Box 3: 9    Box 13: 19
Box 4: 8    Box 14: 18
Box 5: 7    Box 15: 17
Box 6: 6    Box 16: 16
Box 7: 5    Box 17: 15
Box 8: 4    Box 18: 14
Box 9: 3    Box 19: 13
Box 10: 2   Box 20: 12

As you can see in row one this has created three pair-cycles, from Box 2 to Box 10 and one number containing box containing its own number. And this pattern exists for 12..20, 22...30, 32...40, and 42...50. Whilst also producing this cycle:

Box 1: 11
Box 11: 21
Box 21: 31
Box 31: 41
Box 41: 51
Box 51: 1

As there's only 49 boxes left, the next largest cycle must be 49 or lower. Therefore success for the prisoners in this case. To ensure the prisoners can't win the guards would have to come up with a permutation that not only produces a cycle of at least 51 lockers with the official numbers, but also at least 51 for each other way that the prisoners might be able to count the boxes without complicating it to the point that it would confuse some of the inmates. Or simply make a new random assignment for each prisoner, in which case the chance of success returns to an impossible ½100.

This strategy works so well that even for just 4 prisoners it increases the chance of success massively.

With 4 boxes there are 4! (that is, 24) possible number arrangements. The chance of random success is ¼4 (1 in 256). Obviously a strategy where you don't pick overlapping drawers will increase your chances, after all if everyone picks their own number as their first choice then they have a 1 in 24 chance of selecting correctly. If one number is messed up then that must mean two numbers are messed up - so your strategy could become "if odd then pick the next number, if even pick the previous number". This generates four successes in total out of 24, the same with the strategy reversed, the same with the rule "if odd pick each odd number, if even pick each even number".

Yet look what happens when we use the number contained in the box instead. The rule becomes "pick your number box, if your number isn't found then pick the number found in the box". This increases the chance of winning to 10 in 24. The previous mentioned strategies had a 16.7% chance of success (that's still a realistic chance) but the strategy where you use the number in the box to select the next number has a 41.7% chance.

[ApeNotKillApe]

So, if the director wanted all the inmates to die, then they would just have to create a cycle of 50 numbers, starting with the number in box #1, and ending with the number in box #50, ensuring that the number 1 does not appear in that cycle,

Or, y'know, he could just gas 'em or something.

[SteelCurtain]

In fact if the director put the numbers in the boxes following this pattern (the number in the box is the number of the box plus 1, and the number in box 100 is 1) then he would guarantee that the first prisoner would not find their number, even if the first prisoner was chosen at random.

By the 20th time though, most prisoners would recognize the pattern.   It'd be a good test though.

Exactly, prisoners aren't computer programs. (Hopefully) all of them would abandon the plan once they figured out the pattern. I cannot imagine anyone stupid enough that they wouldn't at least do a test pull of their number + 1 after 20 consecutive pulls of the drawer incrementing by one.

[Aractus]

In fact if the director put the numbers in the boxes following this pattern (the number in the box is the number of the box plus 1, and the number in box 100 is 1) then he would guarantee that the first prisoner would not find their number, even if the first prisoner was chosen at random.

By the 20th time though, most prisoners would recognize the pattern.   It'd be a good test though.

That's a really good point. If they recognised an artificial pattern like that they could simply skip to box 51 in the cycle since they know where it will be, and if it points to 52, they can jump ahead again to 75, if it's inside the cycle they go back to 63, if it's in the cycle they go to 87, and continue zeroing in until they find where the cycle ends which is where their number is. That only takes 6-7 guesses to get there, there's no chance of running out of guesses if the pattern is obvious like that.