At a party each man dances with 4 women and each woman dances with 3 men. If 9 men attended the party, how many women attended the party?
I have no idea how to approach this problem.
[Math] At a party each man dances with 4 women and each woman dances with 3 men. If 9 men attended the party, how many women attended the party
combinatorics
Related Solutions
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$.
Let's say that the positions are numbered like this:
$1|2|3|4$
$5|6|7|8$
That means that the seat $5$ is opposite of seat $1$, seat $6$ is opposite of seat $2$, etc.
You can chose between $8$ people for whom to put in seat number $1$.
After this, you can chose between $4$ people for whom to put opposite of seat number $1$(that is in seat number $5$).
Next you can chose between $6$ people for whom to put in seat number $2$, and then you can chose between $3$ people to put in seat number $6$
Continuing this way we can find that there are $8*4*6*3*4*2*2*1$ ways to arrange the people the way you want.
Best Answer
If you assume that a man dances with a woman, how many dances will be performed?
9 men -> dance 9 * 4 times with a woman, so 36 dances
Each woman performs 3 dances, so 12 women.