# choosing points interior to a square

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?

-
Do you mean "...at most $n^2/2$."? – user13838 Oct 17 '11 at 16:11
You might find this discussion of interest: mathworld.wolfram.com/HeilbronnTriangleProblem.html – Joseph Malkevitch Oct 17 '11 at 16:37
@percusse, that wouldn't be interesting -- every triangle that fits within the square has area at most $n^2/2$. – Henning Makholm Oct 17 '11 at 17:32
I think you mean "possibly degenerate"? – joriki Oct 17 '11 at 20:53

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$.