Life In 19x19

Posted: **Wed Dec 15, 2010 3:36 am**

HermanHiddema wrote:
tj86430 wrote:I would like to see the solution, please. If you don't want to post it here, pm me.
As requested, the solution:

On the evening in advance, the prisoners get together and assign a number (1 through 100) to each prisoner. Each prisoner memorizes the numbers of all prisoners. This means that each box is now virtually marked with a prisoner name on the outside. It also means that the piece of paper in any box can now be seen as a reference to a box. Effectively, the boxes have become a permutation of the numbers 1-100, referencing each other.

The next day, each prisoner enters the room and opens the box with his own number on it. If it contains his name, he's done. If it contains another prisoners name, he next opens that prisoners box. He repeats this procedure, following the references to new boxes, until he has found his name, or until his 50 tries are up.

Each permutation is guaranteed to contain loops, and every box is guaranteed to be part of exactly one loop. The shortest loops are when a box points to itself (loop of length 1) or when two boxes point to each other (length 2). The longest possible loop has length 100 (each box points to a new box, until the 100th box in the sequence points back to the first).

The prisoners all go free if the longest loop in the permutation contains at most 50 boxes. The chance of that is 1 - ln(2), which is about 31.18%

Background article: http://www.sciencenews.org/view/generic ... s_in_Boxes

The strategy is pretty clear. Ok I accept, if it works it works

But I still have two problems with it:

1- I still don't get how you calculate 1-ln(2). It is not at all apparent for me that the probability of the longest loop not exceeding 50 is 1-ln(2). But anyway that's pure mathematics. My next problem is more important, which is:

2- Is there a proof that this strategy gives the highest survival probability?

While understanding the strategy and how it works, I must admit that I don't get the feeling of it. Why would creating such a "linked list" maximise the survival probability?
Which information do you exploit for increasing the probability?

Posted: **Wed Dec 15, 2010 4:20 am**

entropi wrote: 2- Is there a proof that this strategy gives the highest survival probability?

Not that I know of, but obviously I also do not know a better strategy.

While understanding the strategy and how it works, I must admit that I don't get the feeling of it. Why would creating such a "linked list" maximise the survival probability?
Which information do you exploit for increasing the probability?

For each individual prisoners, the chance of finding their name has not increased (nor has it decreased). Each prisoner still has 50% chance of finding their name. The strategy just ties them together. So now either all the prisoners in the loop fail, or none of them fail (depending on the loop length). And by doing that, we eliminate the possibility that fewer than 51 prisoners will fail. If the longest loop is at least 51, then all the prisoners in that loop will fail. If the longest is 50 or less, nobody fails. So all the cases of 1,2,3,4,....,47,48,49,50 prisoners failing have suddenly been eliminated.

At the same time, all the cases of 51,52,53,54....,97,98,99,100 prisoners failing have had their chance increased. With a random strategy, the chance of all prisoners failing is as astronomical as all of them succeeding. With this strategy, the chance of all prisoners failing is exactly 1%. Here too, the strategy ties the prisoners together in sharing their fate.

Posted: **Thu Dec 16, 2010 6:38 pm**

entropi wrote:
1- I still don't get how you calculate 1-ln(2). It is not at all apparent for me that the probability of the longest loop not exceeding 50 is 1-ln(2). But anyway that's pure mathematics. My next problem is more important, which is:

Herman is quite pessimistic. His probability of 1 - ln2 is correct in the limit towards infite prisoners. I guess in the finite case at hand the survival chance is exactly 1/2 - 1/3 + 1/4 ...... + 1/100 which is about 0.01 % better than Herman's value. I didn't manage to prove my formula yet. At least I checked it for n =2 and n = 4. When I was trying n = 6 to discover the system, some friends came to visit me unexpectedly, disturbing my cycles. Odysseus' descendents, Cyclops presumed.

Posted: **Fri Dec 17, 2010 2:49 pm**

entropi wrote:
1- I still don't get how you calculate 1-ln(2). It is not at all apparent for me that the probability of the longest loop not exceeding 50 is 1-ln(2). But anyway that's pure mathematics. My next problem is more important, which is:

I'll try to calculate what is the probability that there is one cycle of length 51 exactly if we shuffle the numbers 1 to 100.
There are 100! shuffles ( permatutions ). How many contain a 51 cycle?
There are 100 over 51 that is 100! / ( 51! * 49! ) ways to divide the numbers in two groups: the 51 cycle group and the rest. The rest can be ordered at 49! different ways.
For the 51 cycle we have 50 ways to choose the first element, 49 ways for the second and so on. So from 51 numbers one can realize a 51 cycle in 50! ways.
All together, taking quotients and products, the probability is 1/51.

For Herma's problem to get the probability of failing:
You repeat this for 51-cycles to 100-cycles and add the probabilities. ( They are exclusive ). So you get:
1/51 + 1/52 + 1/53 + .. .. + 1/100 as the probability for failure.
Somehow this sum equals 1 - 1/2 + 1/3 - 1/4 .. + 1/100. And this approaches ln(2).
Because ln(1+x) = x - x^2/2 + x^3/3 - x^4/4 ... ( substitute x = 1 )

Posted: **Fri Dec 17, 2010 4:38 pm**

For a derivation of the probability in the prisoner puzzle see wikipedia.

Posted: **Fri Dec 17, 2010 5:11 pm**

Redundant wrote:For a derivation of the probability in the prisoner puzzle see wikipedia.

better lay-out indeed. thx

Posted: **Fri Dec 17, 2010 5:44 pm**

entropi wrote: 2- Is there a proof that this strategy gives the highest survival probability?
While understanding the strategy and how it works, I must admit that I don't get the feeling of it. Why would creating such a "linked list" maximise the survival probability?
Which information do you exploit for increasing the probability?

a. Eugene Curtain and Max Washauer have recently proved that this solution cannot be improved
upon. ( from link.pdf )
b. Why it works. Assume two prisoners. If they choose random their chance is 25 %. If they agree upon mr one choosing the first box and mr two the second box. Now their chance is 50%. They made sure they succeed or fail together.
If you next try 4 prisoners by hand you see why it works. If they fail as team at least 3 of them has failed personally.

Posted: **Fri Dec 17, 2010 6:35 pm**

cyclops wrote: 1/51 + 1/52 + 1/53 + .. .. + 1/100 as the probability for failure.
Somehow this sum equals 1 - 1/2 + 1/3 - 1/4 .. + 1/100.

This can be proven quite easily by induction.

Life In 19x19

Logical puzzles

Re: Logical puzzles

Re: Logical puzzles

Re: Logical puzzles

Re: Logical puzzles

Re: Logical puzzles

Re: Logical puzzles

Re: Logical puzzles

Re: Logical puzzles