MathLabs

第4問

SS を、1≤a<b≤n1\le a<b\le n を満たす正整数の組 (a,b)(a,b) を mm 個含む集合とする。(a,b),(a,c)(a,b),(a,c)、および (b,c)(b,c) が SS に属する三つ組 (a,b,c)(a,b,c) が少なくとも m(4m−n2)3n\dfrac{m(4m-n^2)}{3n} 個あることを示せ。
ステップ 4/5: 次数にコーシー・シュワルツを適用する
∑i=1ndi2≥(∑idi)2n=4m2n\sum_{i=1}^n d_i^2\ge\frac{(\sum_i d_i)^2}{n}=\frac{4m^2}{n}
詳しい解説

コーシー・シュワルツより n∑idi2≥(∑idi)2n\sum_i d_i^2\ge(\sum_i d_i)^2。∑idi=2m\sum_i d_i=2m を代入して ∑idi2≥4m2/n\sum_i d_i^2\ge4m^2/n を得る。