在 $m$ 个女孩和 $n$ 个男孩组成的群体中，任意两人要么相互认识，要么互不认识．对任意两个男孩和两个女孩，其中至少有一个男孩与一个女孩互不认识．求证：相互认识的男女孩对的个数不超过 $m+\dfrac{n(n-1)}{2}$．
【难度】
【出处】
2013第12届CGMO试题
【标注】
【答案】
略
【解析】
由已知条件，对任意两个男孩，至多有一个公共认识的女孩．考虑恰好认识 $i$ 个男孩的女孩．记这些女孩的人数为 $x_i$，$1\leqslant i\leqslant n$．故 $\sum_{i=1}^{n}x_i =m$．计算上述两男一女三人组的个数，则有 $\sum_{i\geqslant 2} \dfrac{i(i-1)}{2} x_{i} \leqslant \dfrac{n(n-1)}{2}$，
相识的男女孩对的个数为
$\begin{aligned} \sum_{i=1}^{n} i x_{i} &=m+\sum_{i=2}^{n}(i-1) x_{i} \\ & \leqslant m+\sum_{i=2}^{n} \frac{i(i-1)}{2} x_{i} \\ & \leqslant m+\frac{n(n-1)}{2} \end{aligned}$
相识的男女孩对的个数为
$\begin{aligned} \sum_{i=1}^{n} i x_{i} &=m+\sum_{i=2}^{n}(i-1) x_{i} \\ & \leqslant m+\sum_{i=2}^{n} \frac{i(i-1)}{2} x_{i} \\ & \leqslant m+\frac{n(n-1)}{2} \end{aligned}$
答案
解析
备注
