solution

Bài toán sinh nhật (birthday problem) kinh điển hỏi xác suất ít nhất hai người trong nhóm có cùng ngày sinh (trong năm có $365$ ngày). Ở đây ta xét bản tổng quát: có $n$ người, mỗi người được gán ngẫu nhiên, độc lập và đồng khả năng vào một trong $m$ "nhóm" (có thể hiểu là $m$ ngày trong năm, hoặc $m$ hộp bất kỳ). Hãy tính xác suất $P$ để có ít nhất hai người rơi vào cùng một nhóm.

Nếu $n > m$, theo nguyên lý chuồng bồ câu, chắc chắn có ít nhất hai người trùng nhóm nên $P = 1$.

Nếu $n \le m$, xác suất không có ai trùng nhóm là $P(\text{không trùng}) = \dfrac{m(m-1)(m-2)\cdots(m-n+1)}{m^n}$, do đó $P = 1 - P(\text{không trùng})$.

Ví dụ: $n=2, m=2$: $P(\text{không trùng}) = \dfrac{2\cdot 1}{4} = 1/2$, vậy $P = 1/2$.