MathLabs

第3题

nn 为正整数。nn 个人参加聚会，每一对人要么相识要么不相识。求不相识但在参加者中有共同熟人的点对数的最大值。
第 5/6 步：上界
上一步下一步
#counted pairs≤(n2)−(n−1)\#\text{counted pairs}\le\binom n2-(n-1)
详细分析

本步骤利用假设和公式 n−1n-1、(n2)−(n−1)=(n−12)\binom n2-(n-1)=\binom{n-1}{2}，推出所述结论。