3
$\begingroup$

Consider a square of sidelength $n$ and $ (n+1)^{2} $ interior points. Prove that we can choose 3 of these points so that they determine a triangle (eventually degenerated) of area at most 1/2.

I couldn't get started on this. Any ideas?

  • 0
    I think you mean "possibly degenerate"?2011-10-17

1 Answers 1

6

Form the convex hull of the points and triangulate it. If the convex hull is formed by $k$ points, its triangulation has $k-2$ triangles. (For instance, pick one vertex and connect it to all other vertices.) Then add the remaining points one by one, in each step replacing the triangle containing the new point by the three triangles formed by the new point and the three sides of the old triangle. Since $(n+1)^2-k$ points are added and the number of triangles increases by $2$ in each step, this yields a set of $k-2+2((n+1)^2-k)=2n^2+4n-k$ disjoint triangles. If $k\le4n$, the average area of these triangles is at most $n^2/(2n^2)=\frac12$, so at least one of the triangles has at most that area.

Now assume $k\gt4n$. Then the boundary of the convex hull is a polygon with at least $4n$ points, and thus at least $4n$ line segments. The total length of these line segments is at most the perimeter of the enclosing square, which is $4n$. Thus the average length of the line segments is at most $1$, and the average sum of the lengths of adjacent line segments is at most $2$. Thus, there is at least one pair of adjacent line segments whose lengths add up to at most $2$. The largest triangle that can be formed with two given sides is a right triangle with area half the product of the sides, and for a given sum of the two sides the product is maximal when the sides are equal. Thus the area of the triangle formed by the two adjacent sides with sum at most $2$ is at most $\frac12\cdot1\cdot1=\frac12$.

Thus in both cases there is at least one triangle with area at most $\frac12$.