Free the prisoners

[bonanova]

It's time to paint the prison. The warden wants the cells cleared for the convenience of the painter. He devises a scheme by which his 100 prisoners either will be all freed or all executed. Either way, the painting will be made easier. His scheme offers a survival probability that seems terribly small.

In a room he places their names, on sheets of paper, in 100 wooden boxes, numbered 1-100 and lined up on a table, one name to a box. Prisoners are led into the room one by one and are told to look inside the boxes in search of their name. But  each prisoner can open at most 50 boxes. Successful or not, each prisoner must then leave the room, exactly as he found it, and he is permitted no further communication with the others. They may plot a strategy in advance. It needs to be a clever one, because every prisoner must find his own name in order for any of them to survive.

Your fame as a logician has reached the prison and you have been called in to help. They want you to provide them with a strategy having a survival probability that exceeds 30%! They have connections on the outside, they remind you, and they know where you live.

[plasmid]

Give every prisoner a number from 1 to 100, and make sure every prisoner knows the numbers of all of the prisoners. Each prisoner starts off opening the box of his number – if Alex is prisoner number 9 he opens box #9. If he finds his own name then he's done; if he finds another prisoner's name then he opens that prisoner's box – e.g. if Alex finds Eddie's name in box 9 and Eddie's number is 74, then Alex opens 74 next. Then he looks at the name in box 74 and opens that prisoner's box etc. until he reaches his own name. This creates a “loop” where Alex opens each box in a loop that's defined by the contents of each box until he reaches the end of the loop, and by virtue of the way these loops are constructed, the box at the end of the loop must hold his name.

Clearly, if all such “loops” among all the boxes are of size less than or equal to 50, the prisoners will all go free.

What's the probability that box #1 is part of a loop of exactly size N for any given N? The probability that box #1 is part of a loop of size 1 is simply the probability that box #1 contains prisoner #1's name, so 1/100. The probability that box #1 is part of a loop of size 2 is equal to (the probability that the name in box #1 is NOT prisoner #1) and (the box that box #1 points to contains prisoner #1's name), which is (99/100) x (1/99) = 1/100. In general, for the first few steps, the odds that the loop will be pointing to a box other than box #1 will be 99/100 x 98/99 x 97/98 x …. Once you get to the Nth step in the series, the odds of that box pointing to box #1 will be 1/(100-N), so you end up with a series of the form 99/100 x 98/99 x 97/98 x … x (n+1)/(n+2) x (n)/(n+1) x (1)/(n). All the terms in the numerators and denominators will cancel out except the 100 in the denominator of the first term and the 1 in the numerator of the last term. So the probability that a box is part of a loop of any given size is simply 1/(number of boxes) regardless of what size loop you're looking for.

What is the probability that ANY boxes are part of a loop larger than 50? At this point I have to turn to simulation. The following program considers box #1 and generates a random number ($loopsize) from 1 to 100 with equal probability and considers box #1 to be part of a loop of $loopsize boxes, and of the remaining (100-$loopsize) boxes it makes another loop by considering the next un-looped box to be part of a loop of 1 to (100-$loopsize) boxes, etc until there are fewer than 50 un-looped boxes remaining, and counts it as a hit if a loop contains more than 50 boxes. This program estimates the odds of having a loop of size >50 at just under 69%.

#!/usr/bin/perl
use strict;
use warnings;
my $over50 = 0;
for my $iterations (1..1000000) {
  my $boxesleft = 100;
  while ($boxesleft > 50) {
    my $loopsize = int(rand($boxesleft)) + 1;
    $boxesleft -= $loopsize;
    $over50 += ($loopsize > 50);
  }
}
print "There were $over50 trials with a loop >50\n";

[bubbled]

I think bubbled is right, 
"Sorting like" strategy, without "real sorting"  will not work.

I have proposed this "Sorting like" strategy, exactly like plasmid.

How about this :

Hidden Content

but then I realize it was not working. I've tested it using dev-C++.
the chance to find your name is only 50%, the same chance with random way opening boxes.

in my program : box numbered from 0 to 9, and your number is random from 0 to 9. You can only open 5 boxes to find your name.

 

Yes, it does work:

jasen , you were the first in this thread to suggest the right answer. But, because it involved moving the boxes (forbidden) and then you lost faith, bonanova correctly didn't mark it as solved. I recall many years ago, encountering this problem and having the "ah ha" moment where I thought of the solution and was "certain" it must be correct. However, I probably spent another 6 hours just thinking about why (I couldn't code then).

The point I was making earlier about never doing better than 50% still stands. This strategy creates correlated results more powerfully than any other guessing puzzle I've seen. As soon as 1 or 2 prisoners are successful, the chances the next prisoner succeeds starts to trend towards 100%. In fact, if the first prisoner were to not find his name until the 50th box, the next 99 prisoners would be guaranteed to win!

For the purposes of discussion, lets assume that every prisoner will keep looking until he finds his name (using the strategy plasmid suggests). Yes, if a single prisoner fails to find their name in 50 boxes, they all lose. But for science, they will all go into the yard and look into the boxes.

If a prisoner fails to find his name until 80 boxes, the rest of the prisoners have their fate already set in stone. Exactly 79 other prisoners will take 80 boxes to find their name (lose together), and 20 will all find their name in <= 20 boxes.

As I said, their is no way to improve the odds of a single prisoner finding his name, but the strategy will create a result space where a single success breeds massive correlated success and a single failure breeds massive correlated failure. Which is cool.

[jasen]

what you mean  "they can open at most 50 boxes" ?
total boxes they can open   or   each prisoner can open 50 boxes

If each prisoner can open 50 boxes, I think, surviving probability is more than 50%

[bonanova]

Each prisoner can open up to 50 boxes.

[bubbled]

what you mean  "they can open at most 50 boxes" ?
total boxes they can open   or   each prisoner can open 50 boxes

If each prisoner can open 50 boxes, I think, surviving probability is more than 50%

The percentage bonanova is looking to get above 30% is the probability that the ENTIRE group of 100 prisoners will all find their names. Without a powerful group strategy, each prisoner will be exactly 1/2 to find their name, thus the chances the entire group will succeed would be 1 / (2^100). 

[jasen]

can they sort the boxes (by names) they open ?

if they can :
first person open 1st box then exchange the box (the 1st box with the n-th name position of the box)
        repeat this to the next box 50 times, but he have to skip the box if it have been exchanged

2nd person open 2nd box then exchange the box (the 1st box with the n-th name position of the box)
        repeat this to the next box 50 times, but he have to skip the box if it have been exchanged

all prisoner do the same

Edited November 20, 2015 by jasen

[jasen]

I think this strategy is better

everybody have to memorize each person position

say :
n = his position
x = (name in the opened box) position

every person open n-th box 
then exchange the box (with the x-th box)
repeat this to the next box 50 times, but he have to skip the box if it have been exchanged.
if it reach the last box, go to first box

[Rainman]

I'd hate to disappoint them, but...

...it can't be done. Though they might send their friends to kill me anyway, I would proceed to prove my statement. Suppose there exists a strategy such that P(every prisoner finds his own name) > 30%. Let's number the prisoners p₁ through p₁₀₀ in any order (it doesn't matter by argument of symmetry), and the boxes b₁ through b₁₀₀ in any order (it also doesn't matter by argument of symmetry). For 1 ≤ i ≤ 100, let E_i be the event that p_i finds his own name. Thus the event that every prisoner finds his own name is the intersection of the events E₁ through E₁₀₀, which is a subset of the intersection of the events E₁ and E₂. So certainly P(E₁ and E₂) ≥ P(E₁ through E₁₀₀) > 30%. But I can easily prove that P(E₁ and E₂) ≤ 25%, which is a contradiction.

Consider a few facts:

• The prisoners can't provide each other with any information.
• The boxes are indistinguishable from each other by argument of symmetry, i.e. P(you find your own name) = n/100, where n is the number of boxes you open.
• Choosing to open fewer boxes than the 50 which you are allowed to open can not increase the chance of success.

Thus we can assume that p₁ and p₂ each opens exactly 50 boxes.

Let c be the number of boxes which are opened by both p₁ and p₂. (For example, if p₁ opens b₁ through b₅₀ and p₂ opens b₄₁ through b₉₀, then 10 boxes (b₄₁ through b₅₀) are opened by both p₁ and p₂, so c = 10.) We will separate the event E₁ into two disctinct subevents:

• E_1A = "p₁ found his name in a box which p₂ also opened".
• E_1B = "p₁ found his name in a box which p₂ didn't open".

If p₁ finds his own name, the probability is c/50 that p₂ also opened the box that contains p₁'s name. Then p₂ finds his own name with probability 49/100.

If p₁ finds his own name, the probability is 1-c/50 that p₂ didn't open the box that contains p₁'s name. Then p₂ finds his own name with probability 50/100 = 1/2.

So P(E₁ and E₂) = P(E₁) * P(E₂|E₁) = 1/2 * P(E₂|E₁) = 1/2 * (P(E₂|E_1A) + P(E₂|E_1B)) = 1/2 * (c/50 * 49/100 + (1-c/50) * 1/2) ≤ 1/2 * (c/50 * 1/2 + (1-c/50) * 1/2) = 1/2 * ((c/50+1-c/50) * 1/2) = 1/2 * 1/2 = 25%. Q.E.D.

I'm assuming, of course, that this wasn't a trick question. If they all have the same name, or they have access to a renaming facility, it becomes a different matter entirely

[Rainman]

I'd hate to disappoint them, but...

 

Hidden Content

Mistakes were made!

"I can easily prove that P(E₁ and E₂) ≤ 25%" should be "I can prove that P(E₁ and E₂) ≤ 25/99 < 30%"

"Then p₂ finds his own name with probability 49/100." should be "Then p₂ finds his own name with probability 49/99."

"Then p₂ finds his own name with probability 50/100 = 1/2." should be "Then p₂ finds his own name with probability 50/99."

The final calculation should be P(E₁ and E₂) = P(E₁) * P(E₂|E₁) = 1/2 * P(E₂|E₁) = 1/2 * (P(E₂|E_1A) + P(E₂|E_1B)) = 1/2 * (c/50 * 49/99 + (1-c/50) * 50/99) ≤ 1/2 * (c/50 * 50/99 + (1-c/50) * 50/99) = 1/2 * ((c/50+1-c/50) * 50/99) = 1/2 * 50/99 = 25/99 < 27/99 < 27/90 = 30%. Q.E.D.

[bubbled]

I think this strategy is better

Hidden Content

Jasen, you are on the right track, but you can't move the boxes. Imagine that the boxes are wooden with a hinged lid. The boxes are nailed to the table in position. You can open the boxes and look in, but you can't touch the names inside and when you've finished looking in your 50 boxes, you have to close all the boxes. Also, for Rainman, the problem is definitely achievable. The best strategy is not on the order of 1 / 2*100

[bonanova]

Here are three nudges. Not exactly clues. More like clarification of various points covered in the OP

The conditions of the OP mean that each prisoner sees the room identically as all the others see it. That is, it does not matter which order they enter the room. As a consequence, each prisoner has a success probability that does not depend on when, relative to the others, he enters the room.

Without a strategy of some sort, no prisoner can find his name with better than a 50% success probability. But not all strategies will be helpful. "Open the boxes with even numbers," for example, is no better than randomly picking 50 boxes. It leaves the hope of success at 50% because names were randomly placed in the boxes.

Brain fart: Disregard this:

That narrows the solution space somewhat, and points to the fact that any strategy that avoids failure after only two prisoners search the boxes, as Rainman has pointed out, must be one that guides every prisoner independent of the others, and gives each of them an expectation of finding his name that is significantly better than 50%.

And here is a slight "Oops."  
Did I forget to mention that the boxes are externally numbered 1-100?
They are, and now the OP says so.

[jasen]

How about this :

everybody have to memorize each person position

n = one's position in the sorted names.
x = friend's position in the sorted names.
Open the n-th box,
if he find his friend name, open the x-th box. repeat this for the next 48 box. 

[jasen]

bonanova, this your puzzle drives me mad

Only communication can make them survive !
So I think they must create unseen communication between them,
I've find a trick for them to communicate.
They must communicate with time !!

let say a,b,c,d ..... are the prisoners names in sequence, no need to sort.

every prisoner must know who will enter the room after him, 
so 'a' know 'b' will enter the room after 'a'.

'a' open 50 first boxes (1 to 50), if he find 'b' name there, so he must leave the room before 10 minutes.
'b' notice that 'a' leave the room before 10 minutes, so he know that his name is at 50 first boxes (1 to 50).
but if 'a', leave the room after 10 minutes, means that his name is not there so he must open boxes 51 to 100.

with same way, 'b' give information to 'c'.

and the probability they all save are 50% !!

[bubbled]

Here are three nudges. Not exactly clues. More like clarification of various points covered in the OP

Hidden Content

Hidden Content

Hidden Content

And here is a slight "Oops."  
Did I forget to mention that the boxes are externally numbered 1-100?
They are, and now the OP says so.

bonanova I strongly disagree:

 

The statement, "...and gives each of them an expectation of finding his name that is significantly greater than 50%." is (and must be) incorrect.

Whenever you have a guessing game that entails a group strategy, there is no way to improve the chances of an individual succeeding in the guessing game, whether it be red and blue hats, or boxes with names in them. If I'm one of the prisoners, I will be exactly 50% to find my name in the 50 boxes I look in, no matter what strategy I use.

However, the strategies in these games cleverly manage to cluster the wins and losses to increase the group's chances of being successful. In this case, that strategy has an enormous effect. But, if we were to run this game 1000's of times, including making all 100 prisoners complete the game even when one of the earlier prisoners failed, you'd find that exactly 50% of the prisoners would be successful. Clearly, if you are prisoner #80, and no one has failed ahead of you, you are very likely to succeed using the proper strategy. However, if you knew a prisoner had failed ahead of you, you might be very unlikely to succeed. This is the only way the miraculous 30+% success rate is possible.

Given the tremendous solving skills you've demonstrated over the years, I imagine you already know this and was just a little sloppy in the above statement. I just didn't want anyone to be lead astray.

There is no way to improve the inherent odds of a guessing game, and remembering that will usually lead you in the right direction for these group puzzles.

[bonanova]

How about this :

Hidden Content

@jasen, In an earlier post you said to switch boxes. (A) of course that is not permitted. (B) you can succeed even if the warden randomly re-positions them before each visit!

@bubbled, if the statement is incorrect, that you say is incorrect, the puzzle has no 30% solution. We agree on that. So it's not a guessing game. It's a strategy-driven game. And the strategy does group the successes and failures to advantage for the prisoners. We're both traveling the high road, trust me.

Construct, or recognize, a sample space for which a strategy can succeed 30% of the time. As you point out, it isn't and can't be the sample space of, "Hmm, maybe it's in THIS box"

@bubbled, let's not discuss my last point right now. This is because to clarify what I was getting at would mean to restate it in "much too revealing" terms. Perhaps I'll do that as a later clue if needed. For now I'd rather not retract it "with explanation." Let me simply retract spoiler #3. That is, your objection to it is valid, but also your objection to it does not preclude a solution. And if I say more, I say too much.  Thanks.

Edited November 25, 2015 by bonanova
Amending one of my claims.

[bonanova]

@plasmid, nicely done.

@bubbled, my spoiler 3 was a complete brain fart.

[jasen]

I think bubbled is right, 
"Sorting like" strategy, without "real sorting"  will not work.

I have proposed this "Sorting like" strategy, exactly like plasmid.

How about this :

Hidden Content

but then I realize it was not working. I've tested it using dev-C++.
the chance to find your name is only 50%, the same chance with random way opening boxes.

in my program : box numbered from 0 to 9, and your number is random from 0 to 9. You can only open 5 boxes to find your name.

 

Edited November 30, 2015 by jasen

[jasen]

Thank you bubbled, I understand now.