Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1969 IMO Problems/Problem 5"

(Created page with "Given n > 4 points in the plane such that no three are collinear. Prove that there are at least ³ n-3 ---- 2 ´ convex quadrilaterals whose vertices are four of the given points.")
 
 
(15 intermediate revisions by 3 users not shown)
Line 1: Line 1:
−
Given n > 4 points in the plane such that no three are collinear. Prove that
+
==Problem==
−
there are at least
+
Given <math>n > 4</math> points in the plane such that no three are collinear, prove that there are at least <math>C(n-3, 2) = {n-3 \choose 2} = \frac{(n-3)(n-4)}{2}</math> convex quadrilaterals whose vertices are four of the given points.
−
³
+
 
−
n-3
+
==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.
−
  2
+
 
−
´
+
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.
−
convex quadrilaterals whose vertices are four of the
+
 
−
given points.
+
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) = <math>\frac{(n-3)(n-4)}{2}</math> convex quadrilaterals.
 +
 
 +
The above solution was posted and copyrighted by Philip_Leszczynski. The original thread for this problem can be found here: [https://aops.com/community/p364185]
 +
 
 +
==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 <math>5</math> points, there is at least
 +
one convex quadrilateral formed by <math>4</math> of them.  Denote the
 +
<math>5</math> points by <math>A, B, C, D, E</math>.  Without loss of generality,
 +
we can chose to label the points so that <math>C, D, E</math> are on
 +
one side of the line <math>line(AB)</math>.  Further, we chose to label
 +
the point <math>C</math> so that <math>D, E</math> are on one side of <math>line(AC)</math>.
 +
It follows that <math>D, E</math> are inside <math>\angle(BAC)</math>, with
 +
segments <math>AB</math> and <math>AC</math> extended beyond <math>B</math> and <math>C</math>
 +
respectively.
 +
 
 +
Note that from the choice of <math>A, B, C</math> it follows that
 +
<math>\angle(BAC) < 2\pi</math>.  Also, we could have chosen <math>A, B, C</math>
 +
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 <math>A</math> to be any of the vertices, and
 +
<math>B, C</math> 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.
 +
 
 +
[[File:no_of_quads.png|800px]]
 +
 
 +
The line <math>line(DE)</math> must intersect at least one of <math>line(AB)</math>
 +
and <math>line(AC)</math>.  Without loss of generality, we can assume it
 +
intersects <math>line(AB)</math>.  In general, it will also intersect
 +
<math>line(AC)</math>.  The argument we are going to give is for the case
 +
when <math>line(DE)</math> intersects both <math>line(AB)</math> and <math>line(AC)</math>.  The
 +
argument needed in the limiting case when
 +
<math>line(DE) \parallel line(AC)</math> is identical, and is left as an
 +
exercise to the reader.
 +
 
 +
There are three cases:
 +
 
 +
Case 1, when <math>line(DE)</math> intersects <math>segment(AB)</math>, but it does
 +
not intersect <math>segment(AC)</math>.  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 <math>A, D, E, C</math> is convex.  (Note that this also
 +
applies to the case when <math>line(DE) \parallel line(AC)</math>.)
 +
 
 +
Case 2, when <math>line(DE)</math> intersects both <math>segment(AB)</math> and
 +
<math>segment(AC)</math>.  This is shown in the 4th picture.  In this
 +
case the quadrilateral formed by the points <math>B, D, E, C</math>
 +
is convex.
 +
 
 +
Case 3, when <math>line(DE)</math> does not intersect either of
 +
<math>segment(AB)</math> or <math>segment(AC)</math>.  This is shown in the
 +
5th picture.  In this case the quadrilateral formed by
 +
the points <math>B, D, E, C</math> is convex.  (Note that this also
 +
applies to the case when <math>line(DE) \parallel line(AC)</math>.)
 +
 
 +
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 <math>D, E</math> are
 +
inside the angle <math>\angle(BAC)</math> formed by <math>line(AB)</math> and
 +
<math>line(AC)</math> (with segments <math>AB</math> and <math>AC</math> extended beyond
 +
<math>B</math> and <math>C</math> respectively), then we can choose the convex
 +
quadrilateral so that <math>D, E</math> are both part of it.
 +
 
 +
Now the statement of the problem is easy to prove.  Assume
 +
<math>n</math> points are given.  Choose <math>3</math> of them, and label them
 +
<math>A, B, C</math>, so that all the other points are inside
 +
<math>\angle(BAC)</math>.  There are <math>(n - 3)</math> such points.  Now choose
 +
all the groups of <math>2</math> points from these <math>(n - 3)</math> points.
 +
There are <math>{n-3 \choose 2} = \frac{(n-3)(n-4)}{2}</math> ways of
 +
doing this.  From what we proved before, we know that for
 +
each choice of 2 points, call them <math>D, E</math>, there is a group
 +
of <math>4</math> points from among <math>A, B, C, D, E</math> which forms a
 +
convex quadrilateral, such that <math>D, E</math> are <math>2</math> of the <math>4</math>
 +
points.  A different choice <math>D_1, E_1</math> will yield a different
 +
quadrilateral because <math>\{D, E\} \ne \{D_1, E_1\}</math>.
 +
 
 +
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 <math>5</math> points, there is a subgroup of <math>4</math> of them which
 +
forms a convex quadrilateral.  Unlike in the previous solution,
 +
we don't care whether <math>2</math> specific points are part of it or not.
 +
Note that generally there might be several convex quadrilaterals
 +
formed from the group of <math>5</math> points.
 +
 
 +
Now, given <math>n</math> points, create a list of all the groups of <math>5</math>
 +
points chosen from the given <math>n</math> points.  This can be done in
 +
<math>{n \choose 5}</math> ways, so the list has <math>{n \choose 5}</math> elements.
 +
For each group of <math>5</math> points, choose a convex quadrilateral
 +
formed by a subgroup of the <math>5</math> points.  Thus, create a list
 +
<math>M</math> of convex quadrilaterals.  This list has <math>{n \choose 5}</math>
 +
elements.
 +
 
 +
However, note that some convex quadrilaterals in <math>M</math> are not unique,
 +
they might appear several times in <math>M</math>.  A given quadrilateral
 +
could appear up to <math>(n - 4)</math> times, as chosen from a group of <math>5</math>
 +
points which contains the <math>4</math> points of the quadrilateral, and
 +
one point from the remaining <math>(n - 4)</math> points.  We want to form
 +
the list <math>K</math>, which is a subset of <math>M</math>, such that from each group
 +
of duplicates, we keep only one.  Let <math>k</math> be the number of elements
 +
in <math>K</math>.
 +
 
 +
Since each quadrilateral in <math>M</math> appears at most <math>(n - 4)</math> times, it
 +
follows that <math>k \ge {n \choose 5} / (n-4) = \frac{C(n, 5)}{n - 4}</math>,
 +
in other words, there are at least <math>{n \choose 5} / (n-4) =
 +
\frac{C(n, 5)}{n - 4}</math> convex quadrilaterals formed from points in
 +
the given <math>n</math> 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 <math>{n \choose 5} / (n-4) \ge
 +
{n - 3 \choose 2}</math>.  This amounts to proving that
 +
 
 +
<math>\frac{n(n - 1)(n - 2)(n - 3)(n - 4)}{120(n-4)} \ge \frac{(n - 3)(n - 2)}{2}</math>
 +
 
 +
for <math>n \ge 5</math>.  Carry out the computations, and we get that we need
 +
to prove that <math>P(n) = n^3 - 3n^2 - 58n + 240 \ge 0</math> for <math>n \ge 5</math>.
 +
The polynomial <math>P(n)</math> has roots <math>-8, 5, 6</math> from which it follows that
 +
 
 +
<math>\frac{n(n - 1)(n - 2)(n - 3)(n - 4)}{120(n-4)} \ge \frac{(n - 3)(n - 2)}{2}</math>
 +
 
 +
is true, and it is an equality for <math>n = 5, 6</math> and a strict inequality for <math>n > 6</math>.
 +
 
 +
The original thread for this problem can be found here: https://aops.com/community/p364185
 +
 
 +
== See Also == {{IMO box|year=1969|num-b=4|num-a=6}}

Latest revision as of 19:10, 4 August 2024

Problem

Given $n > 4$ points in the plane such that no three are collinear, prove that there are at least $C(n-3, 2) = {n-3 \choose 2} = \frac{(n-3)(n-4)}{2}$ 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) = $\frac{(n-3)(n-4)}{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 $5$ points, there is at least one convex quadrilateral formed by $4$ of them. Denote the $5$ points by $A, B, C, D, E$. Without loss of generality, we can chose to label the points so that $C, D, E$ are on one side of the line $line(AB)$. Further, we chose to label the point $C$ so that $D, E$ are on one side of $line(AC)$. It follows that $D, E$ are inside $\angle(BAC)$, with segments $AB$ and $AC$ extended beyond $B$ and $C$ respectively.

Note that from the choice of $A, B, C$ it follows that $\angle(BAC) < 2\pi$. Also, we could have chosen $A, B, C$ 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 $A$ to be any of the vertices, and $B, C$ 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.

No of quads.png

The line $line(DE)$ must intersect at least one of $line(AB)$ and $line(AC)$. Without loss of generality, we can assume it intersects $line(AB)$. In general, it will also intersect $line(AC)$. The argument we are going to give is for the case when $line(DE)$ intersects both $line(AB)$ and $line(AC)$. The argument needed in the limiting case when $line(DE) \parallel line(AC)$ is identical, and is left as an exercise to the reader.

There are three cases:

Case 1, when $line(DE)$ intersects $segment(AB)$, but it does not intersect $segment(AC)$. 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 $A, D, E, C$ is convex. (Note that this also applies to the case when $line(DE) \parallel line(AC)$.)

Case 2, when $line(DE)$ intersects both $segment(AB)$ and $segment(AC)$. This is shown in the 4th picture. In this case the quadrilateral formed by the points $B, D, E, C$ is convex.

Case 3, when $line(DE)$ does not intersect either of $segment(AB)$ or $segment(AC)$. This is shown in the 5th picture. In this case the quadrilateral formed by the points $B, D, E, C$ is convex. (Note that this also applies to the case when $line(DE) \parallel line(AC)$.)

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 $D, E$ are inside the angle $\angle(BAC)$ formed by $line(AB)$ and $line(AC)$ (with segments $AB$ and $AC$ extended beyond $B$ and $C$ respectively), then we can choose the convex quadrilateral so that $D, E$ are both part of it.

Now the statement of the problem is easy to prove. Assume $n$ points are given. Choose $3$ of them, and label them $A, B, C$, so that all the other points are inside $\angle(BAC)$. There are $(n - 3)$ such points. Now choose all the groups of $2$ points from these $(n - 3)$ points. There are ${n-3 \choose 2} = \frac{(n-3)(n-4)}{2}$ ways of doing this. From what we proved before, we know that for each choice of 2 points, call them $D, E$, there is a group of $4$ points from among $A, B, C, D, E$ which forms a convex quadrilateral, such that $D, E$ are $2$ of the $4$ points. A different choice $D_1, E_1$ will yield a different quadrilateral because $\{D, E\} \ne \{D_1, E_1\}$.

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 $5$ points, there is a subgroup of $4$ of them which forms a convex quadrilateral. Unlike in the previous solution, we don't care whether $2$ specific points are part of it or not. Note that generally there might be several convex quadrilaterals formed from the group of $5$ points.

Now, given $n$ points, create a list of all the groups of $5$ points chosen from the given $n$ points. This can be done in ${n \choose 5}$ ways, so the list has ${n \choose 5}$ elements. For each group of $5$ points, choose a convex quadrilateral formed by a subgroup of the $5$ points. Thus, create a list $M$ of convex quadrilaterals. This list has ${n \choose 5}$ elements.

However, note that some convex quadrilaterals in $M$ are not unique, they might appear several times in $M$. A given quadrilateral could appear up to $(n - 4)$ times, as chosen from a group of $5$ points which contains the $4$ points of the quadrilateral, and one point from the remaining $(n - 4)$ points. We want to form the list $K$, which is a subset of $M$, such that from each group of duplicates, we keep only one. Let $k$ be the number of elements in $K$.

Since each quadrilateral in $M$ appears at most $(n - 4)$ times, it follows that $k \ge {n \choose 5} / (n-4) = \frac{C(n, 5)}{n - 4}$, in other words, there are at least ${n \choose 5} / (n-4) = \frac{C(n, 5)}{n - 4}$ convex quadrilaterals formed from points in the given $n$ 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 ${n \choose 5} / (n-4) \ge {n - 3 \choose 2}$. This amounts to proving that

$\frac{n(n - 1)(n - 2)(n - 3)(n - 4)}{120(n-4)} \ge \frac{(n - 3)(n - 2)}{2}$

for $n \ge 5$. Carry out the computations, and we get that we need to prove that $P(n) = n^3 - 3n^2 - 58n + 240 \ge 0$ for $n \ge 5$. The polynomial $P(n)$ has roots $-8, 5, 6$ from which it follows that

$\frac{n(n - 1)(n - 2)(n - 3)(n - 4)}{120(n-4)} \ge \frac{(n - 3)(n - 2)}{2}$

is true, and it is an equality for $n = 5, 6$ and a strict inequality for $n > 6$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1969_IMO_Problems/Problem_5&oldid=224464"