There’s a problem that a coworker recently brought up. The problem statement can be found here.
This is a re-hash of an existing problem known as the one hundred prisoners problem. It seems impossible at first, and many naive approaches yield failing results. But, given the correct approach, it is solvable with a surprisingly high probability.
It’s really just a permutation problem. The basic idea is that the boxes are numbered 1..100 and they all contain a bill with a number 1..100. To construct a working solution, you use the bills as pointers to box numbers in the following way. You start at the box labelled with your number, and go to the box number of the bill it contains. Keep doing that, looking in the box and going to the box of the bill you find inside. Eventually, you get to the box containing the bill that points to where you started – and that’s the bill you’re looking for. So, the question really becomes: How often does a random permutation of degree $n$ contain a cycle having length greater than $n/2$? If you get a longer cycle, then anyone with a number in that cycle is screwed because it takes them longer than $n/2$ steps to find their bill. If there are only cycles having lengths less than $n/2$, then everyone can find their bill in the appropriate number of steps.
So, how many random permutations of degree $n=100$ contain only cycles having length less than 50? For this, we can look at approximations given by Stirling numbers of the first kind. Essentially, the number of random permutations having only cycles of length less than $n/2$ (in our case 50) as asymptotic to $log(2)$, which is around 0.3010. That’s a bit surprising, because it means that the strategy above is expected to win roughly 30% of the time for large numbers of boxes.
Testing with Sage
How well does the strategy actually perform when $n=100$? We can test this out in Sage.
""" Generate a random permutation on 1..n and compute the longest orbit."""
return max([len(i) for i in Permutations(n).random_element().cycle_tuples()])
won = 0
tries = 10000
for i in range(tries):
if max_length_orbit_random_perm(100) <= 50:
won += 1
print "won %s out of %s" % (won, tries)
And we get the following.
So, we win roughly 3 out of 10 times. If we were charged $1 to play the game, but won $100 if everyone found their dollar, then we’d be doing very well to play the game.