Logical puzzles

entropi · **#101**

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:

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?

HermanHiddema · **#102**

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.

Quote:

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.

cyclops · **#103**

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.

cyclops · **#104**

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 )

Redundant · **#105**

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

cyclops · **#106**

Redundant wrote:

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

better lay-out indeed. thx

cyclops · **#107**

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.

cyclops · **#108**

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.

Logical puzzles

Who is online