January 2008
<<December January February>>
Ponder This Solution:
The answer is the following piecewise linear function, f(c).
For 0 < c < 1/4 ; f(c) = 3/2 - 3*c
For 1/4 < c < 3/8 ; f(c) = 17/12 - (8/3)*c
For 3/8 < c < 1/2 ; f(c) = 7/6 - 2*c
For 1/2 < c < 13/22 ; f(c) = 13/12 - (11/6)*c
For 13/22 < c < 1 ; f(c) = 0
A sketch of the derivation follows. First we claim if we are drawing balls randomly from an urn containing n balls initially known to contain 0,1,2 ... n white balls with equal probability (with the remainder of the balls being black) and we have drawn a white balls and b black balls (a+b < n) the probability that the next ball is white is (a+1)/((a+1)+(b+1)). Suppose first n=a+b+1. Then we can have 1 white ball left over from an initial contents of a+1 white balls (and b black balls) which will occur with probability ((a+1)/n)*(1/(n+1)) or we can have 1 black ball left over from an initial contents of a white balls and b+1 black balls which will occur with probability ((b+1)/n)*(1/(n+1)). So the probability the last ball is white is (a+1)/((a+1)+(b+1)). Now suppose there are several remaining balls. The result is the same since as is easily checked if we throw out 1 ball without looking at it the remaining n-1 balls are equally likely to contain 0,1, ... or n-1 white balls.
Using the above result and working backwards from the cases where there is just one ball remaining it is straightforward albeit a bit tedious to derive the answer. For c < 1/4 you should buy all the balls. For 1/4 < c < 3/8 you should stop buying if the first two balls are black. For 3/8 < c < 1/2 you should stop buying if the first ball is black. For 1/2 < c < 13/22 you stop buying as soon as you buy a black ball. For 13/22 < c you should not buy any balls.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com