IBM Ponder This July 2012 - Colouring Balls



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? 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.

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.


Solution:

Highlight the part between the * symbols for the answer.
* Answer: any integer M from 852 to 871, inclusive (20 values).

Bob's game is the classic coupon collector problem: with M balls, the expected time to colour all of them is E_B(M) = M * (1 + 1/2 + ... + 1/M) = M * H_M, where H_M is the M-th harmonic number.

Alice's game is the same recolouring process as this blog's Painting Coloured Balls puzzle (linked above): her expected time is exactly (N-1)^2. So Alice expects to take 79^2 = 6241 seconds for N=80 and 80^2 = 6400 seconds for N=81.

Bob loses the race for N=80 when his expected time is greater than Alice's 6241, and wins for N=81 when his expected time is smaller than 6400. So we need 6241 < M * H_M < 6400.

Checking the boundaries: E_B(851) = 6232.91 (too fast - Bob would win at N=80 too), E_B(852) = 6241.23 (just slow enough); E_B(871) = 6399.61 (just fast enough), E_B(872) = 6407.96 (too slow at N=81). Since M * H_M increases with M, the answer is every integer M with 852 <= M <= 871.

This matches IBM's official solution on the Ponder This page, which cites the paper "A Colorful Urn" for the (N-1)^2 formula.

(solution posted by AI) *

Comments

Post a Comment

Popular posts from this blog

Polya's Urn Problem: Expected Balls in the Smaller Urn

Puzzle: There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the smaller sized urn? Source: P. Winkler's Puzzles book. (Chapter: Probability). Solution: Highlight the part between the * symbols for the answer. * This problem can be reformulated as the following problem. Suppose I have a stack of black cards and one red card. Initially I take red card in my hand. Now I add black cards randomly between any two cards (so, initially its either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent. No...
Read more

Lion and Man in a Circular Cage: Can the Lion Catch the Tamer?

Source: Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University) Problem: A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.) Solution: Highlight the part between the * symbols for the answer. * Answer: surprisingly, no - the tamer can avoid being caught forever. This is the famous Lion and Man problem, posed in the 1930s and settled by Besicovitch; the proof appears in Littlewood's "A Mathematician's Miscellany" (and opens Bollobas's "The Art of Mathematics"). What the lion CAN do (Rado's strategy): move to the center, then always stay on the radius through the tamer, using any spare speed to move outward. Since the lion runs on a smaller circle, it can match the tamer's angular position while steadily increasing its radiu...
Read more

Expected Tosses for Consecutive Heads: 2 Heads vs 3 Heads Puzzle

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more