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} 個あることを示せ。
ステップ 3/5: 辺について和を取り三つ組の重複を補正する
前のステップ次のステップ
T≥13∑(i,j)∈S(di+dj−n)=13(∑i=1ndi2−mn)T\ge\frac13\sum_{(i,j)\in S}(d_i+d_j-n)=\frac13\left(\sum_{i=1}^n d_i^2-mn\right)
詳しい解説

mm 本の辺について共通隣接点の下界を足すと、辺とそれを完成させる頂点の出現回数になる。良い三つ組は3辺をもつので3回数えられる。また各 did_i は接する辺ごとに1回現れるから次数項の和は ∑idi2\sum_i d_i^2 であり、nn の項の和は mnmn である。