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 |