Behdad Esfahbod's daily notes on GNOME, Pango, Fedora, Persian Computing, Bob Dylan, and Dan Bern!

My Photo
Name:
Location: Toronto, Ontario, Canada

Ask Google.

Contact info
Google
Hacker Emblem Become a Friend of GNOME I Power Blogger
follow me on Twitter
Archives
July 2003
August 2003
October 2003
November 2003
December 2003
March 2004
April 2004
May 2004
July 2004
August 2004
September 2004
November 2004
March 2005
April 2005
May 2005
June 2005
July 2005
August 2005
September 2005
October 2005
November 2005
December 2005
January 2006
February 2006
March 2006
April 2006
May 2006
June 2006
July 2006
August 2006
September 2006
October 2006
November 2006
December 2006
January 2007
February 2007
March 2007
April 2007
May 2007
June 2007
July 2007
August 2007
September 2007
October 2007
November 2007
December 2007
January 2008
February 2008
March 2008
April 2008
May 2008
June 2008
July 2008
August 2008
October 2008
November 2008
December 2008
January 2009
March 2009
April 2009
May 2009
June 2009
July 2009
August 2009
November 2009
December 2009
March 2010
April 2010
May 2010
June 2010
July 2010
October 2010
November 2010
April 2011
May 2011
August 2011
September 2011
October 2011
November 2011
November 2012
June 2013
January 2014
May 2015
Current Posts
McEs, A Hacker Life
Saturday, June 02, 2007
 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):

Group Strategy


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: ,

Comments:
Your strategy as described doesn't seem optimal. Consider a 4-player game, with 4 boxes, where boxes 1,2,3,4 contain the number 4,1,3,2. This is a loser because there is a permutation group of length 3. But as you describe it, a player who picks box 3, which contains 3, will loop forever, while picking another box at random will increase his probability of success.

But it doesn't affect the probability of winning in the limit, since the players are reduced to guessing at random.
 
This is a good post. I like the clear explanation; it's a very very elegant solution.
 
Post a Comment



<< Archive
<< Home