Secret Santa

Since $p$ is the probability that someone receives their own gift, $1-p$ is the probability that nobody receives their own gift. This is known as a derangement , a permutation of elements where no element ends up in their original position. If we interpret the gifts as elements as the people as positions, where an element is in its original position if the gift was one's own gift, the fact that this is a derangement is clear.

I won't prove it here, but there is a very interesting formula for the number of derangements: the number of derangements of $n$ elements is the integer closest to $\frac{n!}{e}$ . (This can be derived from the formula $n! \sum_{i=1}^n \frac{(-1)^i}{i!}$ by taking the power series of $e^x$ , which in turn is derived by PIE.) Since $n$ is very big, we can effectively treat the number as $\frac{n!}{e}$ ; the loss of accuracy is insignificant. The number of permutations overall is $n!$ , so the probability that nobody receives their own gift is simply $\frac{n!/e}{n!}$ , the probability that we pick a derangement out of all possible permutations. This simplifies to $\frac{1}{e}$ , no matter the value of $n$ (as long as it's large enough).

Finally, we have $1-p = \frac{1}{e}$ , so $p = 1 - \frac{1}{e}$ . Using calculator, we can compute that $p = 0.63212 \ldots$ , so $\lfloor 10000p \rfloor = \boxed{6321}$ .

Let there are $n$ persons who will participate in this game.

So number of ways thay can not receive their own gifts is $\displaystyle n! \sum_{r=0}^{n} \dfrac{(-1)^r}{r!}$

Number of ways one person can take any gifts from $n$ gifts is $n!$ .

So $p$ is the probability that on can not receive their own gifts is $p=\dfrac{n! \sum_{r=0}^{n} \dfrac{(-1)^r}{r!}}{n!}$

$p=\sum_{r=0}^{n} \dfrac{(-1)^r}{r!}$

So, probability that one person receive their own fifts is $p'=1-p=1 -\sum_{r=0}^{n} \dfrac{(-1)^r}{r!}=1-\frac{1}{e}=0.63208$