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.
