MathLabs

Problem 4

Let SS be a set consisting of mm pairs (a,b)(a,b) of positive integers with 1≤a<b≤n1\le a<b\le n. Show that there are at least m(4m−n2)3n\dfrac{m(4m-n^2)}{3n} triples (a,b,c)(a,b,c) such that (a,b),(a,c)(a,b),(a,c), and (b,c)(b,c) belong to SS.
Step 4 of 5: Apply Cauchy–Schwarz to the degrees
Previous stepNext step
∑i=1ndi2≥(∑idi)2n=4m2n\sum_{i=1}^n d_i^2\ge\frac{(\sum_i d_i)^2}{n}=\frac{4m^2}{n}
Detailed analysis

Cauchy–Schwarz gives n∑idi2≥(∑idi)2n\sum_i d_i^2\ge(\sum_i d_i)^2. Substituting ∑idi=2m\sum_i d_i=2m yields ∑idi2≥4m2/n\sum_i d_i^2\ge4m^2/n.