Question: You have 50 red marbles, 50 blue marbles and 2 jars. One of the jars is chosen at random and then one marble will be chosen from that jar at random. How would you maximize the chance of drawing a red marble? What is the probability of doing so? All 100 marbles should be placed in the jars.
Answer: Seems tricky at first right? Given that the number of red and blue marbles are the same, you would tend to think that the odds are 50-50. You would try different combinations, such as 25 of each colored marble in a jar or putting all red marbles in one jar and all the blue in the other. You would still end up with a chance of 50%.
So lets think of a better way to distribute the marbles. What if you put a single red marble in one jar and the rest of the marbles in the other jar? This way, you are guaranteed at least a 50% chance of getting a red marble (since one marble picked at random, doesn’t leave any room for choice). Now that you have 49 red marbles left in the other jar, you have a nearly even chance of picking a red marble (49 out of 99).
So let’s calculate the total probability.
P( red marble ) = P( Jar 1 ) * P( red marble in Jar 1 ) + P( Jar 2 ) * P( red marble in Jar 2 )
P( red marble ) = 0.5 * 1 + 0.5 * 49/99
P( red marble ) = 0.7474
Thus, we end up with ~75% chance of picking a red marble.
Have a better solution? Let us know through the comments section!
If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:
I agree, I put 1 marble in 1 jar. 49 marbles in the other. The Blue in the trash. The probability is 1.
I also came up with this answer intuitively. It’s a good solution but this definitely isn’t a proof it’s the best possible solution.
In order to prove this seems pretty complicated though.
This is what I did:
r1 is the number of red marbles in jar 1
b1 is the number of blue marbles in jar 1
we know r2 = 50-r1
and b2 = 50-b1
then by the regular conditional probability rules:
P(picking red) = 1/2 * r1/(b1+r1) + 1/2 * ((50-r1)/(100-b1-r1))
if we let x, y = r1, b1 respectively and we know they lie in a range of [0…50].
then z = P(picking red)
The equation for the probability is now:
def f(x,y):
return 1/2 * x/(y+x) + 1/2 * ((50-x)/(100-y-x));
plotting that in 3d shows you that there are indeed 2 maxima close to 0.75.
I used sage to do this, and used the ranges 0…49 and 1…50 since there are discontinuities when you divide by zero.
P = plot3d(f,(0,49),(1,50), adaptive=True, color=rainbow(60, ‘rgbtuple’));
here’s a pic:
http://bit.ly/qLHLuY
Now to we need to use calculus to prove that the maxima are inded global maxima and not local maxima. We can find them using the method of gradient descent/ascent. Where the path of greatest ascent/descent on the curve has a tangent vector at any point that coincides with the gradient vector at that point.
GRAD_V = d/dx([f(x,y)])*i + d/dy(f[x,y])*j
(i and j are the unit vectors along x and y.)
ie. its partial derivatives with respect to x and y must coincide with the above.
So thats as far as I got, I know that the method of gradient ascent/descent isn’t guaranteed to converge to global maxima/minima it might get stuck and local maxima/minima. But I think we can get around this by finding roots and using the second derivative test / etc.
Not 100% sure about that part though.
There must an easier way to prove this else why would they ask it? I mean otherwise you’re just submitting a clever hunch as your solution.
Let me know what you think.
Or if you can prove that they are global maxima/minima without waving your hands in the air.
Cheers.
Damn! I came across this questions, and took a very long time to answer (with some hints from teh interviewer!)
wish I discovered this blog on the day it started! 🙂
it’ a bit of trick question. it depends on how many times a marble is getting drawn.
I could physically feel mind mind wrench when I read this beautiful solution. Awesome!
Hey John, smart answer but it clears says in the problem that “All 100 marbles should be placed in the jars”. I guess you have to think again now 🙂
I believe this is the best result we can achieve
I would put one red marble in jar 1, 49 red marbles in jar 2, and the blue marbles in the trash. The probability of picking a red marble is now 1.
I don’t see anything in the problem statement that prevents this, so I win.