Wednesday, December 20, 2006

Gift Exchange Combinatorics

Well, I'm about to head to a holiday party. But, before I do that I just wanted to share a quick story with all of you.

So, our company promoted a holiday gift exchange recently, and a total of 19 people participated. Anyway, each person brought a gift and then each person was given one of the gifts randomly. There was nothing in place to ensure that people wouldn't be given their own gifts, and what happened was 4 of the 19 participants got their own gifts back. Pretty strange, and so I got a bit curious about the probability of such an occurrence.

I had to go back to some old math books that I haven't touched in a while and read up a bit on the inclusion-exclusion principle, but after some time, I was able to get the answer I sought. Just to double-check, I programmed up a quick Monte Carlo simulation, which pretty much corroborated the answer. After more digging, I learned that there's something interesting about this problem, which turns out to be a classic one. It seems that this problem is closely tied to the natural number, e, which I thought was really neat.

Anyway, the chance that exactly 4 of 19 people receive their own gifts is 1.53%. The chance that 4 or more people receive their own gifts is 1.90%.

No comments: