Olympiad Maths Prep

Track / Stage 7 / 10 of 300 #1410 of 2000

Problem 1410

National olympiad second round; IMO P1/P4
Geometry Difficulty 7.0 Prove it

In a circle of diameter 11 consider 6565 points, no three of them collinear. Prove that there exist three among these points which are the vertices of a triangle with area less than or equal to 172\frac{1}{72}.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

1. Understanding the Problem:
We are given a circle with a diameter of 1 and 65 points inside it, with no three points being collinear. We need to prove that there exist three points among these 65 that form a triangle with an area less than or equal to 172\frac{1}{72}.

2. Convex Hull and Triangulation:
For n n points in the plane, where no three points are collinear, the convex hull of these points is a polygon with k k vertices, where 3kn 3 \leq k \leq n . A complete triangulation of this convex hull results in t=2nk2 t = 2n - k - 2 triangles. The minimum number of triangles, t=n2 t = n - 2 , occurs when k=n k = n .

3. Area of Convex Hull:
Since the points are within a circle of diameter 1, the area of the convex hull is less than or equal to the area of the circle, which is π(12)2=π4\pi \left(\frac{1}{2}\right)^2 = \frac{\pi}{4}.

4. Average Area of Triangles:
If we have n n points, the convex hull can be triangulated into n2 n - 2 triangles. Therefore, the average area of each triangle in the triangulation is less than or equal to π/4n2\frac{\pi/4}{n-2}.

5. Finding the Bound:
We need to find n n such that π/4n2172\frac{\pi/4}{n-2} \leq \frac{1}{72}. Solving this inequality:
π4(n2)172 \frac{\pi}{4(n-2)} \leq \frac{1}{72}
π4(n2)72 \pi \leq \frac{4(n-2)}{72}
πn218 \pi \leq \frac{n-2}{18}
18πn2 18\pi \leq n - 2
n18π+2 n \geq 18\pi + 2
Using π3.14159\pi \approx 3.14159:
n18×3.14159+256.54862+258.54862 n \geq 18 \times 3.14159 + 2 \approx 56.54862 + 2 \approx 58.54862
Since n n must be an integer, we round up to get n59 n \geq 59 .

6. Conclusion:
For n=65 n = 65 , which is greater than 59, there must exist a triangle with an area less than or equal to 172\frac{1}{72}.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.