Ponder This Challenge - January 2008 - Buying random balls out of an urn

Ponder This Challenge:

This month's puzzle concerns drawing balls from an urn. You know the urn contains 3 balls. You know each ball is white or black and that white balls are worth 1 unit, black balls are worth nothing. You know the urn is equally likely to contain 0,1,2 or 3 white balls. You have an opportunity to buy balls from the urn. Each ball costs c units (0<c<1). When you buy a ball one of the remaining balls in the urn is randomly selected and given to you. You may stop buying balls at any time based on the color of the balls you have received. Assuming you adopt the best strategy, what is your expected return as a function of c?

UPDATE, 1/3/08: You do not have to buy any balls. By return I mean the value of the balls you receive minus their cost.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  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

Solvers

• Ryan Milligan (01.02.2008 @05:30:00 AM EST)
• Andreas Eisele (01.02.2008 @05:30:06 AM EST)
• V. Balakrishnan (01.02.2008 @08:58:53 AM EST)
• Dan Dima (01.02.2008 @09:34:17 AM EST)
• Luke Pebody (01.02.2008 @11:17:30 AM EST)
• Frank Yang (01.02.2008 @12:42:14 PM EST)
• Fred Batty (01.02.2008 @01:13:01 PM EST)
• Jimmy Hu (01.02.2008 @04:28:20 PM EST)
• Eugene Vasilchenko (01.02.2008 @04:52:27 PM EST)
• Mark Perkins (01.02.2008 @05:23:19 PM EST)
• John Tromp (01.02.2008 @05:24:32 PM EST)
• Christian Blatter (01.03.2008 @05:30:49 AM EST)
• Karl Morton (01.03.2008 @12:01:03 PM EST)
• William C. Hasenplaugh (01.03.2008 @12:23:56 PM EST)
• Joe Fendel (01.03.2008 @01:06:56 PM EST)
• Erik Hostens (01.03.2008 @01:21:58 PM EST)
• Mehmet Soyturk (01.03.2008 @05:42:38 PM EST)
• Kai Guttmann (01.03.2008 @06:20:17 PM EST)
• Joshua Green (01.03.2008 @10:44:42 PM EST)
• John Ritson (01.03.2008 @11:03:30 PM EST)
• Hongcheng Zhu (01.04.2008 @03:24:16 AM EST)
• Dharmadeep Muppalla (01.04.2008 @09:33:11 AM EST)
• Maxim G. Smith (01.04.2008 @11:04:42 AM EST)
• James Dow Allen (01.04.2008 @01:36:55 PM EST)
• Henry Bottomley (01.04.2008 @01:40:35 PM EST)
• Dion Harmon (01.04.2008 @05:46:52 PM EST)
• Gary M. Gerken (01.05.2008 @07:38:04 AM EST)
• Matt Hickford (01.05.2008 @09:45:15 AM EST)
• Al Zimmermann (01.05.2008 @10:38:43 AM EST)
• Christie Marr (01.05.2008 @12:57:25 PM EST)
• Joseph DeVincentis (01.05.2008 @01:06:11 PM EST)
• Alan Murray (01.05.2008 @04:30:20 PM EST)
• Mithil Ramteke (01.06.2008 @01:56:58 PM EST)
• Jan Musschoot (01.06.2008 @04:03:30 PM EST)
• Ed Shepard ( (01.06.2008 @08:06:09 PM EST))
• Jochen Hoenicke (01.07.2008 @11:25:09 AM EST)
• Samantha Casanova (01.07.2008 @01:53:59 PM EST)
• Ashish Srivasta (01.07.2008 @04:06:02 PM EST)
• Jiri Navratil (01.07.2008 @06:27:13 PM EST)
• Anneke Van Steirteghem (01.08.2008 @10:52:07 AM EST)
• Slawomir Pudlis (01.08.2008 @11:28:53 AM EST)
• Victor Chang (01.08.2008 @02:34:21 PM EST)
• zhouguang (01.08.2008 @10:14:20 PM EST)
• Chris Lomont (01.09.2008 @09:06:46 AM EST)
• Greg Jane (01.09.2008 @01:24:31 PM EST)
• Chris Hills (01.09.2008 @05:28:55 PM EST)
• Phil Muhm (01.09.2008 @10:41:58 PM EST)
• Rubén Hernández Aza (01.09.2008 @10:52:04 PM EST)
• John T. Robinson (01.10.2008 @12:34:40 PM EST)
• Guillermo Ruiz (01.11.2008 @07:13:33 AM EST)
• Andrea Andenna (01.13.2008 @09:55:10 AM EST)
• Ole Martin (01.13.2008 @12:12:58 PM EST)
• Øyvind Grotmol (01.13.2008 @04:21:40 PM EST)
• Ian Smith (01.14.2008 @07:30:57 AM EST)
• Mark Thornquist (01.15.2008 @06:47:20 PM EST)
• Don Dodson (01.16.2008 @04:50:58 PM EST)
• John Stebbins (01.18.2008 @01:25:02 AM EST)
• Peter Chikov (01.18.2008 @11:56:21 AM EST)
• Stephen Merriman (01.18.2008 @08:29:50 PM EST)
• Aleksandar Damnjanovic (01.19.2008 @02:58:51 AM EST)
• Amos Guler (01.20.2008 @03:15:42 AM EST)
• John G. Fletcher (01.20.2008 @04:10:41 PM EST)
• Nathaniel Litton (01.22.2008 @12:33:37 PM EST)
• Volkmar Kobelt (01.23.2008 @10:09:30 AM EST)
• Nyles Heise (01.24.2008 @03:04:44 AM EST)
• Amit Sinha (01.26.2008 @05:31:41 PM EST)
• Chuck Carroll (01.27.2008 @10:35:21 AM EST)
• Arjun R. Acharya (01.27.2008 @07:10:26 PM EST)
• Deepak (01.28.2008 @11:39:07 AM EST)
• Gale Greenlee (01.28.2008 @11:41:13 AM EST)
• Ashutosh Mahajan (01.28.2008 @01:57:05 PM EST)
• Wolf Mosle (01.28.2008 @03:42:02 PM EST)
• David Friedman (01.29.2008 @05:19:03 PM EST)
• Thomas Hähndel (01.29.2008 @07:25:50 PM EST)
• Chris Shannon (01.30.2008 @05:51:37 PM EST)
• Albert Stadler (01.31.2008 @01:59:57 PM EST)
• Michael Liepelt (01.31.2008 @02:51:38 PM EST)
• Danny Walters (02.01.2008 @01:50:51 AM EST)