# Throw $n/3$ red balls and $2n/3$ blue balls into k bins. Maximum count of balls in red-majority bins?

Given a set of $n$ balls where $\displaystyle\frac{n}{3}$ balls are blue and $\displaystyle\frac{2n}{3}$ balls are red, we throw each one, at random, into one of $k$ bins with uniform probability. After throwing all $n$ balls, bin $k$ is said to contain $n_k$ balls ($R_k$ being red and $B_k$ being blue).

Define a new variable for each bin, $M_k$, that is $1$ if red balls compose the majority of balls in bin $k$, and $0$ otherwise. Another way to think of this is $M_k = 1$ if bin $k$ has more red balls than blue balls, and $0$ otherwise.

Define $A$ to be the sum of the number of balls in each bin ($n_k$) if $M_k = 1$. i.e: $$A = \sum\limits_{i=0}^k M_i n_i$$

What is the upper bound of $A$?

$$\ldots\ldots\ldots\ldots$$

So far what I have is a hint that a clever solution using Markov's inequality exists, but I'm failing to see it. What I've worked out so far is the following (though perhaps I'm mistaken somewhere): $$\mathop{E}(n_k) = \frac{n}{k}$$ $$\mathop{E}(R_k) = \frac{\mathop{E}(n_k)}{3} = \frac{n}{3k}$$ And I believe the Markov solution follows something along the lines of: $$\mathcal P (R_k > \frac{n_k}{2}) = \frac{2\mathop{E}(R_k)}{n_k} = \frac{2nk}{3kn} = \frac{2}{3}$$ Meaning the final solution I'm getting, using union bound: $$\mathcal P (\bigcup\limits_{i=0}^k(R_k > \frac{n_k}{2})) = k\frac{2}{3}$$ In other words...this should be the maximum value of $A$...

Which doesn't entirely make sense to me. So I ask you, stackexchange...Am I heading down the right path? Have I overlooked something extremely important? Or am I completely lost? Any help on the matter would be greatly appreciated.

-
Your last step can’t possibly be right: for $k>1$ it gives you a probability greater than $1$. – Brian M. Scott Nov 20 '12 at 6:22

## 1 Answer

If you want upper bounds, you should ignore expectation values. The upper bound on $A$ is $n$. Just put all the balls in one bin. Or just group the balls into batches of 2 red and 1 blue and put each batch into any bin. All the balls will be in bins with a clear majority of red. There are more configurations that achieve this limit. If there aren't too many bins, most configurations will have $A=n$.

-