In a circle of diameter consider 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 .
Problem 1410
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 .
2. Convex Hull and Triangulation:
For points in the plane, where no three points are collinear, the convex hull of these points is a polygon with vertices, where . A complete triangulation of this convex hull results in triangles. The minimum number of triangles, , occurs when .
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 .
4. Average Area of Triangles:
If we have points, the convex hull can be triangulated into triangles. Therefore, the average area of each triangle in the triangulation is less than or equal to .
5. Finding the Bound:
We need to find such that . Solving this inequality:
Using :
Since must be an integer, we round up to get .
6. Conclusion:
For , which is greater than 59, there must exist a triangle with an area less than or equal to .