Colored balls and bins -- asymptotic behavior Suppose I have $N$ bins and a set of balls with $m$ different colors, where there are $n_i$ balls of color $i$.  I also have values $0 < p_i \leq 1$ for all colors $i$.  I throw all $\sum_i n_i$ balls into bins uniformly at random and then I want the set of bins of smallest cardinality, such that I have at least $p_i n_i$ balls of each color $i$.  Is the asymptotic behavior of (the distribution of the cardinality of the smallest set), in the limit as $N\to\infty$ and $n_i\to\infty$, well understood?  Specifically, let's say that they all scale at the same rate so that $N = N_0 t$ and $n_i = n_i^0 t$ for fixed $N_0, n_i^0$ and we're letting $t\to\infty$.
 A: Here's an informal pointer towards an answer. The number of bins required should grow linearly with $N$, with the rate given by an optimisation problem involving Poisson probabilities.
As $N\to\infty$ in your model, the distribution of balls in bins becomes very close to a collection of independent Poisson random variables: the answer to the question should be nearly the same as if each bin had a number of balls of colour $i$ with Poisson($\lambda_i$) distribution where $\lambda_i=n_i^0/N_0$, independently between different colours and different bins. 
Let's say a bin has type $\mathbf{a}=(a_1, \dots, a_m)$ if it has $a_i$ balls of colour $i$ for $1\leq i\leq m$. In the Poisson model, the probability that a bin has type $\mathbf{a}$ is
$$
p(\mathbf{a}):= \frac{\lambda_1^{a_1} e^{-\lambda_1}}{a_1!}
\dots
\frac{\lambda_m^{a_m} e^{-\lambda_m}}{a_m!}.
$$
Consider the strategy of taking all bins whose type is in some given set $A\subset\mathbb{N}^m$. This strategy is likely to be "succesful" (in the sense of taking at least $p_i\lambda_i N$ balls of each colour) if for each $i=1,\dots,m$, 
$$
\sum_{\mathbf{a}\in A} a_i p(\mathbf{a}) > p_i \lambda_i.
$$
Also, the number of bins taken will be roughly $Np(A)$ where $p(A):=\sum_{\mathbf{a}\in A} p(\mathbf{a})$.
This suggests the optimisation problem
$$
p^*=\min_{\textstyle A: \sum_{\mathbf{a}\in A} a_i p(\mathbf{a}) > p_i\lambda_i \text{ for each }i}
p(A).
$$
The claim is that (to first order) the number of bins required behaves like $p^*N$. Clearly the optimising $A$ will be an increasing set (in the sense that if $\mathbf{a}\in A$ and $\mathbf{b}\geq\mathbf{a}$ componentwise, then also 
$\mathbf{b}\in A$).
It should be relatively straightforward to show that this is an upper bound, just by considering strategies of the form described above. 
I'm confident that this is also a lower bound, but a rigorous proof of that might need more care since you need to justify that the random fluctuations are not helping you much in the long run. Some sort of concentration argument for the number of bins of each type could be the way to go. 
EDITED: I think this is correct in spirit, but there is at least one subtlety that I missed, so that it (mostly) gives the wrong answer. Consider the case $m=1$. Then the strategies that I considered above are of the form "take every bin which contains at least $K$ balls", and I asserted that one of these would be optimal. However (except for cases where $\lambda_1$ and $p_1$ are carefully chosen) in fact there are better strategies of the form "take every bin that contains more than $K$ balls, and some proportion $\alpha$ of the bins that contain precisely $K$ balls". Extending to the case of multiple colours, we need to allow weights between $0$ and $1$ for types in the boundary of the set $A$ described above. Although the behaviour should be similar, it will make a more complicated optimisation problem than the one I originally claimed.
