Say you have $m$ boxes each of which is colored with one of $n$ colors. What should $m$ be so that the probability that there is atleast $k$ boxes with one same color is strictly greater than $\frac{1}{2}$?
If $k = \Theta(n^{c})$, then what is $m$ if $c < 1$, $c > 1$? Is $m = \Omega(n^{c+1})$ in general?
I was trying to generalize birthday paradox problem. By Pigeon hole I can get only $m=\Omega(n^{2})$ if $k=O(n)$ for 'certainty'. Using pigeon hole I cannot give a probabilistic argument here. Was curious for general sizes of $m$, $n$ and $k$ and what would replace pigeon hole?
http://www.math.ucsd.edu/~tkemp/180A/180A.LectureNotes.pdf says answer for $n=365$ and general $k$ was not known till $1995$ but does not provide reference.
In this problem, there are two cases: $k < n$ and $k > n$.