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} を用いて、示された結論を導く。