December 2006
<<November December January>>
Puzzle for December 2006.
Consider a random permutation, P, on n elements. P can be decomposed into cycles. Let x be a fraction between .5 and 1. Let f(x,n) be the probability that all the cycles of P have size less than x*n. This month's problem is to find the asymptotic behavior of f(x,n) for fixed x as n --> infinity.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
12/01/2006 @ 12:00 PM EST
Solution:
01/02/2007 @ 11:00 AM EST
List Updated:
01/09/2007 @ 12:30 PM EST
People who answered correctly:
Roberto Tauraso (12.01.2006 @03:06:36 PM EST)
V. Balakrishnan (12.01.2006 @05:24:13 PM EST)
Charles Reilly (12.01.2006 @05:56:50 PM EST)
Dave Blackston (12.01.2006 @07:31:26 PM EST)
Alan Murray (12.02.2006 @01:26:52 AM EST)
Dan Dima (12.02.2006 @08:02:48 AM EST)
Firat Solgun (12.02.2006 @08:57:01 AM EST)
Frank Yang (12.02.2006 @12:02:36 PM EST)
Amghibech Said (12.02.2006 @01:24:24 PM EST)
John T. Robinson (12.02.2006 @02:59:02 PM EST)
Rich Kaye (12.02.2006 @03:54:58 PM EST)
Yoav Raz (12.02.2006 @06:44:20 PM EST)
Miroslava Sotakova (12.03.2006 @02:49:36 AM EST)
Oded Margalit (12.03.2006 @10:04:41 AM EST)
John G. Fletcher (12.03.2006 @07:36:40 PM EST)
Eddie Marcus (12.03.2006 @10:56:21 PM EST)
Arjun Archarya (12.03.2006 @11:29:20 PM EST)
Eugene Vasilchenko (12.04.2006 @09:42:28 AM EST)
Wolfgang Kais (12.04.2006 @11:52:04 AM EST)
Frank Mullin (12.04.2006 @01:42:34 PM EST)
Christian Blatter (12.04.2006 @02:18:08 PM EST)
Jack Kennedy (12.04.2006 @02:38:59 PM EST)
David Friedman (12.04.2006 @05:00:11 PM EST)
Tom Gutman (12.04.2006 @06:44:17 PM EST)
Zhou Guang (12.06.2006 @04:14:26 AM EST)
arnab.x.bose (12.07.2006 @03:32:52 AM EST)
Jiri Hrdina (12.07.2006 @07:58:35 AM EST)
Fang Yu (12.07.2006 @01:19:35 PM EST)
Phil Muhm (12.07.2006 @01:20:11 PM EST)
Riyaaz Shaik (12.08.2006 @07:22:54 AM EST)
John Tromp (12.08.2006 @05:18:13 PM EST)
Ashish Srivastava (12.08.2006 @08:10:39 PM EST)
dineshk (12.09.2006 @12:08:31 PM EST)
Michael Quist (12.09.2006 @10:37:36 PM EST)
Justin T. Miller (12.11.2006 @12:47:14 PM EST)
Matthew Samuel (12.11.2006 @11:07:04 PM EST)
Lawrence Hon (12.11.2006 @11:54:44 PM EST)
David McQuillan (12.12.2006 @01:15:23 PM EST)
Ed Shepard (12.12.2006 @03:54:34 PM EST)
Rajeev Rao (12.12.2006 @07:27:26 PM EST)
Du Yang (12.13.2006 @06:12:59 PM EST)
Yurun Liu (12.13.2006 @10:33:19 PM EST)
Ashutosh Mahajan (12.14.2006 @07:56:23 AM EST)
Bryan Bell (12.17.2006 @06:43:23 PM EST)
John Durham (12.19.2006 @09:18:10 PM EST)
Viral Gupta (12.22.2006 @02:33:22 AM EST)
Jakub Łopuszański (12.25.2006 @02:17:29 PM EST)
Arthur Breitman (12.26.2006 @01:13:08 PM EST)
Ray Gregory (12.27.2006 @04:26:56 PM EST)
Dharmadeep Muppalla (12.28.2006 @07:33:07 AM EST)
Se Kwon Kim (12.28.2006 @10:16:21 AM EST)
Chris Messer (12.31.2006 @08:48:26 PM EST)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.