Given $n>4$ points in the plane, no three collinear. Prove that there are at least $\frac{(n-3)(n-4)}{2}$ convex quadrilaterals with vertices amongst the $n$ points.
Problem
Source: IMO 1969 B2
Tags: combinatorics, combinatorial geometry, counting, convex quadrilateral, IMO, IMO 1969
Philip_Leszczynski
08.11.2005 06:07
Orient the points so that one of them corresponds to the origin (A), another lies on the y-axis (B), and all the others are in either quandrant I or IV. (In other words, you are creating a boundary line.) Select one of the points (C) which minimizes the angle BAC. You cannot have two of them because then they would be collinear. Also no points lie inside the area of ABC because if such a point D did exist, then the angle DAC would be less than BAC - contradiction. So there are none of the other n-3 points inside the area of ABC.
Now we will show that for any two of the remaining n-3 points, you can create a convex quadrilateral containing two of them and two of A,B,C.
Now select two arbitrary points from the remaining n-3. Call them E and F, and draw a line though them; call this line l. If l does not intersect ABC, then ABCEF is convex and you choose the quadrilateral ABEF.
The other case is that it separates ABC such that one of A,B,C is one one side of l and the other two are on the other side. Without loss of generality, A is on one side of l while B and C are on the other side. Consider the quadrilateral BCEF (or CBEF, depending on orientation.) We know that BC are on the same side of EF. Also, since no points are in the third quadrant, we know that EF are on the same side of BC. Now we can choose either BCEF or CBEF to be our convex quadrilateral.
So we now have that for the given ABC, all pairs of the other n points give a distinct convex quadrilateral. So we have n-3 points to choose from, and we must choose two of them. So this gives us at least C(n-3,2) = $\frac{(n-3)(n-4)}{2}$ convex quadrilaterals.
[edit] Slight technicality.
manuel
14.03.2006 06:45
We can also proceed by showing that given 5 points with the given conditions, there is always a convex quadrilateral. Then we can choose 5 points from the set of n points in $n\choose 5$ ways. But each quadrialteral is counted $n-4$ times, so the problem is equivalent to proving that ${n\choose5}\frac{1}{n-4}\geq{{n-3}\choose2}$, which is trivial.
DHu
18.05.2013 19:10
Philip_Leszczynski wrote: Now select two arbitrary points from the remaining n-3. Call them E and F, and draw a line though them; call this line l. If l does not intersect ABC, then ABCEF is convex and you choose the quadrilateral ABEF. The other case is that it separates ABC such that one of A,B,C is one one side of l and the other two are on the other side. Without loss of generality, A is on one side of l while B and C are on the other side. Consider the quadrilateral BCEF (or CBEF, depending on orientation.) We know that BC are on the same side of EF. Also, since no points are in the third quadrant, we know that EF are on the same side of BC. Now we can choose either BCEF or CBEF to be our convex quadrilateral. Sorry, I just noticed this. I don't think this is right. The critical case is actually whether l intersects AB or not. And it seems possible for line BC to intersect segment EF and line EF to intersect ABC: A=(0,0), B=(0,4), C=(2,2), E=(2,1), F=(4,1). Here the only convex quad is ABCE. On the other hand, letting the C be the point that maximises BAC seems to solve the problem. Then all the points are between lines AB and AC, and lines AB and AC will not intersect segment EF. And the only case when line EF manages to intersect both segments AB and AC is a case where segments EF and BC do not intersect. A convex quad with both E and F is found in all cases.
eazy_math
19.07.2021 21:13
........