1969 IMO Problems/Problem 5
Problem
Given 
points in the plane such that no three are collinear, prove that there are at least 
convex quadrilaterals whose vertices are four of the given points.
Solution
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) = 
convex quadrilaterals.
The above solution was posted and copyrighted by Philip_Leszczynski. The original thread for this problem can be found here: [1]
Remarks (added by pf02, August 2024)
The solution given above is incorrect. This is pointed out very clearly and explicitly by DHu on https://aops.com/community/p364185. I will not repeat the argument here. DHu also gives the idea for a correct proof.
On the same page (https://aops.com/community/p364185), manuel gives an idea for a proof of a stronger result. His proof is somewhere between vague, incorrect and incomplete.
Below, I will give two solutions. The first is just an expansion of DHu's idea. The second one is carrying out manuel's idea.
Solution
We start by proving that given 
points, there is at least
one convex quadrilateral formed by 
of them. Denote the
points by 
. Without loss of generality,
we can chose to label the points so that 
are to the
right of the line 
. Further, we chose to label the
point 
so that 
are above the line 
. The
picture below shows this choice of labels.
The line 
must intersect at least one of
and . Without loss of generality, we can assume it
intersects . In general, it will also intersect
. The argument we are going to give for the case
when intersects both and is
identical to the argument needed in the limiting case (when
line(AC)$) and is left as an exercise to
the reader.
There are three cases:
[TO BE CONTINUED. I AM JUST SAVING THIS BEFORE IT IS FINISHED, SO I DON'T LOSE WORK DONE SO FAR.]
The original thread for this problem can be found here: https://aops.com/community/p364185
See Also
| 1969 IMO (Problems) • Resources | ||
| Preceded by Problem 4 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
| All IMO Problems and Solutions | ||
