IBM Research | Ponder This | May 2010 challenges
Skip to main content

Ponder This

May 2010

<<April May June>>

Ponder This Challenge:

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

If you have any problems you think we might enjoy, please send them in. All replies should be sent to:


Challenge: 05/03/2010 @ 03:00 PM EST
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