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。
第 5/5 步：得到 Goodman 型下界
上一步下一步
T≥13(4m2n−mn)=m(4m−n2)3nT\ge\frac13\left(\frac{4m^2}{n}-mn\right)=\boxed{\frac{m(4m-n^2)}{3n}}
详细分析

将柯西–施瓦茨下界代入计数估计，得 T≥(4m2/n−mn)/3=m(4m−n2)/(3n)T\ge(4m^2/n-mn)/3=m(4m-n^2)/(3n)，即所求（若右边为负则结论自动成立）。