EPTGuess nobody will read this now but I'm gonna try to solve and post it now anyway -_-
100 Prisoners Problem - Page 3
| Blogs > Slithe |
|
jtan
Sweden5891 Posts
Guess nobody will read this now but I'm gonna try to solve and post it now anyway -_- | ||
|
jtan
Sweden5891 Posts
This will mean they all survives if the permutation of names in boxes contains no orbits of greater length than 50. Now for the calculation of the probability The probability that there IS atleast 1 orbit with greater length than 50 will be exactly: p=(Sum n=51..100((100 over n)(n-1)!(100-n)!))/100! + Show Spoiler [explanation] + For each term of the sum: (100 over n) (means the binomial coefficient): Pick n of the boxes. (n-1)!: put theese n boxes in an orbit. Start with the n'th box where you have n-1 possibilites for a name to another box: everone except itself. For the n-1'th box you can pick any box except itself and the n'th box and so on. (100-n)!: Permute the remaining 100-n boxes arbitrarily (doesn't matter how many orbits arises here) The sum will then contain all cases where the longest orbit is 51 or longer. Then divide by all possible permutations=100! to get the probability p. Expand the binomial coefficient and do some basic arithmetic and it amazingly reduces to almost nothing: p=Sum n=51..100 (1/n) Now for a value, compare it with an integral p < Integral x=50..100 (dx/x) = ln 100-ln 50=ln 100/50 = ln 2 So the chance that they survive=1-p is greater than 1-ln2 ~=0.31 Another quick integral comparison shows that the error in this number will be about 0.005. A fun thing is that it doesn't matter how many prisoners there are, as long as they can pick half of the boxes. With a million prisoners you get even closer to 1-ln2. Nice problem, keep posting these! | ||
| ||
