At a dance party there are 100 men and 20 women. Each man selects a group of women as potential dance partners, but in such a way that given any group of 20 men it is always possible to pair 20 men with 20 women, with each man paired with someone on their list. What is the smallest number L where L is the sum of the total number of women on each mans list that will guarantee this.
[Math] Dance party with 100 men and 20 women
combinatorics
Best Answer
I came here to verify my solution to this problem, exercise 20 from chapter 2 of the fourth edition of Introductory Combinatorics by Richard A. Brualdi.
My solution: 1981
Problem text: "At a dance-hop there are $100$ men and $20$ women. For each $i$ from $1, 2, \ldots, 100$, the $i$th man selects a group of $a_i$ women as potential dance partners (his dance list), but in such a way that given any group of $20$ men, it is always possible to pair the $20$ men up with the $20$ women with each man paired up with a woman on his dance list. What is the smallest sum $a_1 + a_2 + \cdots + a_{100}$ that will guarantee this?"
Clarification: In order for the problem to make sense, we assume $1 \leq a_i \leq 20$ for each $i$.
Pedantic nitpicking: First, we have to establish that, if $n > 100$ does not guarantee this, then no number $100 \leq m < n$ can guarantee this. Suppose $n$ does not guarantee this. Then, there is a choice of lists such that, for some group of $20$ men, it is not possible to pair each man up with a partner from his list. Now, since $n > 100$, then some list must contain at least two names. If we strike out one of the names from the list, we now have a sum of $n-1$ total names. If this configuration were valid, then the pairing chosen would be valid for the original configuration, so $n-1$ does not guarantee a pairing.
Argument: First, we show that $1980$ does not guarantee the condition. Let $a_i = 20$ for $1 \leq i \leq 80$, and $a_i = 19$ for $81 \leq i \leq 100$. If the $20$ men with $19$ women on their lists are chosen, and each list is the same, then those $20$ men cannot each be paired up with a woman from their list, so $1980 = 80 \cdot 20 + 20 \cdot 19$ does not work.
Now, we prove that $1981$ guarantees the condition. Choose any configuration of lists of names with sum of lengths equal to $1981$. Consider any $k \leq 19$ lists with less than $20$ women on the list. The total number of women referenced by the lists is at least $20 - \lfloor 19/k \rfloor$, since a name has to be struck off $k$ lists to lose a reference, and there are at most $19$ missing names. By Hall's Marriage Theorem, there is a matching if $20 - \lfloor 19/k \rfloor \geq k$, but this clearly holds for all $1 \leq k \leq 19$.