MathLabs

第4题

设 SS 是由 mm 个满足 1≤a<b≤n1\le a<b\le n 的正整数对 (a,b)(a,b) 组成的集合。证明存在至少 m(4m−n2)3n\dfrac{m(4m-n^2)}{3n} 个三元组 (a,b,c)(a,b,c),使得 (a,b),(a,c)(a,b),(a,c) 和 (b,c)(b,c) 都属于 SS。
第 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。