Consider a square with the side of length n and $(n+1)^2$ points inside it. Show that we can choose 3 of them to determine a triangle (possibly degenerate) of area at most $\frac{1}{2}$.

I think that I know how to solve the problem for the cases $n=1$ and $n=2$:

For $n=1$ we can easily prove that the triangle formed by those 3 points has the area at most $\frac{1}{2}$,like here:Maximum area of a triangle in a square

For $n=2$ we can divide the square into 4 smaller squares (by uniting the midpoints of the opposite sides),each of them with the length of the side equal to 1.By pigeonhole priciple we know that at least one of those squares contains at least 3 of the 9 points inside it.From here we can use the same proof from the case $n=1$ to prove that those 3 points determine a triangle of area at most $\frac{1}{2}$

This idea doesn't work for the other cases because we would need $2n^2+1$ points instead of $(n+1)^2$

Can you help me please with the other cases? Source:book:Combinatorics Advances,by Charles J. Colbourn


1 Answer 1


The idea is to consider the convex hull $C$ of the $(n+1)^2$ points, and split into cases depending on whether $C$ has "many" or "few" points.

If $C$ has at least $4n$ points, then as the perimeter of $C$ is at most $4n$, we can find two adjacent sides whose total length is at most $2$. These two sides determine a triangle of area at most $\frac{1}{2}$.

Else $C$ has $k<4n$ points. Triangulate $C$ into $k-2$ triangles, then iteratively triangulate these triangles via the other $(n+1)^2-k$ points. We have split $C$ into $k-2+2\left[(n+1)^2-k\right]>2n^2$ triangles, so one of them has area at most $\frac{1}{2}$.

  • $\begingroup$ Very nice solution.I thought about the convex hull too but I didn't know how to solve the first case so I tought that my idea was wrong. $\endgroup$
    – alien2003
    Dec 26, 2020 at 15:51

Not the answer you're looking for? Browse other questions tagged .