May 2010
The idea for this month's challenge came from a presentation given by Ohad Rodeh.
Let P = {p_i}_{i=0}^9 be a probability distribution over the digits (\sum_{i=0}^9 p_i = 1).
There are infinitely many possibilities for P.
A common way to make this number finite is to quantize each p_i into, say, four different bins.
The obvious way to do this is as follows: 0<=x<0.25; 0.25<=x<0.5; 0.5<=x<0.75; and 0.75<=x<=1.
A. How many, out of the 4^10=1,048,576 possibilities, can be realized by a probability vector?
B. If we change the boundaries of the four bins, what is the maximum number of possibilities that can be realized?
Update: May 6th: To those of you who do not master TeX notation, P is a vector of ten non-negative real numbers (p0,p1,p2,...,p9) and their sum (p0+p1+p2+...+p9) is 1.
Update: May 6th: In part B you can change the boundaries of the intervals, but they must be disjoint: [0,A) [A,B) [B,C) and [C,1] for 0<A<B<C<1.
Update: May 9th: For example, if P=(0.01,0.02,0.04,0.03,0.1,0.51,0.01,0.01,0.26,0.01) then the quantized version, according to part A, is (a,a,a,a,a,c,a,a,b,a); and for part B, if we change the boundaries (for example) to a=[0,0.05); b=[0.05,0.15); c=[0.15,0.44); d=[0.44,1] we get (a,a,a,a,b,d,a,a,c,a). (d,d,d,d,d,d,d,d,d,d) is not realizeable since there is no probability vector with all 10 elements greater than 0.44.
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:
05/03/2010 @ 03:00 PM EST
Solution:
List Updated:
05/03/2010 @ 03:00 PM EST
People who answered correctly:
John T. Robinson (04/30/2010 11:53 PM EDT)
Joseph DeVincentis (05/01/2010 12:41 AM EDT)
Michael Liepelt (05/01/2010 08:38 AM EDT)
Pataki Gergely (05/01/2010 12:02 PM EDT)
Amos Guler (05/02/2010 03:47 PM EDT)
Arthur Breitman (05/03/2010 03:07 PM EDT)
Dan Colestock (05/03/2010 12:24 PM EDT)
Michael Brand (05/04/2010 07:05 AM EDT)
Don Dodson & David Dodson (05/04/2010 05:28 PM EDT)
Tom Sirgedas (05/04/2010 06:34 PM EDT)
Viacheslav Chernoy (05/04/2010 09:17 PM EDT)
Dmitry Litvinenko (05/05/2010 01:59 PM EDT)
Adam Daire (05/05/2010 07:05 PM EDT)
Artiom Myaskouvskey (05/06/2010 03:57 AM EDT)
Austin Shapiro (05/06/2010 11:43 AM EDT)
Chuck Grant (05/06/2010 12:04 PM EDT)
Mark Mixer (05/06/2010 03:12 PM EDT)
Motty Porat (05/06/2010 06:10 PM EDT)
Jonathan Campbell (05/06/2010 06:25 PM EDT)
John Ritson (05/06/2010 08:23 PM EDT)
Ross Millikan (05/06/2010 09:40 PM EDT)
Clive Tong (05/08/2010 05:14 AM EDT)
Sevag Papazian (05/08/2010 07:11 AM EDT)
Thomas Jessen (05/08/2010 11:30 AM EDT)
Albert Stadler (05/09/2010 05:41 AM EDT)
Daniel Bitin (05/09/2010 08:17 AM EDT)
Nicolas Landes (05/09/2010 02:39 PM EDT)
Dan Ignatoff (05/09/2010 07:07 PM EDT)
David Friedman (05/10/2010 02:05 PM EDT)
Dan Dima (05/10/2010 06:46 PM EDT)
Danny Antonetti (05/10/2010 09:42 PM EDT)
Phil Benamy (05/11/2010 01:41 AM EDT)
Ari Freund (05/11/2010 03:21 AM EDT)
Andreas Stiller (05/11/2010 08:46 PM EDT)
Serge Thill (05/12/2010 05:43 PM EDT)
Christian Blatter (05/14/2010 04:29 AM EDT)
Lachezar Hristov (05/14/2010 04:34 AM EDT)
Jonathan A Wildstrom (05/14/2010 10:53 AM EDT)
Harald Bögeholz (05/15/2010 12:10 PM EDT)
Don Ryan (05/17/2010 02:48 AM EDT)
Venkata Ramayya (05/17/2010 07:24 AM EDT)
Sylvain Becker (05/17/2010 06:16 PM EDT)
Jan Fricke (05/18/2010 01:26 PM EDT)
Abhishek Jha (05/21/2010 05:30 PM EDT)
Anoop Varghese (05/22/2010 01:09 PM EDT)
William Heller (05/23/2010 10:24 AM EDT)
Sidharth Lath (05/23/2010 10:58 AM EDT)
Varun Jindal IIT Kanpur (05/25/2010 01:39 PM EDT)
Fabio Filatrella (05/25/2010 02:13 PM EDT)
Nagy Zoltan (05/25/2010 02:58 PM EDT)
Adel El-Atawy (05/26/2010 02:25 PM EDT)
Khalid Elbadawi (05/28/2010 10:29 PM EDT)
Matthew Paterson (05/30/2010 01:59 PM EDT)
John G Fletcher (05/30/2010 06:03 PM EDT)
Adriana Clerici (05/31/2010 11:16 AM EDT)
Se Kwon Kim (05/31/2010 08:01 PM EDT)
Nyles Heise (05/31/2010 09:41 PM EDT)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.