An office of twenty people decides to engage in a holiday ‘Secret Santa’ assignment. Each staff member purchases a dozen small gifts. Each employee distributes their gifts to other members of the office, making sure each recipient, at most, receives one gift from them (meaning staffers get one, or no gifts, from any individual giver; nobody gets more than one gift from any single person). Also, people do not gift to themselves!
Prove that there must be occurrences where a pair of employees mutually exchange gifts with each other.
Show Solution
Solution
Because there are twenty people in the office, and each person has purchased a dozen gifts, there are a total of 240 gifts flying around.
Next, we need to calculate the number of possible pairs. With twenty employees, there are 20C2 possible distinct pairs, which is (20 × 19) ÷ 2 = 190.
From the pigeonhole principle, there are more gifts given (240) than distinct pairs (190), so some distinct pairs will get more than one gift (in fact, at least 50 such pairs).
Happy New Year to all my readers!