I was thinking this morning about the well-known Birthday Problem. (This is nothing to do with Markov Chains.) The Wikipedia article discusses a large number of interesting generalizations$^\dagger$, but it does not seem to cover the following.
How many students do we need in a lecture so that it is more likely than not that at least $k$ of them share the same birthday?
It is well-known that 23 suffices when $k=2$. But what about $k=3$ or $4$?
$\dagger\ $ I enjoyed reading this. Suppose $X_1,\ldots,X_n$ are i.i.d. random variables uniformly distributed on the integers from 1 to 1 million. How large must $n$ be so that with probability exceeding $1/2$ there exists a set $S\subset\{1,\dotsc,n\}$ such that the two sums $\sum_{i\in S}X_i$ and $\sum_{i\not \in S}X_i$ are equal, (or differ by no more than 1 in the case that $\sum_i X_i$ is odd)?
Apparently the correct answer is surprisingly small, $n=23$.
