IBM Research Ponder This: July 2012 Puzzle

I like this month’s IBM Research puzzle for several reasons.  First, it is really three puzzles in one, where each component is relatively self-contained.  Second, it has some very “nice” elegant mathematics in it, but will also yield to computer simulation… up to a point.  And third… I think it is hard.

Problem: 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?

The three pieces of the puzzle are to: (1) analyze Alice’s game, (2) analyze Bob’s game, and then (3) compare the two.  I think the original intent of the problem was that Alice’s game should be the really “interesting” part.  Consider computing the expected number of seconds for each player to finish.  Bob’s game is a rather standard problem in thin disguise. Alice’s game, on the other hand, requires a bit more work.

However, it is that part (3) of the puzzle that motivated this post.  I think a key question is, what is meant by “Bob losing on average“?  More precisely, once Alice and Bob have completed their games, what does the winner win?  There are two reasonable possibilities:

  1. The loser pays the winner a dollar for every additional second needed to finish the (loser’s) game.
  2. The loser pays the winner a dollar.

An update to the problem in response to this question confirms, as I suspected, that (1) is actually the intended interpretation.  Good thing, too, because in that case the problem essentially reduces to simply finding the expected number of seconds for Alice to finish.  But it seems to me that the original problem, as written, implies (2), which I think makes the problem much harder… or at least, much harder for me.

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s