4 couples, 8 people total, participate in a Secret Santa gift exchange. Call the people A, B, C, D, E, F, G, H. Assume A+B are a married couple. Likewise, assume C+D, E+F, and G+H are all couples. All 8 people put their names on a piece of paper and then the people randomly draw names from the bowl. This time, people are not allowed to draw their own name or their partner's name. If a person draws their own name or their partner's name (an invalid name), they hold onto the paper with that name while drawing a second piece of paper. If the second piece of paper is also invalid then they hold onto that as well and choose a third name. After drawing a valid name, they replace the piece(s) of paper with the invalid name(s). This ensures that nobody draws their own name or their partner's until the last two people are to draw. When there are two people remaining to draw, there are different situations that can occur. Assume that the rules have been followed and everyone who could draw a valid name has done so. If the second to last person could not draw a valid name, that means the last two people are a couple and the last two names in the bowl are their names. So, have the third and fourth to last people redraw randomly from among the last two people's names and have the last two people take those names drawn by those other people (the third and fourth to last). If only the last person cannot draw a valid name, have them switch with the second to last (if the switch makes a valid draw for both people) or third to last, fourth to last, etc. Keep working backwards until the switch can be made so that both people have valid names.
a) Assume they draw in this order: A, B, C, D, E, F, G, H. What is the probability that there is a perfect pairing? A perfect pairing means that whatever name A draws, that person also drew A's name; whatever name B draws. that person also drew B's name, etc.
b) Assume they draw in this order: A, C, E, G, B, D, F, H. What is the probability that there is a perfect pairing?
- 2,140
- 6
- 15
1 Answers
I think this should be fairly straightforward, but my combinatorics is a bit rusty.
There are 8 participants. Assume A goes first. A can not choose themselves and can not choose their partner, leaving 6 possibilities.
B goes next. B can not choose themselves and can not choose their partner. One person that is neither A nor B has been selected. This leaves 5 people to choose from.
This line of argumentation shows that A has possible 6 names, B 5, C 4, D 3, E 2, F 1, leaving G and H's selection determined as you've noted.
The number of ways in which this can happen is $6! = 720$, so there are 720 valid "perfect pairings".
The probability of a perfect pairing given the "can't choose yourself or your spouse" rule is easiest to calculate if we examine instead $1 - \operatorname{Pr}(\mbox{fail to get a perfect pairing})$. Failure can occur in two ways:
The last person can not draw a name because they are the last person in the hat. An example would be the following draw sequence: A chooses C, B chooses D, C chooses E, D chooses F, E chooses G, F chooses A, G chooses B. Here, H is left all alone. There are 5! ways this can happen.
The two names in the hat are the names of couple yet to draw. There are 4! ways this can happen.
The probability of a perfect match should then be $$1 - 4!/6! - 5!/6!$$
- 24,380
- 1
- 36
- 94