Ponder This Challenge - July 2012 - Coloring balls games

Ponder This Challenge:

Alice and Bob are playing two games: they start simultaneously and the first one to win his game is the winner.

Alice is given an urn with N balls, colored in N different colors and in every second she randomly picks two balls, colors the first ball in the color of the second ball and returns both to the urn.

Her game is over once all the balls in the urn have the same color.

Bob is given an urn with M balls, all colorless, and in every second he picks a random ball, color it, and puts it back to the urn. Bob's game is over once all his balls are colored.

Our question is: what are the possible values of M for which (on average) Bob is expected to lose for N=80 and win for N=81?

Update 7/4: Alice picks two different random balls in and can not change their order: it colors the first in the color of the second. Bob can be color-blind: all he cares is whether a ball is colored or not; if he takes out a colored ball - he colors it again and continue. Both Bob and Alice finish their task each second.

Update 7/9: We ask for possible Ms for which the expected time of Bob's game is smaller than Alice's expected time for N=81 and greater for N=80.

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

  Alice's expected game time is (n-1)**2, as you can read in the paper "A Colorful Urn" (PDF, 82KB)

  Bob's game is the famous coupon collector problem: http://en.wikipedia.org/wiki/Coupon_collector%27s_problem.

  Solving the equation for the expected value gives us 852 <= m <= 871.

  We don't have an elegant solution for the more difficult version of this problem (as it was phrased before the update), which asked when Bob is expected to win, rather than when his expected value is smaller than Alice's. A simulation gives the answer as 764 <= m <= 780.

Solvers

• Dan Dima (06/28/2012 07:10 PM EDT)
• Hrushikesh Tilak (06/28/2012 10:34 PM EDT)
• Shilei Zang (06/30/2012 10:08 AM EDT)
• John Snyder (06/30/2012 12:07 PM EDT)
• Lorenzo gianferrari pini & Radu-Alexandru Todor (06/30/2012 06:34 PM EDT)
• Duane Bailey (06/30/2012 10:59 PM EDT)
• Anoop Ghanwani (07/01/2012 03:23 AM EDT)
• Peter Gerritson (07/01/2012 10:59 AM EDT)
• Mark Pervovskiy (07/01/2012 11:31 AM EDT)
• Ritobroto Maitra (07/01/2012 04:43 PM EDT)
• Wu Chengyuan (07/02/2012 07:26 AM EDT)
• Joshua Small (07/02/2012 11:00 AM EDT)
• Yury X Volvovskiy (07/02/2012 04:50 PM EDT)
• Armin Krauss (07/03/2012 03:41 PM EDT)
• William Heller (07/03/2012 07:33 PM EDT)
• Allen Sirolly (07/03/2012 11:50 PM EDT)
• Henri Gonin (07/04/2012 02:14 AM EDT)
• Lewei Weng (07/04/2012 06:15 AM EDT)
• Hamidreza Bidar (07/04/2012 07:47 AM EDT)
• Yueru Sun (07/04/2012 12:56 PM EDT)
• Øyvind Grotmol (07/05/2012 06:21 AM EDT)
• Eric Farmer (07/05/2012 10:56 AM EDT)
• Liubing Yu (07/12/2012 12:36 AM EDT)
• Albert Stadler (07/13/2012 08:27 AM EDT)
• Don Dodson (07/13/2012 05:43 PM EDT)
• Phil Benamy (07/14/2012 10:33 AM EDT)
• Kenneth Meehan (07/17/2012 09:27 PM EDT)
• David Korsnack (07/18/2012 04:02 PM EDT)
• Adrian Orzepowski (07/19/2012 05:36 PM EDT)
• Pratik Poddar (07/19/2012 07:14:35 PM EDT)
• Denys Kopiychenko (07/23/2012 10:18 AM EDT)
• Peter Derivaz (07/23/2012 03:07 PM EDT)
• Hari MP (07/24/2012 02:34 AM EDT)
• Andrea Andenna (07/24/2012 04:26 PM EDT)
• Kevin Sham (07/24/2012 10:39 PM EDT)
• Frederik Kaster (07/25/2012 04:29 AM EDT)
• Sergey Grishaev (07/25/2012 06:28 AM EDT)
• Hakan Summakoglu (07/25/2012 09:52 AM EDT)
• Daniel Bitin (07/25/2012 11:33 AM EDT)
• Nyles Heise (07/25/2012 01:05 PM EDT)
• Stéphane Higueret (07/26/2012 03:52 AM EDT)
• Christian Pape & Markus Boettle (07/26/2012 11:45 AM EDT)
• Shouky Dan & Tamir Ganor (07/27/2012 09:41 AM EDT)
• Janos Csorba (07/27/2012 09:59 AM EDT)
• James Aaronson (07/27/2012 10:30 AM EDT)
• Hannes Schenck & Matthias Herzkamp (07/27/2012 12:32 PM EDT)
• Christian Blatter (07/29/2012 06:00 AM EDT)
• Erik Hostens (07/30/2012 04:00 AM EDT)
• Dan Arnon (07/30/2012 02:59 PM EDT)
• Shiv Shankar (07/30/2012 05:39 PM EDT)
• Siddharth S (07/31/2012 02:14 AM EDT)
• Tony Harrison (07/31/2012 10:39 AM EDT)
• Ilya Khivrich (07/31/2012 04:11 PM EDT)
• Six people correctly solved a harder version of the question, before the update: (None)
• Deane Stewart (06/28/2012 05:42 PM EDT)
• Deron Stewart (06/28/2012 07:27 PM EDT)
• Simon Xu (06/28/2012 11:41 PM EDT)
• Adrian Orzepowski (06/29/2012 01:23 PM EDT)
• Peter de Rivaz (07/03/2012 04:03 PM EDT)
• Hakan Summakoglu (07/04/2012 12:12 PM EDT)