Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question

migrated from stackoverflow.com May 3 '12 at 13:38

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

    
off-topic. Best fit is probably math.stackexchange (NOT mathoverflow.net) –  Jason S Dec 26 '11 at 2:16
2  
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
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? –  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

2 Answers 2

Copied from Raymond Hettinger's comment just so we have an answer

They are asking you to implement gerrymandering. Put one red ball in each container, then put all the remaining balls in a single container.

share|improve this answer

I know this thread is pretty old, but I just ran across the question and spent some time looking into it. One possible problem is that I may have misinterpreted the question: when it says you have "some containers", does that mean you get to pick how many containers you're going to use, or is the number of containers $C$ fixed beforehand (so that you must put at least one ball in each of those containers)? I interpreted it the former way, which may not be how the question was intended, but it led to some interesting results.

As has been said a few times, the best solution involves all but one of the containers having just one red ball. The remaining container has all of the blue balls, and maybe some red balls and maybe not. What I think is the best solution, although I haven't proven it:

If $n <= m$, then it's best to have $n + 1$ containers, with $n$ containers containing one red ball each and the rest containing only blue balls.

If $n > m$, it works out best to have a container with at least one red ball and all the blue balls. The best number of red balls in that last container seems to be $k = \lfloor(n - m + 1)/2\rfloor$, so that the number of containers is $n + 1 - k$. (If $n - m$ is even, then choosing $k = \lfloor(n - m)/2\rfloor$ and $k = \lfloor1 + (n - m)/2\rfloor$ result in the same probability; I've convinced myself of that.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.