# how to distribute n red and m blue balls in some containers to maximize probability of random picking a red one from them?

This is an interview question.

Given n red balls and m blue balls and some containers, how would you distribute those balls among the containers such that the probability of picking a red ball is maximized, assuming that the user randomly chooses a container and then randomly picks a ball from that.

My solution:

suppose we have c containers, distribute n/c read balls to each c. If c == 1, put all of them together, it is n/(m+n)

 If c == 2,  put 1 red in c1 and all left red and all blue ones in c2 in this way , we have:
1/2 + 1/2 *(n-1) /(m+n-1) > 1/2

If c == 3,   put a red in c1, put a red in c2, put left red and all blue in c3, we have:
1/3 + 1/3 + 1/3 * (n-2)/(m+n-2) > 2/3

If c == n,  put a red in each of p -1, and all left red and blue in pth container, we have:
( Sum of (1/n) from 1 to n-1 ) +  ( 1/n * 1/(m+1) )
(n-1)/n + 1/n * 1/(m+1) == 1 (almost)


As n is large, the (n-1)/n is very close to 1 so that we maximize the probability to get a red balls.

Any better ideas ?

-
off-topic. Best fit is probably math.stackexchange (NOT mathoverflow.net) –  Jason S Dec 26 '11 at 2:16
They are asking you to implement gerrymandering. Put one red ball in each container, then put all the remaining balls in a single container. –  Raymond Hettinger Dec 26 '11 at 2:17
I wonder what's wrong with : Put one red and one blue into first container, then into 2nd, then into nth, then restart or stop when you run out of any colored balls. –  ScarletAmaranth Dec 26 '11 at 2:17
Are there any constraints to how many balls can/need to go in every container? Can we just put all the blue balls in a single container? –  adi92 Dec 26 '11 at 2:18
I must be missing something. If I have n red and m blue balls, no matter how they are split, if I pick a random ball from a random container, the probability to get a red ball is the same n / n + m –  Mathias Dec 26 '11 at 20:40
show 1 more comment

## migrated from stackoverflow.comMay 3 '12 at 13:38

This question came from our site for professional and enthusiast programmers.