In a group of m girls and n 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+2n(n−1).
Solution
From the hypothesis, for any two boys, there is at most one girl that knows both of them. Let xi be the number of girls that know exactly i boys, 1≤i≤n. So ∑i=1nxi=m. By counting the number of the above two boys-one girl combinations, we have i≥2∑2i(i−1)xi≤2n(n−1). The number of boy-girl pairs that know each other is then i=1∑nixi=m+i=2∑n(i−1)xi≤m+i=2∑n2i(i−1)xi≤m+2n(n−1).□
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.