The 100 prisoners puzzle

Unbelievable puzzle... Look at the code below, or better yet, download and run it...

#!/usr/bin/env python import itertools # The 100 prisoners problem statement: # # The warden places 100 numbers in 100 boxes, at random - with equal # probability that any number will be in any box. Each convict is assigned # a number. One by one they enter the room with the boxes, and try to find # their corresponding number. They can open up to 50 different boxes. Once # they either find their number or fail, they move on to a different room # and all of the boxes are returned to exactly how they were before the # prisoner entered the room. The prisoners can communicate with each # other before the game begins, but as soon as it starts they have no way # to signal to each other. The warden is requiring that all 100 prisoners # find their numbers! # # At first glance, since each of them has 50% chance (0.5), the probability # of all of them succeeding is (0.5)^100 = .... zero. # # And yet, with the approach described below, the chance of success # (i.e. ALL of them finding their number) is 31.2% !!! # # In fact, for N prisoners, with N=2*k, the probability of success is: # # p(success) = 1-(1/M + 1/(M+1) + ... + (1/N)) # where # M = N/2 + 1 # # So, for N=8: 1-(1/5+1/6+1/7+1/8) = .36547619047 # for N=10: 1-(1/6+1/7+1/8+1/9+1/10) = .35436507936 # for N=100: 1-(1/51+1/52+...+ 1/100) = .31182782069 # # Brilliant description of the puzzle's solution here: # http://www.mast.queensu.ca/~peter/inprocess/prisoners.pdf def CheckSolution(prisoners, perm): for i in xrange(prisoners): attempt = 0 idx = i found = False while attempt < prisoners/2: # You have N/2 attempts... if perm[idx] == i: # Look in your box... found = True # you found your number, great! break else: idx = perm[idx] # else "seek" to the number inside the box attempt += 1 if not found: return False # This permutation failed, it had a cycle>N/2 return True # This permutation was a good one... def main(): for prisoners in xrange(4, 12, 2): # Do the experiment for 4,6,8,10 total = 0 success = 0 for perm in itertools.permutations(xrange(prisoners)): total += 1 if CheckSolution(prisoners, perm): success += 1 print "When", prisoners, "prisoners,", print "Saved:", success, "/", total, print "(%5.2f)" % (100.0*success/total) if __name__ == "__main__": main()

bash$python ./100prisoners.py When 4 prisoners, Saved: 10 / 24 (41.67) When 6 prisoners, Saved: 276 / 720 (38.33) When 8 prisoners, Saved: 14736 / 40320 (36.55) When 10 prisoners, Saved: 1285920 / 3628800 (35.44)

Index CV | Updated: Fri Aug 9 22:48:30 2013 |

The comments on this website require the use of JavaScript. Perhaps your browser isn't JavaScript capable or the script is not being run for another reason. If you're interested in reading the comments or leaving a comment behind please try again with a different browser or from a different connection.