Proving Triangle Area ≤ $\frac{1}{2}$ in a Square with $(n+1)^2$ Points

[Adele06]

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:https://math.stackexchange.com/q/173333

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 principle 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?

 

[jvicens]

Sure, let's consider the case $n=3$. In this case, we have a square with side length 3 and 16 points inside it. We can divide the square into 9 smaller squares, each with side length 1. By pigeonhole principle, at least one of these squares will contain at least 3 points. Let's call this square $S$. Now, we have 9 points inside $S$ and we need to choose 3 of them to determine a triangle with area at most $\frac{1}{2}$.

One way to approach this is to consider the points on the boundary of $S$. There are 12 points on the boundary, and we can choose any 3 of them to form a triangle with area at most $\frac{1}{2}$. This is because the area of a triangle is given by the formula $\frac{1}{2}bh$, where $b$ is the base and $h$ is the height. Since the base and height are both 1 in this case, the area of the triangle will be at most $\frac{1}{2}$.

So, we have 12 points on the boundary of $S$ that we can choose from. This leaves us with 9 points inside $S$ that we can choose from. Using the same argument as in the case $n=2$, we can divide $S$ into 4 smaller squares, each with side length $\frac{1}{2}$. By pigeonhole principle, at least one of these squares will contain at least 3 points. We can then use the same proof as in the case $n=1$ to show that these 3 points determine a triangle with area at most $\frac{1}{2}$.

So, in total, we have chosen 3 points from the boundary of $S$ and 3 points from inside $S$ to form a triangle with area at most $\frac{1}{2}$. Thus, we have shown that for $n=3$, we can choose 3 points to determine a triangle with area at most $\frac{1}{2}$.

You can follow a similar approach for other values of $n$ as well. The key is to use the pigeonhole principle to divide the square into smaller squares and then use the same proof as in the case $n=1$ to show that the 3 points chosen from