4
$\begingroup$

There are 40 men and 40 women. In how many ways can you pick a board of 31 people that has a majority of women?
I was thinking - let's start with the women. There are $\binom{40}{16}$ ways to pick 16 women (so that there will be more women than men), and then I just need to choose the other 15 people out of all the rest - $\binom{64}{15}$... So I thought the answer would be : $\binom{40}{16}\cdot\binom{64}{15}$
but apparently it's incorrect...
Why? And why is the correct answer $\frac{1}{2}\cdot\binom{80}{31}$?

$\endgroup$

marked as duplicate by N. F. Taussig, Silvia Ghinassi, SchrodingersCat, Alex M., wythagoras Jan 29 '16 at 18:53

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ You're overcounting the solutions that have more than 16 women in them, because your way of counting distinguishes the 16 first-picked women. For example a board with 17 women will be counted 17 times with different women counting as the at-large member. $\endgroup$ – Henning Makholm Jan 29 '16 at 16:21
  • $\begingroup$ I didn't even notice... Thanks! $\endgroup$ – Lisa Jan 29 '16 at 16:32
6
$\begingroup$

Since the number of men and women is the same, and $31$ is odd, of all the $\dbinom{80}{31}$ choices of $31$ people out of $80$, exactly half will have a majority of men, and half a majority of women.


Addendum With your estimate, you are overcounting. To consider a simpler case, suppose you have just three women $W_{i}$ and three men $M_{i}$, and have to select three persons so that women have the majority. Then you are counting the choice $W_{1}, W_{2}, W_{3}$ three times.

$\endgroup$
2
$\begingroup$

We can make use of the symmetry here: Assume for simplicity that the 40 men and 40 women are in fact 40 married couples. In any subset of 31 people, there will either be a majority of women or a majority of men (there cannot be a tie because 31 is odd). Now if for any subset we perform the operation "replace everybody with their spouse" we always turn a men-majority set into a women-majority set and vice versa. And doing the replacement twice always takes us back to the set we started with. Therefore the men-majority and the women-majority sets of size 31 are in bijection with each other, hence of equal size, so ech makes half the size of the totally possible $40\choose 31$ subsets of size 31.

The reason why your attempt did not work: You weigh choices differently. In the extreme case, each set of 31 women only will be counted $31\choose 16$ times because any 16-subset of the chosen group mighg be chosen in your first step.

$\endgroup$
  • $\begingroup$ There are a total of $80$ people, so there are $\binom{80}{31}$ subsets of size $31$. $\endgroup$ – N. F. Taussig Jan 29 '16 at 16:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.