A variant of bin-and-ball problem We have $n$ balls, each belonging to a group (e.g, color). There are $g$ groups ($g$ may be large but $g=o(n)$). We sequentially put the balls into $m$ bins in the following way: for each ball, we randomly choose $k$ bins; if there is a bin containing balls of the same group, we put the ball into the bin, otherwise we put the ball into the leftmost empty bin; if we cannot find an appropriate bin for the ball, there is a insertion failure. The question is to find at least how many bins (i.e., the value of $m$) are required so as to achieve a small insertion failure probability.
 A: The problem seems too vague. I don't have sources to draw from but here are some speculations:
I will assume that the groups are the same size. Also that $g$ is fixed and $n$ goes to infinity. And also that the bins that have colors are equally distributed among the colors (or close enough so that the discrepancy doesn't matter). 
In the event that all $m$ bins are colored ahead of time, $g\ln{n}$ seems about right in the sense that if $k=g(\ln{n}+c)$ then the expected number of insertion failures is very close to $e^{-c}.$ That estimate is based on the assumption that the colors of the bins selected are independent. That means $m$ much bigger than $g$. However, if that is not the case, it lowers expected number of failures. 
But to get from $m$ empty bins to all or almost all colored might take some time. My rough (and suspect) calculation for $g=2$  is on the order of $2^{mk}.$ I suppose that for $g=2$ and $m$ fixed, as $n$ goes to infinity this would became paltry compared to  $2{\ln{n}}.$
Of course $k=m$ is surely enough and if we hold $g$ and $m$ fixed and let $n$ go to infinity then eventually $g\ln{n} \gt m.$ Actually $k=\frac{g-1}{g}m+1$ is enough if their are exactly $\frac{m}{g}$ bins of each color.
All this is pretty sketchy. However if it is generally on the right track then perhaps it is possible to extend it to cases such as $m=\ln^2(n)=\ln(\ln{n})$ and $g=\ln^4(n).$
