About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
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