PUZZLE SOLUTION: Group Strategy

This is the solution to the puzzle Group Strategy that I posted a few weeks ago. Make sure you give it a try before reading further.

Intro:

There are multiple ways one can approach the solution. Some need more combinatorial background than the others. One intuitive way that Carl Worth suggested was: what should the strategy look like if we want to make sure that the identity permutation always leads to success? Easy, each man should make sure to look into the box numbered as himself. Now what if the permutation is not identity, but identity plus one swap? Continue...

Another approach is probabilistic. Any strategy that has each man's rate of success in finding his number be probabilistically independent of the others is destined to fail with a total success rate of at most 2^-2k. So, in any winning strategy, the success rate of the men are not independent. A corollary is that no man should know which boxes he's going to open until after he entered the room. Think about it (and no, don't think about random strategies).

Strategy:

So here is the winning strategy: Each man enters the room, opens the box numbered as himself and reads the paper inside; while not found, he then opens the box with the number written on piece of paper in the last box he opened.

Of course, every man still has the exact same rate of individual success: 1/2, but what the algorithm does is to kinda "align" their success runs together so as a group they succeed with a surprisingly huge probability: more than 30%!

Proof:

The algorithm becomes a lot more intuitive if one imagines the graph representation of the permutation that the boxes represent. The graph representation of our permutation has 2k nodes, and node i has an edge towards node j if number j is in box i. This is a directed graph.

Permutation graphs are always a set of (possibly size 1) cycles because each node has in and out degrees of exactly one. The man numbered i wants to find the node that has an outgoing edge to i. Well, looking at the problem this way, the strategy is trivial: start from node i and follow the cycle, until you get back to i. That's all everyone has got to do!

The success probability of the group is equal to the probability that the permutation graph has no cycle longer than k. And since there are only 2k nodes and each node is in exactly one cycle, there can exist at most one cycle longer than k. The question is: what is the probability that a cycle longer than k exists. This is the failure probability.

Getting this far you can claim having solved the puzzle! Now to get a tight bound: I used straight counting. Failure probability is the sum of probability that a cycle of size c exists, for c from k+1 to 2k. The probability that such a cycle exists is the number of permutations with such a cycle divided by total number of permutations (2k!). Finally lets count how many such permutations exist: Choose c members for the cycle and divide by c because the order is not important: 2k! / ((2k-c)! * c). Finally permute the remaining members: (2k-c)!. It simplifies drastically and at the end, failure probability becomes exactly H(2k) - H(k), where H(n) is the n'th Harmonic number. A tight upper bound to this failure probability is ln(2k) - ln(k), which is ln(2). So, success probability is not less than 1 - ln(2), which is a bit over 30%.

The math set using my embedded TeX engine (click for other sizes):

Update:

Proof that the bound is tight: While failure probability is not more than ln(2k) - ln(k), using the same idea, it's not less than ln(2k+1) - ln(k+1). So, success probability is between 1 - ln(2) and 1 - ln(2 - 1/(k+1)).

Labels: puzzle, solution

¶ 4:13 PM