Using your Head is Permitted

January 2012 riddle

UPDATE (1 January): The riddle was shortened from two parts to one part, due to an error in one of the parts. Thanks go to Jan Fricke for spotting it.

UPDATE (5 January): One correction to the riddle and one clarification. First, the correction: the input numbers are not only identically distributed but actually uniformly distributed in their range. So are the output numbers. (Thanks to Radu-Alexandru Todor for pointing out that this fact was omitted between revisions of the riddle.)
Now, the clarification: The main difference between this riddle and IBM PT's September 2011 riddle is that here the requirement is to handle streams. That is to say, it is not enough to handle n-number inputs for every n. The algorithm must receive at each iteration a single new number, with these numbers incrementally building up to arbitrarily long number strings. After each new input, the algorithm must output as many new output numbers as are possible, in expectation.

This riddle is a variation on IBM's Ponder This September 2011 challenge, based on an idea by Bart de Vylder.

A computer program receives a stream of integers that represent the values of independent identically distributed random variables in the range [0, ..., A-1]. Its output is a stream of integers that should be independent identically distributed random variables in the range [0, ..., B-1]. We want the expected number of output integers to be maximal after the program receives n inputs, for every n.

Describe (with proof) an algorithm for this.

List of solvers:

Joseph DeVincentis (6 January 03:41)
Omer Angel (15 January 10:05)

Elegant and original solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!

To solution

Back to main page