Problem 4

Let

S

be a set consisting of

m

pairs

(a,b)

of positive integers with

1\le a<b\le n

. Show that there are at least

\dfrac{m(4m-n^2)}{3n}

triples

(a,b,c)

such that

(a,b),(a,c)

, and

(b,c)

belong to

S

Step 5 of 5: Conclude the Goodman-type lower bound

Previous step Next step

T\ge\frac13\left(\frac{4m^2}{n}-mn\right)=\boxed{\frac{m(4m-n^2)}{3n}}

Detailed analysis

Insert the Cauchy–Schwarz bound into the incidence estimate. This gives $T\ge(4m^2/n-mn)/3=m(4m-n^2)/(3n)$ , as required (when the right side is negative the assertion is automatic).