Given n > 4 points in the plane, no three collinear. Prove that there are at least (n-3)(n-4)/2 convex quadrilaterals with vertices amongst the n points.
Solution
(n-3)(n-4)/2 is a poor lower bound.
Observe first that any 5 points include 4 forming a convex quadrilateral. For take the convex hull. If it consists of more than 3 points, we are done. If not, it must consist of 3 points, A, B and C, with the other 2 points, D and E, inside the triangle ABC. Two vertices of the triangle must lie on the same side of the line DE and they form convex quadrilateral with D and E.
Given n points, we can choose 5 in n(n-1)(n-2)(n-3)(n-4)/120 different ways. Each choice gives us a convex quadrilateral, but any given convex quadrilateral may arise from n-4 different sets of 5 points, so we have at least n(n-1)(n-2)(n-3)/120 different convex quadrilaterals. We now show that n(n-1)(n-2)(n-3)/120 ≥ (n-3)(n-4)/2 for all n ≥ 5.
We wish to prove that n(n-1)(n-2) ≥ 60(n-4), or n(n-1)(n-2) - 60(n-4) ≥ 0. Trial shows equality for n = 5 and 6, so we can factorise and get (n-5)(n-6)(n+8), which is clearly at least 0 for n at least 5.
Solutions are also available in: Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
5 Oct 1998
Last corrected/updated 5 Oct 1998