Jump to content
BrainDen.com - Brain Teasers
  • 1

Free the prisoners


bonanova
 Share

Question

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.

Link to comment
Share on other sites

18 answers to this question

Recommended Posts

  • 1

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";
Link to comment
Share on other sites

  • 1

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.

 

findNamesInBoxes.gif

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.

Link to comment
Share on other sites

  • 0

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). 

Link to comment
Share on other sites

  • 0

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 by jasen
Link to comment
Share on other sites

  • 0

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

Link to comment
Share on other sites

  • 0

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 p1 through p100 in any order (it doesn't matter by argument of symmetry), and the boxes b1 through b100 in any order (it also doesn't matter by argument of symmetry). For 1 ≤ i ≤ 100, let Ei be the event that pi finds his own name. Thus the event that every prisoner finds his own name is the intersection of the events E1 through E100, which is a subset of the intersection of the events E1 and E2. So certainly P(E1 and E2) ≥ P(E1 through E100) > 30%. But I can easily prove that P(E1 and E2) ≤ 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 p1 and p2 each opens exactly 50 boxes.

Let c be the number of boxes which are opened by both p1 and p2. (For example, if p1 opens b1 through b50 and p2 opens b41 through b90, then 10 boxes (b41 through b50) are opened by both p1 and p2, so c = 10.) We will separate the event E1 into two disctinct subevents:

  • E1A = "p1 found his name in a box which p2 also opened".
  • E1B = "p1 found his name in a box which p2 didn't open".

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

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

So P(E1 and E2) = P(E1) * P(E2|E1) = 1/2 * P(E2|E1) = 1/2 * (P(E2|E1A) + P(E2|E1B)) = 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 ;)

Link to comment
Share on other sites

  • 0

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

 

Hidden Content

Mistakes were made!

"I can easily prove that P(E1 and E2) ≤ 25%" should be "I can prove that P(E1 and E2) ≤ 25/99 < 30%"

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

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

The final calculation should be P(E1 and E2) = P(E1) * P(E2|E1) = 1/2 * P(E2|E1) = 1/2 * (P(E2|E1A) + P(E2|E1B)) = 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.

Link to comment
Share on other sites

  • 0

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

Link to comment
Share on other sites

  • 0

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."  :rolleyes:
Did I forget to mention that the boxes are externally numbered 1-100?
They are, and now the OP says so.

Link to comment
Share on other sites

  • 0

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% !!

Link to comment
Share on other sites

  • 0

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."  :rolleyes:
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.

Link to comment
Share on other sites

  • 0

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 by bonanova
Amending one of my claims.
Link to comment
Share on other sites

  • 0

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.

 

findNamesInBoxes.gif

Edited by jasen
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...