1969 IMO Problems/Problem 5
Contents
[hide]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 based on DHu's idea
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 on
one side of the line
. Further, we chose to label
the point
so that
are on one side of
.
It follows that
are inside
, with
segments
and
extended beyond
and
respectively.
Note that from the choice of it follows that
. Also, we could have chosen
by considering the convex hull of the set of 5 points. It
is either a triangle, or a convex quadrilateral, or a convex
pentagon. We choose
to be any of the vertices, and
to be the adjacent vertices. (We don't need these
notes in the proof, I just wanted to make things easier to
visualize.)
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 is for the case
when
intersects both
and
. The
argument needed in the limiting case when
is identical, and is left as an
exercise to the reader.
There are three cases:
Case 1, when intersects
, but it does
not intersect
. This is shown on the first 3
pictures (one picture would have been enough, but I made all
of them, for emphasis). In this case the quadrilateral formed
by the points
is convex. (Note that this also
applies to the case when
.)
Case 2, when intersects both
and
. This is shown in the 4th picture. In this
case the quadrilateral formed by the points
is convex.
Case 3, when does not intersect either of
or
. This is shown in the
5th picture. In this case the quadrilateral formed by
the points
is convex. (Note that this also
applies to the case when
.)
We thus proved that in any group of 5 points, there is a subgroup of 4 points which forms a convex quadrilateral. Note that in general, given a group of 5 points, more than one convex quadrilateral can be found by taking subgroups of 4 points.
Important remark: In fact, we proved more: if are
inside the angle
formed by
and
(with segments
and
extended beyond
and
respectively), then we can choose the convex
quadrilateral so that
are both part of it.
Now the statement of the problem is easy to prove. Assume
points are given. Choose
of them, and label them
, so that all the other points are inside
. There are
such points. Now choose
all the groups of
points from these
points.
There are
ways of
doing this. From what we proved before, we know that for
each choice of 2 points, call them
, there is a group
of
points from among
which forms a
convex quadrilateral, such that
are
of the
points. A different choice
will yield a different
quadrilateral because
.
This concludes the proof.
Solution 2, based on manuel's idea
As we did in the previous solution, we first prove that given
a group of points, there is a subgroup of
of them which
forms a convex quadrilateral. Unlike in the previous solution,
we don't care whether
specific points are part of it or not.
Note that generally there might be several convex quadrilaterals
formed from the group of
points.
Now, given points, create a list of all the groups of
points chosen from the given
points. This can be done in
ways, so the list has
elements.
For each group of
points, choose a convex quadrilateral
formed by a subgroup of the
points. Thus, create a list
of convex quadrilaterals. This list has
elements.
However, note that some convex quadrilaterals in are not unique,
they might appear several times in
. A given quadrilateral
could appear up to
times, as chosen from a group of
points which contains the
points of the quadrilateral, and
one point from the remaining
points. We want to form
the list
, which is a subset of
, such that from each group
of duplicates, we keep only one. Let
be the number of elements
in
.
Since each quadrilateral in appears at most
times, it
follows that
,
in other words, there are at least
convex quadrilaterals formed from points in
the given
points.
This is a stronger result than the one in the statement of the problem.
To prove the statement of the problem, we will prove the assertion I
just made above, by showing that . This amounts to proving that
for . Carry out the computations, and we get that we need
to prove that
for
.
The polynomial
has roots
from which it follows that
is true, and it is an equality for and a strict inequality for
.
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 |