In a school there are male and female students. Each student joins not more than clubs in the school. It is known that any two students of opposite genders have joined at least one common club. Show that there is a club with at least male and female members.
Solution
Suppose on the contrary that no club contains at least male and female members. We shall count the number of triples where is a male student, is a female student and is a club joined by these two students.
Firstly, for each of the choices of and each of the choices of , the condition shows that there is at least one club for which should be counted. This gives at least triples.
Secondly, we count according to the clubs. We label the clubs as . For each , let and be the numbers of male students and female students in the club respectively. Then the number of triples is
From the assumption, we can divide these clubs into two groups. The first group consists of those clubs with at most male members (say ). The second group consists of those clubs with at least male members, and hence at most female members (say ). Then
Note that the sum over counts the total number of female members in all clubs. By another simple double counting, this is equal to the total number of clubs joined by all the female students. Therefore, we have
The same upper bound holds for the sum over . Combining all these, we obtain
This is a contradiction. Hence, there must be a club with at least male and female members.