#!/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()