Prisoners' strategy

[Genady]

There is a group of four prisoners, Al, Bill, Chuck, and Dick. After one year in prison, they have a chance to be released. It works as follows.

There is a room with a row of four boxes. Slips with the prisoners' names are randomly placed in the boxes, one per box.

Each prisoner enters the room, one at a time, checks one or two boxes of their choice, leaves the room without changing anything, and goes to his cell without any communication with other prisoners. Next prisoner enters the room. Etc.

If each prisoner finds his names in the boxes he checks, all four are released. If even one of them does not find his name, all four stay in prison for another year. A year later, they get this chance again. Of course, the slips are placed randomly again then.

How long are they expected to stay in prison? The calculation is straightforward. Each prisoner has 1/2 chance to find his name by checking two out of the four boxes. A chance that all four will find their names is 1/2 x 1/2 x 1/2 x 1/2 = 1/16. Thus, they are statistically expected to stay in prison for 16 years.

It turned out that there is a strategy which shortens this time. Significantly. Down to 2-3 years!

What is the strategy?

No tricks. Pure strategy. 

They can strategize only before entering the room.

[Ghideon]

39 minutes ago, Genady said:

There is a group of four prisoners, Al, Bill, Chuck, and Dick. After one year in prison, they have a chance to be released. It works as follows.

There is a room with a row of four boxes. Slips with the prisoners' names are randomly placed in the boxes, one per box.

Each prisoner enters the room, one at a time, checks one or two boxes of their choice, leaves the room without changing anything, and goes to his cell without any communication with other prisoners. Next prisoner enters the room. Etc.

If each prisoner finds his names in the boxes he checks, all four are released. If even one of them does not find his name, all four stay in prison for another year. A year later, they get this chance again. Of course, the slips are placed randomly again then.

How long are they expected to stay in prison? The calculation is straightforward. Each prisoner has 1/2 chance to find his name by checking two out of the four boxes. A chance that all four will find their names is 1/2 x 1/2 x 1/2 x 1/2 = 1/16. Thus, they are statistically expected to stay in prison for 16 years.

It turned out that there is a strategy which shortens this time. Significantly. Down to 2-3 years!

What is the strategy?

No tricks. Pure strategy. 

They can strategize only before entering the room.

.

Spoiler

Idea: If they choose at random there are combinations where the same two boxes are opened by all four prisoners. They should decide something like numbering system from left to right so that Al checks box 1,2, Chuck 3,4, Bill 1,3 Dick 2,4 to reduce the number of times they check combinations that can't possibly be correct.

 

[Genady]

1 hour ago, Ghideon said:

.

  Hide contents

Idea: If they choose at random there are combinations where the same two boxes are opened by all four prisoners. They should decide something like numbering system from left to right so that Al checks box 1,2, Chuck 3,4, Bill 1,3 Dick 2,4 to reduce the number of times they check combinations that can't possibly be correct.

 

Spoiler

It seems to help but it doesn't seem to me helping that much. Here is why.

There are 6 ways to pick two boxes out of 4. Thus, there are 6^4=1296 ways for them to pick pairs of boxes independently. 

OTOH, there are 6x4x6 ways for 3 prisoners to pick the same pair of boxes while the fourth prisoner picks the same or other pair. Eliminating these, we eliminate the total of 144 useless choices, out of 1296. Good, but doesn't seem to be that effective.

Let me know if you think I'm mistaken.

 

[TheVat]

 

4 hours ago, Genady said:

chance that all four will find their names is 1/2 x 1/2 x 1/2 x 1/2 = 1/16. Thus, they are statistically expected to stay in prison for 16 years.

Spoiler

Better each prisoner pick a different box to open first, since otherwise some common choices are wasted ones.

Prisoner one opens box one, with p=.25 he finds his name.  If he finds it, he stops.  If not, he opens box 2.  This time, because of his knowledge, the odds are based on three boxes, p=.333.  (the intuition failure is thinking his odds are still .25)  So p total=.5833, and not .5.

Prisoners 2-4 choose boxes 2-4.  Because of OUR knowledge of what prisoner 1 found, their odds are better.  This problem requires a Bayesian view of probability, in which expectations are constantly updated due to knowledge.

The improved p, plus avoiding wasted choices, should help to greatly reduce years in prison.

 

[Genady]

15 minutes ago, TheVat said:

 

  Hide contents

Prisoners 2-4 choose boxes 2-4.

 

Spoiler

I see a problem here. If prisoner 1 finds his name in box 2, then the box 1 contains a name of one of the prisoners 2-4, but they don't even open the box 1.

 

[md65536]

4 hours ago, Genady said:

How long are they expected to stay in prison?

Spoiler

2.4 years?

 

[Genady]

18 minutes ago, md65536 said:

  Hide contents

2.4 years?

 

Perfect. +1

[TheVat]

Spoiler

If I'm making any sense of this, there has to be a box searching strategy that somehow correlates the prisoners individual searches.

Prisoners are named "1" through "4".  Prisoner 1 goes to room, opens box one.  If that is not his number, then he opens the box of whichever number he finds.  Say he finds "#3" then he opens box three.  Later, #2 goes to room, opens box two.  Say he finds "#1" then he opens box one.  And so on.  In this way, placement is random, but selection is not.  The math for a permutation cycle is not fresh in my mind, but I will come back to this.

 

[Genady]

5 minutes ago, TheVat said:

  Hide contents

If I'm making any sense of this, there has to be a box searching strategy that somehow correlates the prisoners individual searches.

Prisoners are named "1" through "4".  Prisoner 1 goes to room, opens box one.  If that is not his number, then he opens the box of whichever number he finds.  Say he finds "#3" then he opens box three.  Later, #2 goes to room, opens box two.  Say he finds "#1" then he opens box one.  And so on.  In this way, placement is random, but selection is not.  The math for a permutation cycle is not fresh in my mind, but I will come back to this.

 

Yes, this is the strategy. +1

[Genady]

How will the answer change if the slips are randomly reshuffled each time before the next prisoner enters the room?