May 2010
Part A:
We number the bins from the first bin, [0,0.25), as bin #0; and the last bin [0.75,1], as bin #3. A 10-tuple of 4-bins (b1,b2,...,b10) is realizable if and only if b1+b2+...+b10 <= 4. There is a one-to-one mapping of 10 non-negative integers whose sum is no more than 4, with an arrangement of 10 balls and 4 bars. Out of the (14 \choose 4) such arrangements, 10 are illegal (we have 0,1,2,3 so we cannot use 4). The answer is therefore 1001-10=991.
Part B:
If we take any realizable quantization and shift every probability D bins to the left (or right), it is easy to see that we get a non-realizable quantization. Therefore, there are at least 3^10 unrealizable quantization since all the ones with an empty first bin are either unrealizable, or at least one shift of them is. This bound is tight since, for example, [0,0.01) [0.01,0.02) [0.03 0.04) [0.04 1] achieves it by realizing exactly 4^10-3^10=989527 possibilities.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com