I come from a CS background and had to contend with a problem similar to this one. Essentially, I want a general-case estimate on how many rolls I'd have to make to land on the same number twice with a (fair) $k$-sided die.
I got as far as this for an expected value:
$$\displaystyle \sum_{n=1}^{k}\frac{(k-1)!\cdot n^2}{(k-n)!\cdot k^n}$$
and managed to simplify it to this cute looking guy:
$$\displaystyle \sum_{n=1}^{k}\frac{\binom{k-1}{n-1}\cdot n!\cdot n}{k^n}$$
But here, i have no idea how to proceed, I'd do with a simple asymptotic approximation but I got nothing. Through computer simulation, I found this very close to $\sqrt{k}$ as far as $k=10^{10}$ but I can't really prove it, any help would be appreciated.
Hint: Look up the birthday paradox problem and calculations related to it. Your empirical observation that it has something to do with $\sqrt{k}$ is right on the money.