A group of $n>4$ people gathers for a feast. Each person brings $n$ dishes of his/her own unique stew. Then, each person forms his/her own menu by choosing 4 distinct dishes (of different stews), randomly and independently of any of the other people. What is the probability that at least two people chose the exact same menu?

What I got so far is since the probability for a person to choose a specific menu is $p=\frac{1}{n \choose 4}$, if $X$ is the random variable of the number of people choosing "that" menu, then $\Pr(X\geq 2)=\sum_{k=2}^{n} {n \choose k}p^k(1-p)^{n-k}\\$, but even after simplyfing this expression it doesn't resemble any of the answers (it's a multiple choice).

So I could really use some guidance here.


There are $N=\binom n4$ possible possibilities for a menu, and there are enough dishes of each type so that the persons are free to choose. So the problem can be restated, and let us better ask for the complementary probability:

$n$ persons choose in the same time, independently one of $N$ menus, that exist in overflow. Which is the probability for $n$ different choices?

The answer is $$ \frac1{N^n}\cdot (N-0)(N-1)\dots(N-(n-1)) = \left(1-\frac 1N\right) \left(1-\frac 2N\right) \dots \left(1-\frac {n-1}N\right) \ . $$ The complement is the answer to the OP $$ 1-\left(1-\frac 1N\right) \left(1-\frac 2N\right) \dots \left(1-\frac {n-1}N\right)\ ,\qquad N = \binom n4=\frac 1{24}n(n-1)(n-2)(n-3) \ . $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.