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.