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.

Comments

Post a Comment

Popular posts from this blog

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Consecutive Heads

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