Our teacher assigned this problem to our class as a challenge and I was able to do some of it but got stuck. Here it is:

A company with n employees has a scheme according to which each employee buys a Christmas gift and the gifts are then distributed at random to the employees. What is the probability that someone gets his or her own gift?

So far, I found that the probability that an employee gets his or her own gift is $\frac 1 n$. Additionally, we can let $A_i$ equal the $ith$ employee that gets his or her own gift. This is now what we are trying to find:

$$P\bigcup_{i=1}^{n} A_i$$

So, we have:

$$P(A_i) = \frac 1 n$$ $$P(A_i \cup A_j) = \frac{n-2!}{n!} = \frac{1}{n(n-1)}$$

Thus, we can deduce:

$$P(A_1 \cup \cdots \cup A_n) = \frac{1}{n!}$$

Using this, I start deducing the answer:

$$1 - \frac{1}{2!} + \frac{1}{3!} + \cdots + (-1)^{n-1} \frac{1}{n!}$$

After this step, I am unsure on how to proceed and simplify my work. Also, can someone tell me if I worked out the proof accurately?

  • $\begingroup$ This is very close to the derangement problem, which asks what the problem is that no one gets their own gift (or their own hat, or whatever). The answer to both the derangement problem and your problem, in the limit as $n \to \infty$, is $1/e$, and you're almost all of the way there. You need only the Taylor-series expansion of $e^x = 1 + x/1! + x^2/2! + x^3/3! + \cdots$, where $x = -1$ in your case. $\endgroup$ – Brian Tung Apr 9 '15 at 22:12
  • $\begingroup$ You are working it correctly, and your answer converges to $1-\frac{1}{e}$ as $n\to\infty$ using the Taylor series for $f(x)=e^x$ with $x=-1$. $\endgroup$ – user84413 Apr 10 '15 at 0:40

Your answer is correct. The probability is approximately $$e^{-1}$$ being the first $n$ terms for the Taylor series for $e^x$ evaluated at $x=-1.$

| cite | improve this answer | |

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.