WoodCentral Forums

Est. 1998 — 27 years of woodworking knowledge

Prisoner strategy

Posts

Prisoner strategy

#1

Peter Martin

100 prisoners numbered 1-100.
screenshot-from-2024-02-02-20-22-56_324.png
Slips with their numbers are randomly placed in 100 boxes in a room. Each prisoner may enter the room one at a time and check 50 boxes. They must leave the room exactly as they found it and can't communicate with the other prisoners.
screenshot-from-2024-02-02-20-23-31_323.png
If all 100 prisoners find their number during their turn in the room, they will all be freed. But if even one fails, they will all be executed.

They all can communicate BEFORE any of them enter the room. What is their best strategy?

Re: Prisoner strategy

#2

Start with a similar but simpler problem.  Just 2 prisoners and a room with 2 boxes.  Each prisoner enters the room and opens 1 box.  If they both find their number they go free.  If either does not find his number they both die.  They agree before going in that each will open the box corresponding to their number i.e prisoner 1 opens box 1, prisoner 2 opens box 2.
There is a 50-50 chance that 1 is in box 1.  So if prisoner 1 opens box 1 he finds his number.  And prisoner 2, having agreed before he goes in that he will open box 2, so he will find his number.  The odds of success are 50-50.  
I think similar reasoning can be applied to larger even numbers of prisoners.   (The puzzle does not work with odd numbers of prisoners. )  I started to try this with 4 prisoners.  I think the strategy is that assuming the 1st (and subsequent) prisoners are successful in finding their number, then the best strategy for the 2nd prisoner (and subsequent) prisoners is to avoid opening the same boxes that the first prisoner opened.  Of course, if prisoner 1 failed then it does not matter what the 2nd prisoner does.

Re: Prisoner strategy

#3

No prisoners enter the room.  No one is executed.  They serve out their sentences and go home!  Only downside is for the prisoners with life sentences. :lol:

Re: Prisoner strategy

Edited #4

As I'm understanding this, the odds that all 100 of these prisoners will find their number even with 50 tries is......1 in 2x2x2x{100 times).......which is a very large number (my little calculator isn't able to compute that number)......so, this outcome is extremely unlikely (not unlike your chances with TS).......

The prisoners best move might be to riot then and there......overpower their guards.......and run off into the night........

Re: Prisoner strategy

Edited #5

admin

What would happen if the number of the next box they opened was the number contained in the previous box? Would that increase the odds of finding the box with their number?

Re: Prisoner strategy

#6

Consider the simpler problem with just 4 prisoners.  There are 4 boxes, and the 4 boxes contain the numbers 1,2,3,4 in a random order.  Each prisoner can open 2 boxes. 
For prisoner 1, consider two schemes (call them scheme A and B).  He can open boxes 1 and 2 (scheme A).  Or he can open box 1 and then open the box that corresponds to the number he finds in box 1 (scheme B). 
There are 4!=24 possible combinations of the numbers 1,2,3,4 that can be placed in boxes 1,2,3,4.  There are 6 combinations where the number 1 is in box 1, as follows: (1,2,3,4 - 1,2,4,3 - 1,3,2,4 - 1,3,4,2 - 1,4,2,3 - 1,4,3,2).  Similarly, there are 6 combinations where 2 is in box 1, 6 combinations where 3 is in box 1, and 6 where 4 is in box 1. Here are the combinations if 2 is in box 1 (2,1,3,4 - 2,1,4,3 - 2,3,1,4 - 2,3,4,1 - 2,4,1,3 - 2,4,3,1).  Similarly when box 1 contains the number 3 and similarly when box 1 contains the number 4. 
For scheme A, Prisoner 1 will be successful (find number 1) 6 times if the number 1 is in box 1, and 2 times when box 1 contains the number 2 but box 2 contains the number 1. And 2 times when box 1 contains the number 3 but box 2 contains the number 1 and 2 times when box 1 contains the number 4 but box 2 contains the number 1.   So for scheme A, prisoner 1 will be successful 6+2+2+2 = 12 times.  
It is easy to see that for scheme B, prisoner 1 will also be successful 6+2+2+2 =12 times.  So to answer the question posed by Admin, there is no difference in this case for prisoner 1.

Re: Prisoner strategy

Solution #7

Peter Martin

Here is the video I watched to create the problem:
https://youtu.be/iSNsgj1OCLA?si=YNGN6aH4ZTubHu7H

👍 This page answered my questions

Your vote helps other woodworkers quickly find the answers and techniques that actually work in the shop.