Maths Olympiad Prep

Library / /39 of 94

Combinatorics Difficulty 5.8 AIME, harder Prove it Hong Kong

In a school there are 20072007 male and 20072007 female students. Each student joins not more than 100100 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 1111 male and 1111 female members.

Solution

Suppose on the contrary that no club contains at least 1111 male and 1111 female members. We shall count the number of triples (M,F,C)(M, F, C) where MM is a male student, FF is a female student and CC is a club joined by these two students.

Firstly, for each of the 20072007 choices of MM and each of the 20072007 choices of FF, the condition shows that there is at least one club CC for which (M,F,C)(M, F, C) should be counted. This gives at least 200722007^2 triples.

Secondly, we count according to the clubs. We label the clubs as C1,C2,,CkC_1, C_2, \dots, C_k. For each i=1,2,,ki = 1, 2, \dots, k, let mim_i and fif_i be the numbers of male students and female students in the club CiC_i respectively. Then the number of triples (M,F,C)(M, F, C) is
i=1kmifi. \sum_{i=1}^{k} m_i f_i .
From the assumption, we can divide these clubs into two groups. The first group consists of those clubs with at most 1010 male members (say C1,C2,,CC_1, C_2, \dots, C_\ell). The second group consists of those clubs with at least 1111 male members, and hence at most 1010 female members (say C+1,C+2,,CkC_{\ell+1}, C_{\ell+2}, \dots, C_k). Then
i=1kmifi=i=1mifi+i=+1kmifi10i=1fi+10i=+1kmi10i=1kfi+10i=1kmi. \begin{aligned} \sum_{i=1}^{k} m_i f_i &= \sum_{i=1}^{\ell} m_i f_i + \sum_{i=\ell+1}^{k} m_i f_i \\ &\le 10 \sum_{i=1}^{\ell} f_i + 10 \sum_{i=\ell+1}^{k} m_i \\ &\le 10 \sum_{i=1}^{k} f_i + 10 \sum_{i=1}^{k} m_i. \end{aligned}
Note that the sum over fif_i 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
i=1kfi100×2007. \sum_{i=1}^{k} f_i \le 100 \times 2007.
The same upper bound holds for the sum over mim_i. Combining all these, we obtain
2007210×100×2007+10×100×2007=2000×2007. 2007^2 \le 10 \times 100 \times 2007 + 10 \times 100 \times 2007 = 2000 \times 2007.
This is a contradiction. Hence, there must be a club with at least 1111 male and 1111 female members.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.