Maths Olympiad Prep

Library / /3 of 53

Combinatorics Difficulty 4.9 AIME Prove it China

In a group of mm girls and nn boys, any two of them either know each other, or do not know each other. For any two boys and two girls, at least one boy and one girl do not know each other. Prove that the number of boy-girl pairs that know each other is at most m+n(n1)2m + \frac{n(n-1)}{2}.

Solution

From the hypothesis, for any two boys, there is at most one girl that knows both of them. Let xix_i be the number of girls that know exactly ii boys, 1in1 \le i \le n. So i=1nxi=m\sum_{i=1}^{n} x_i = m. By counting the number of the above two boys-one girl combinations, we have
i2i(i1)2xin(n1)2. \sum_{i \ge 2} \frac{i(i-1)}{2} x_i \le \frac{n(n-1)}{2}.
The number of boy-girl pairs that know each other is then

i=1nixi=m+i=2n(i1)xim+i=2ni(i1)2xim+n(n1)2.\begin{aligned} \sum_{i=1}^{n} ix_i &= m + \sum_{i=2}^{n} (i-1)x_i \le m + \sum_{i=2}^{n} \frac{i(i-1)}{2}x_i \\ &\le m + \frac{n(n-1)}{2}. \end{aligned} \quad \square

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 and solution reproduced as published; topic and difficulty added by this site.