2
$\begingroup$

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 ?

  • 0
    off-topic. Best fit is probably math.stackexchange (NOT mathoverflow.net)2011-12-26
  • 0
    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.2011-12-26
  • 1
    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?2011-12-26
  • 0
    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 + m2011-12-26
  • 2
    They are asking you to implement [gerrymandering](http://en.wikipedia.org/wiki/Gerrymandering). Put one red ball in each container, then put all the remaining balls in a single container.2011-12-26

2 Answers 2