IBM Ponder This #171 · July 2012

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.

Solution

Best opened after a real attempt

To be added.