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.

  • 4
    $\begingroup$ This doesn't sound like a very good dance party at all. $\endgroup$ – Servaes Oct 10 '16 at 21:04
  • $\begingroup$ Why the downvotes? It's actually a not bad question. L = 20 is definitely a upper bound because having a list of 20 women of 20 women actually means that every man can pair with every woman. L = 1 is definitely too low because if every man chooses just one woman then there have to be at least two men that chose the same woman and every group of 20 men that contains those two men is then in trouble. $\endgroup$ – Jeyekomon Oct 10 '16 at 21:32
  • $\begingroup$ My book gives the hint: First show that there is a way to choose the dance lists that works with 1620 (=20+80*20) . Then show, by using an averaging argument to show that there is no arrangement with a sum of 1619 that works. $\endgroup$ – Justin Stevenson Oct 10 '16 at 22:16
  • $\begingroup$ The hint would suggest that if $80$ men each have $20$ women on their lists, and the remaining $20$ men each have $1$ woman on their lists, then you can do the pairing. This is not true, though - what if you choose the $20$ men who each have $1$ woman on their list and they've all chosen the same woman? Perhaps I'm misunderstanding the problem. $\endgroup$ – kccu Oct 10 '16 at 22:25
  • $\begingroup$ Yeah same i'm having trouble fully understanding what the problem was asking. $\endgroup$ – Justin Stevenson Oct 10 '16 at 23:55

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$.


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.