[Guest]

On an island inhabited by tribals, 100 Englishmen were held captive. One day the leader of the tribe decided that the deserved one chance to save themselves. He ordered for 100 wooden boxes and placed into each of them a name of one of the 100 prisoners. The boxes were then lined up on a table in one of the huts.

The rules were simple:

1. The Englishmen would be led into the hut one by one and one at a time.

2. He was allowed to open at most 50 boxes. After that, he had to shut the boxes and leave the hut and wait in another hut for the remaining men to finish their turns.

3. Once he entered the hut with the boxes, he was not permitted to communicate with any of the others.

4. The Prisoner's can't change the positions of the boxes or disturb the arrangement in any way.

The prisoners are, however, given an opportunity to plan out their strategy a day prior to the day when they have to enter the hut. The stakes for them were very high as each prisoner would HAVE to find a box with his name in it. Failing to do so would mean that all of them would be hanged to death. Help them chalk out a plan that has at least a 30% probability of success. Provide a detailed explanation along with your answer.

[bonanova]

Well the strategy can't produce a winning probability

50%.

Prisoner 1 opens the first 50 boxes, and there is a 50% chance he doesn't find his name.

But it also can't be

50%, either,

Prisoner 1 opens the first 50 boxes.

He places each name he finds in front of its respective box.

Prisoner 2 opens the last 50 boxes and does the same.

He and all the remaining prisoners finds his name.

[superprismatic]

The prisoners randomly assign numbers (1-100) to names.

The prisoner whose name is assigned to N looks in the

Nth box. If it contains his name, he is successful.

If it does not, he converts the name in the box to a

number based on the agreed-upon assignment and looks

in that box. He keep doing this until either he finds

his name or he has looked in 50 boxes. The boxes with

names are, thus, a permutation of the numbers 1-100.

The prisoners will all find there names if all of the

cycles of this permutation have length less than 51.

It is easy (but tedious) to show that the probability

of such a cycle structure is 1-log(2) which is

approximately .307.

Edit: log here is the natural logarithm, now usually written ln.

[Guest]

The prisoners randomly assign numbers (1-100) to names.

The prisoner whose name is assigned to N looks in the

Nth box. If it contains his name, he is successful.

If it does not, he converts the name in the box to a

number based on the agreed-upon assignment and looks

in that box. He keep doing this until either he finds

his name or he has looked in 50 boxes. The boxes with

names are, thus, a permutation of the numbers 1-100.

The prisoners will all find there names if all of the

cycles of this permutation have length less than 51.

It is easy (but tedious) to show that the probability

of such a cycle structure is 1-log(2) which is

approximately .307.

Edit: log here is the natural logarithm, now usually written ln.

the answer is correct

could you please explain the final solution how you got that 1-log2(actually thats what I am really intrested in)

Edited August 7, 2011 by TrUnX

[superprismatic]

the answer is correct

could you please explain the final solution how you got that 1-log2(actually thats what I am really intrested in)

OK, here goes.....

Let's count the number of ways to make a 100-long permutation

with an N-cycle with N>50 (only one of these can be in a

100-long permutation). There are 100!/((100-N)!×N!)

ways to pick the elements of the cycle, (N-1)! ways to

order them (it's not N! because the N circular shifts

shifts don't change what the cycle is), and there are

(100-N)! ways to permute the things not on the cycle. So,

the number of ways to make a permutation with an N-cycle

is (100!/((100-N)!×N!))×((N-1)!)×((100-N)!) = 100!/N.

Divide this by 100! (the number of permutations) and we

get that the probability of having an N-cycle is 1/N.

So, the probability we seek is 1-(1/51)-(1/52)-...-(1/100),

as this is the probability of NOT having a cycle 51 or larger.

Now, Euler proved that the sum of the reciprocals of the

first K natural numbers is approximately ln(K). Using that,

1-(1/51)-(1/52)-...-(1/100) = 1-(1/1)-(1/2)-...-(1/100)+

(1/1)+(1/2)+...+(1/50) ≈ 1-ln(100)+ln(50) = 1-ln(2×50)+ln(50)

= 1-ln(2)-ln(50)+ln(50) = 1-ln(2). The particulars of

Euler's approximation make this an underestimate.