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
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.)
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.
Back to main page