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 "1970 IMO Problems/Problem 6"
 
(3 intermediate revisions by 2 users not shown)
Line 2: Line 2:
  
 
In a plane there are <math>100</math> points, no three of which are collinear.  Consider all possible triangles having these point as vertices.  Prove that no more than <math>70 \%</math> of these triangles are acute-angled.
 
In a plane there are <math>100</math> points, no three of which are collinear.  Consider all possible triangles having these point as vertices.  Prove that no more than <math>70 \%</math> of these triangles are acute-angled.
 +
  
 
==Solution==
 
==Solution==
−
At most 3 of the triangles formed by 4 points can be acute. It follows that at most 7 out of the 10 triangles formed by any 5 points can be acute. For given 10 points, the maximum no. of acute triangles is: the no. of subsets of 4 points x 3/the no. of subsets of 4 points containing 3 given points. The total no. of triangles is the same expression with the first 3 replaced by 4. Hence at most 3/4 of the 10, or 7.5, can be acute, and hence at most 7 can be acute.
+
 
−
The same argument now extends the result to 100 points. The maximum number of acute triangles formed by 100 points is: the no. of subsets of 5 points x 7/the no. of subsets of 5 points containing 3 given points. The total no. of triangles is the same expression with 7 replaced by 10. Hence at most 7/10 of the triangles are acute.
+
At most <math>3</math> of the triangles formed by <math>4</math> points can be acute. It follows that at most <math>7</math> out of the <math>10</math> triangles formed by any <math>5</math> points can be acute. For given <math>10</math> points, the maximum number of acute triangles is: the number of subsets of <math>4</math> points times <math>\frac{3}{\text{the number of subsets of 4 points containing 3 given points}}</math>. The total number of triangles is the same expression with the first <math>3</math> replaced by <math>4</math>. Hence at most <math>\frac{3}{4}</math> of the <math>10</math>, or <math>7.5</math>, can be acute, and hence at most <math>7</math> can be acute.
 +
The same argument now extends the result to <math>100</math> points. The maximum number of acute triangles formed by <math>100</math> points is: the number of subsets of <math>5</math> points times <math>\frac{7}{\text{the number of subsets of 5 points containing 3 given points}}</math>. The total number of triangles is the same expression with <math>7</math> replaced by <math>10</math>. Hence at most <math>\frac{7}{10}</math> of the triangles are acute.
 +
 
 +
 
 +
==Remarks (added by pf02, December 2024)==
 +
 
 +
1.  The solution above contains an error (a typo?) and skips too many steps,
 +
which make it very hard to understand.  For the benefit of future readers,
 +
and as a public service, I re-write the proof below.
 +
 
 +
2.  Note the commonality with [[1969 IMO Problems/Problem 5]].  In fact,
 +
the solution to this problem has a strong commonality with Solution 2
 +
of [[1969 IMO Problems/Problem 5]].
 +
 
 +
 
 +
==Solution re-written==
 +
 
 +
Define a <math>n</math>-gon to be a configuration of <math>n</math> points, no three
 +
of which are collinear.  Given an <math>n</math>-gon draw all the triangles
 +
whose vertices are among the <math>n</math> points.  We say that a triangle
 +
<math>\triangle ABC</math> is in the <math>n</math>-gon, or that the <math>n</math>-gon has
 +
<math>\triangle ABC</math> in it, if <math>A, B, C</math> are points in the <math>n</math>-gon.
 +
 
 +
We start by proving that a <math>4</math>-gon has <math>4</math> triangles, out of which
 +
at most <math>3</math> are acute.
 +
 
 +
[[File:prob_1970_6.png|600px]]
 +
 
 +
Clearly there are exactly <math>4</math> triangles.  We have two cases.  If
 +
the convex hull of the <math>4</math>-gon is a quadrilateral, then at least
 +
one of <math>\angle A, \angle B, \angle C, \angle D</math> is <math>\ge \frac{\pi}{2}</math>
 +
(if they were all <math>< \frac{\pi}{2}</math> then
 +
<math>\angle A + \angle B + \angle C + \angle D < 2\pi</math>, which is false).
 +
Let us say that <math>\angle C \ge \frac{\pi}{2}</math>.  Then <math>\triangle BCD</math>
 +
is obtuse, so at most the other <math>3</math> triangles are acute.  (Note
 +
that it is possible to have <math>3</math> acute triangles.)
 +
 
 +
If the convex hull of the <math>4</math>-gon is a triangle, let us say that <math>C</math>
 +
is in the interior of <math>\triangle ABD</math>.  Then at least two of
 +
<math>\angle ACB, \angle BCD, \angle DCA</math> are
 +
<math>\ge \frac{2\pi}{3} > \frac{\pi}{2}</math> (if they were all
 +
<math>< \frac{2\pi}{3}</math> then their sum would be <math>< 2\pi</math>, which is false).
 +
So, at least two of <math>\triangle ACB, \triangle BCD, \triangle DCA</math>
 +
are obtuse.
 +
 
 +
Note: We would be tempted to use this result, and the argument which
 +
follows below to prove the problem.  But that would only yield the
 +
result that at most 75% of the triangles in an <math>n</math>-gon (in particular
 +
a <math>100</math>-gon) are acute.  We need to do better.
 +
 
 +
Now, we will prove that a <math>5</math>-gon has <math>10</math> triangles, out of which
 +
at most <math>7</math> are acute.  It is easy to see  that there are <math>10</math>
 +
triangles in a <math>5</math>-gon, either by counting, or by remembering that
 +
the number of triangles <math>= C(5, 3) = {5 \choose 3} =
 +
\frac{5 \cdot 4 \cdot 3}{1 \cdot 2 \cdot 3} = 10</math>.  Now, we could
 +
proceed like in the case of a <math>4</math>-gon, by looking at many possible
 +
cases and chasing angle sizes.  Instead, we will give a different
 +
argument, using an idea we will use again later.
 +
 
 +
A <math>5</math>-gon has <math>5</math> <math>4</math>-gons in it.  Each of these <math>4</math>-gons has <math>4</math>
 +
triangles in it, of which at most <math>3</math> are acute. Make a list
 +
<math>\mathcal{L}_1</math> of all the triangles, and a sub-list <math>\mathcal{L}_2</math>
 +
of all the acute triangles.  The size of <math>\mathcal{L}_1 = 5 \cdot 4 = 20</math>,
 +
and the size of <math>\mathcal{L}_2 \le 5 \cdot 3 = 15</math>.  These lists contain
 +
duplicates.  Each triangle is counted exactly twice (corresponding to
 +
the two points which are not in the triangle; we can see this as
 +
<math>= C(5-3, 4-3) = C(2, 1) = {2 \choose 1} = 2</math>).  Dividing by <math>2</math> to
 +
eliminate duplicates, we get that out of the <math>\frac{20}{2} = 10</math>
 +
triangles, at most <math>\frac{15}{2} = 7.5</math> are acute.  We conclude that
 +
at most <math>7</math> out of the <math>10</math> are acute.
 +
 
 +
Now we are ready to prove that given a <math>n</math>-gon with <math>n > 5</math>, at most
 +
<math>\frac{7}{10} = 70\%</math> of its triangles are acute.  Consider all the
 +
<math>5</math>-gons in the given <math>n</math>-gon, and consider all the triangles in each
 +
<math>5</math>-gon.  Make a list <math>\mathcal{L}_1</math> of all these triangles, and a
 +
sub-list <math>\mathcal{L}_2</math> of all the acute triangles.  We have that
 +
<math>\frac{\text{size of } \mathcal{L}_2}{\text{size of } \mathcal{L}_1} \le
 +
\frac{7}{10}</math> (according to what we showed above).  These lists contain
 +
duplicates.  Each triangle is counted the same number of times, say <math>k</math>
 +
times (in fact, <math>k = C(n-3, 5-3) = C(n-3, 2) = {n-3 \choose 2}</math>, but we
 +
don't need this).  Dividing both the numerator and the denominator by <math>k</math>
 +
to eliminate duplicates, we have that at most <math>\frac{7}{10} = 70\%</math> of
 +
the triangles are acute.
 +
 
 +
[Re-writing by pf02, December 2024]
 +
 
  
 
{{IMO box|year=1970|num-b=5|after=Last question}}
 
{{IMO box|year=1970|num-b=5|after=Last question}}
  
 
[[Category:Olympiad Geometry Problems]]
 
[[Category:Olympiad Geometry Problems]]

Latest revision as of 18:09, 11 December 2024

Problem

In a plane there are $100$ points, no three of which are collinear. Consider all possible triangles having these point as vertices. Prove that no more than $70 \%$ of these triangles are acute-angled.


Solution

At most $3$ of the triangles formed by $4$ points can be acute. It follows that at most $7$ out of the $10$ triangles formed by any $5$ points can be acute. For given $10$ points, the maximum number of acute triangles is: the number of subsets of $4$ points times $\frac{3}{\text{the number of subsets of 4 points containing 3 given points}}$. The total number of triangles is the same expression with the first $3$ replaced by $4$. Hence at most $\frac{3}{4}$ of the $10$, or $7.5$, can be acute, and hence at most $7$ can be acute. The same argument now extends the result to $100$ points. The maximum number of acute triangles formed by $100$ points is: the number of subsets of $5$ points times $\frac{7}{\text{the number of subsets of 5 points containing 3 given points}}$. The total number of triangles is the same expression with $7$ replaced by $10$. Hence at most $\frac{7}{10}$ of the triangles are acute.


Remarks (added by pf02, December 2024)

1. The solution above contains an error (a typo?) and skips too many steps, which make it very hard to understand. For the benefit of future readers, and as a public service, I re-write the proof below.

2. Note the commonality with 1969 IMO Problems/Problem 5. In fact, the solution to this problem has a strong commonality with Solution 2 of 1969 IMO Problems/Problem 5.


Solution re-written

Define a $n$-gon to be a configuration of $n$ points, no three of which are collinear. Given an $n$-gon draw all the triangles whose vertices are among the $n$ points. We say that a triangle $\triangle ABC$ is in the $n$-gon, or that the $n$-gon has $\triangle ABC$ in it, if $A, B, C$ are points in the $n$-gon.

We start by proving that a $4$-gon has $4$ triangles, out of which at most $3$ are acute.

Prob 1970 6.png

Clearly there are exactly $4$ triangles. We have two cases. If the convex hull of the $4$-gon is a quadrilateral, then at least one of $\angle A, \angle B, \angle C, \angle D$ is $\ge \frac{\pi}{2}$ (if they were all $< \frac{\pi}{2}$ then $\angle A + \angle B + \angle C + \angle D < 2\pi$, which is false). Let us say that $\angle C \ge \frac{\pi}{2}$. Then $\triangle BCD$ is obtuse, so at most the other $3$ triangles are acute. (Note that it is possible to have $3$ acute triangles.)

If the convex hull of the $4$-gon is a triangle, let us say that $C$ is in the interior of $\triangle ABD$. Then at least two of $\angle ACB, \angle BCD, \angle DCA$ are $\ge \frac{2\pi}{3} > \frac{\pi}{2}$ (if they were all $< \frac{2\pi}{3}$ then their sum would be $< 2\pi$, which is false). So, at least two of $\triangle ACB, \triangle BCD, \triangle DCA$ are obtuse.

Note: We would be tempted to use this result, and the argument which follows below to prove the problem. But that would only yield the result that at most 75% of the triangles in an $n$-gon (in particular a $100$-gon) are acute. We need to do better.

Now, we will prove that a $5$-gon has $10$ triangles, out of which at most $7$ are acute. It is easy to see that there are $10$ triangles in a $5$-gon, either by counting, or by remembering that the number of triangles $= C(5, 3) = {5 \choose 3} = \frac{5 \cdot 4 \cdot 3}{1 \cdot 2 \cdot 3} = 10$. Now, we could proceed like in the case of a $4$-gon, by looking at many possible cases and chasing angle sizes. Instead, we will give a different argument, using an idea we will use again later.

A $5$-gon has $5$ $4$-gons in it. Each of these $4$-gons has $4$ triangles in it, of which at most $3$ are acute. Make a list $\mathcal{L}_1$ of all the triangles, and a sub-list $\mathcal{L}_2$ of all the acute triangles. The size of $\mathcal{L}_1 = 5 \cdot 4 = 20$, and the size of $\mathcal{L}_2 \le 5 \cdot 3 = 15$. These lists contain duplicates. Each triangle is counted exactly twice (corresponding to the two points which are not in the triangle; we can see this as $= C(5-3, 4-3) = C(2, 1) = {2 \choose 1} = 2$). Dividing by $2$ to eliminate duplicates, we get that out of the $\frac{20}{2} = 10$ triangles, at most $\frac{15}{2} = 7.5$ are acute. We conclude that at most $7$ out of the $10$ are acute.

Now we are ready to prove that given a $n$-gon with $n > 5$, at most $\frac{7}{10} = 70\%$ of its triangles are acute. Consider all the $5$-gons in the given $n$-gon, and consider all the triangles in each $5$-gon. Make a list $\mathcal{L}_1$ of all these triangles, and a sub-list $\mathcal{L}_2$ of all the acute triangles. We have that $\frac{\text{size of } \mathcal{L}_2}{\text{size of } \mathcal{L}_1} \le \frac{7}{10}$ (according to what we showed above). These lists contain duplicates. Each triangle is counted the same number of times, say $k$ times (in fact, $k = C(n-3, 5-3) = C(n-3, 2) = {n-3 \choose 2}$, but we don't need this). Dividing both the numerator and the denominator by $k$ to eliminate duplicates, we have that at most $\frac{7}{10} = 70\%$ of the triangles are acute.

[Re-writing by pf02, December 2024]


1970 IMO (Problems) • Resources
Preceded by
Problem 5 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Last question
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1970_IMO_Problems/Problem_6&oldid=236779"