Show that given any 9 points inside a square of side 1 we can always find 3 which form a triangle with area less than .
[i]Bulgaria[/i]
Problem 1221
Official solution
1. Divide the Square into Smaller Regions:
Consider a unit square with side length 1. Divide this square into 4 smaller squares, each with side length . Each of these smaller squares has an area of .
2. Pigeonhole Principle:
By the pigeonhole principle, if we place 9 points inside the unit square, at least one of the smaller squares must contain at least 3 of these points. This is because there are only 4 smaller squares and 9 points, so at least one square must contain points.
3. Area of Triangle in Smaller Square:
Consider one of these smaller squares with side length . Any triangle formed by 3 points within this smaller square will have an area less than or equal to the area of the smaller square. The maximum area of a triangle within this smaller square is achieved when the triangle is right-angled and its legs are the sides of the smaller square. The area of such a triangle is:
4. Conclusion:
Therefore, any triangle formed by 3 points within this smaller square will have an area less than or equal to . Since we have shown that at least one of the smaller squares must contain at least 3 of the 9 points, we can conclude that there always exists a triangle with an area less than or equal to .