It is classical subject. If $ N$ points are indside unit square, how large may be the least are of triangles they form? Heilbronn conjectured that the answer is $ \mathcal{O}\left(\frac{1}{n^2}\right)$, but it turns out that it's possible that all areas are logarithmically larger. So now refined Heilbronn's conjecture is that the least area is $ \mathcal{O}(n^{\epsilon-2})$ for any $ \epsilon>0$. The best known estimate is (as I know) $ n^{\epsilon-5/4}$. As for the problem proposed, it may be solved by triangulation the convex hull of these points. There are two cases, when convex hull contains "many" points on its boundary (in this case we find a triangle with vertices on the convex hull boundary) or "not many" points, in this case triangulation has many triangles and the Pigeonhole Principle works.

What`s your meaning?Can someone give a solusion more clear

Let the convex hull of our $ (n+1)^2$ points be a $ k$-gon $ F$ for some integer $ k$. First case. $ k\ge 4n$. Then the perimetr of a polygon $ F$ does not exceed $ 4n$ (since it lies in a square with perimetr $ 4n$), hence the sum $ a+b$ of some two consecutive sides $ a$, $ b$, of $ F$ does not exceed 2, hence $ ab\le 1$ and the area of triangles with sides $ a$, $ b$ does not exceed $ 1/2$. Second case. $ k<4n$. Triangulate $ F$ onto $ k-2$ triangles (say, draw all diagonals from some specific vertex). Then mark one by one all other $ (n+1)^2-k$ points inside $ F$ and for each of them join it with the vertices of triangle, into which it is situated on the step. So, we get $ k-2+2((n+1)^2-k)=2n^2+4n-k>2n^2$ triangles in our triangulation, hence the area of one of them does not exceed $ 1/2$.

See here. There are some remarks about that problem.

Note that in a unit square, any 3 points determine a triangle with area at most $\frac{1}{2}$. This is because if any of the 3 points is not at a corner of the square, we can always move that point to one of the corners such that the area is not decreased. Thus we can assume that each of the 3 points is at a corner of the square and calculate that the area is at most $\frac{1}{2}$. We conclude that the problem statement is trivial for $n = 1$. We will now prove the problem statement for $n \ge 2$. Assume for the sake of contradiction that every 3 points determine a triangle with area greater than $\frac{1}{2}$. Clearly, no 3 points are collinear. Let $\mathcal{P}$ be the convex hull of the interior points and let $k$ be the number of vertices of $\mathcal{P}$. We will prove an upper bound and a lower bound for $k$ that have no intersection, thus providing our desired contradiction. Let $V_1, V_2, \cdots, V_k$ be the vertices of $\mathcal{P}$, in that order, and let $\theta_i$ denote $\angle V_{i-1}V_iV_{i+1}$ for each $i$. Let $a_i$ denote the length of side $V_iV_{i+1}$, for each $i$. Note that for each $i$, triangle $V_{i-1}V_iV_{i+1}$ has area strictly greater than $\frac{1}{2}$. But this is equivalent to \[a_{i-1}a_i \sin \theta_i>1.\]Since $\sin x < x$ for all $x > 0$, we have $a_{i-1}a_i\theta_i > 1$, implying \[\theta_i > \frac{1}{a_{i-1}a_i}.\]Noting that the sum of the $\theta_i$'s is $2\pi$, we sum over $i$ to get \[ 2\pi > \sum_i \frac{1}{a_{i-1}a_i}. \] Now we rewrite this as \[\frac{k}{2\pi} < \frac{k}{\sum_i \frac{1}{a_{i-1}a_i}}\]and use AM-GM-HM to conclude that \[\frac{k}{2\pi} < (a_1a_2\cdots a_k)^{2/k} \le (\frac{a_1+a_2 +\cdots + a_k}{k})^2. \]Thus \[a_1 + a_2 + \cdots + a_k > \frac{k\sqrt{k}}{\sqrt{2\pi}}.\] Note that the perimeter of $\mathcal{P}$, which is $a_1 + a_2 + \cdots + a_k$, is at most the perimeter of the square of side length $n$. Thus \[a_1 + a_2 + \cdots + a_k \le 4n.\]Putting this together, we conclude that \[\frac{k\sqrt{k}}{\sqrt{2\pi}} < 4n,\]or equivalently \[k < \sqrt[3]{32\pi n^2}.\]This is our upper bound on $k$. Now let $r$ be the number of points inside $\mathcal{P}$; i.e. $r = (n+1)^2 - k$. It's easy to prove by induction that we can partition $\mathcal{P}$ into $k+2r-2$ triangles such that the vertices of the triangles are points and such that no point is inside any triangle. Doing this, we conclude that the area of $\mathcal{P}$ is greater than \[\frac{k+2r-2}{2} = \frac{2(n+1)^2-k-2}{2} = (n+1)^2 - 1 - \frac{k}{2} = n^2 + 2n - \frac{k}{2}.\]It's also clear that the area of $\mathcal{P}$ is at most the area of the square; i.e. \[n^2 + 2n - \frac{k}{2} < n^2.\]Thus \[k > 4n.\]This is our lower bound on $k$. Putting the two bounds together, we conclude that \[4n < \sqrt[3]{32 \pi n^2}\]and thus \[64n^3 < 32\pi n^2,\]implying \[2n < \pi,\]contradicting $n \ge 2$. This is our desired contradiction and we are done. $\blacksquare$ Note This proof shows that the $(n+1)^2$ figure can be improved to $n^2 + \sqrt[3]{4\pi n^2} + 1$.

Clearly, if any 3 points are collinear, they form a degenerate triangle, implying the result. Thus we assume that no three points are collinear. We use the following lemma: Consider a polygon (convex or not) with $x$ vertices and $y$ points inside it, and a triangulation with the vertices of the triangles the $x+y$ points. Then there are $2y+x-2$ triangles in the triangulation. We double count the total sum of angles of triangles. Denote by $T$ the number of triangles in the triangulation. The sum of angles of all of them is clearly $T\pi$. On the other hand, the angles around each of the interior points add up to $2\pi$, while the angles around the $n$ points of the polygon add up to the sum of interior angles of the polygon, that is, $(n-2)\pi$. It follows that: $$T\pi=2m\pi+(n-2)\pi\implies T = 2m+n-2.$$ Consider the convex hull of the $(n+1)^{2}$ points in the square. This will be a convex polygon with, say, $k$ vertices, $3 \leq k \leq(n+1)^{2}$. Thus the area of the convex hull is at most $n^{2}$. This along with our lemma our claim for $x=k, y=(n+1)^{2}-k$ gives that there exists a triangle with area at most $$\frac{n^{2}}{-k-2+2(n+1)^{2}}=\frac{n^{2}}{2 n^{2}+4 n-k}.$$Consider the perimeter of the convex hull. This is at most $4n$. Now consider a triangle with sides on the hull, say $l_1$ and $l_2$. These must be consecutive. Then the area is at least $$\textrm{Area}=\frac{1}{2} l_{1} l_{2} \sin \left(\angle l_{1} l_{2}\right) \leqslant \frac{1}{2} l_{1} l_{2} \overset{AM-GM}{\leqslant} \frac{1}{2}\left(\frac{l_{1}+l_{2}}{2}\right)^{2} \leq \frac{(4 n)^{2}}{k^{2}} \cdot \frac{1}{2}=\frac{8 n^{2}}{k^{2}}.$$Combining the two we get $$\frac{8 n^{2}}{k^{2}} \leqslant \frac{n^{2}}{2 n^{2}+4 n-k} \Leftrightarrow \frac{k-4 n}{n-2 n(n+2)} \leqslant 0.$$As $k<2 n(n+2) \implies k \geqslant 4 n$. Setting $k=4n$, both bounds give $\frac{1}{2}$ which is the required bound.

Construct the convex hull of the $(n+1)^2$ points. Suppose $k$ of the $(n+1)^2$ points are on the convex hull. It's well-known that the convex hull must have perimeter less than $4n$ because it's inside a square with perimeter $4n$. If $k\ge 4n$, we can find two adjacent sides of the convex hull which sum to less than $2$, because if not we would get a perimeter of $\ge 4n$. Let these two sides be $AB$ and $BC$. Then $[\triangle ABC]=\frac{1}{2}(AB)(BC)\sin \angle ABC\le \frac{1}{2}\left(\frac{AB+BC}{2}\right)^2\sin\angle ABC\le \frac{1}{2}$ by the sine area formula and AM-GM. Otherwise, if $k<4n$, we triangulate the convex hull, then form disjoint (besides sharing a side) triangles with the points not on the convex hull. All in all, $k-2+2(n+1)^2-2k=2(n+1)^2-k-2>2(n+1)^2-4n-2=2n^2$ triangles have been formed. Since the triangles all together have area $\le n^2$, we get there must be at least one triangle with area at most $\frac12$, and we are done.

Solution from Twitch Solves ISL: Assume no $3$ points are collinear (else they are area $0$). Suppose the convex hull of our polygon has $k \ge 3$ points. We consider two cases. First case: $k \le 4n$ If $k \le 4n$, we use the following algorithm: draw the entire convex hull, and then repeatedly draw non-intersecting segments between pairs of points. The end result is a division of the $k$-gon into triangles. By double-counting interior angles, the number of triangles is given exactly by \[ \frac{360^{\circ} \cdot \left( (n+1)^2-k \right) + 180^{\circ} \cdot (k-2)}{180^{\circ}} = 2n^2 + 4n - k \ge 2n^2. \]The sum of the areas of the triangles is at most $n^2$ (the total area of the square), so we're done. Second case: $k \ge 4n$ We will show that we can take some three consecutive vertices of the convex hull. Let $a_1$, \dots, $a_k$ be the side lengths of the convex hull in order. A convex polygon contained inside a square of side length $n$ has perimeter at most $4n$, so we have $a_1 + \dots + a_k \le 4n$. Using the lemma with $k \ge 4n$, there should be an index $i$ with $a_i + a_{i+1} \le 2$. It follows that $a_i a_{i+1} \le 1$ for some index $i$ by AM-GM. The two associated sides then carve out a triangle of area at most $\frac{1}{2}$.

Suppose no three points are collinear, else the problem is obvious. Let the convex hull of the points contain $k$ vertices. It is well-known that if a convex hull completely contains another, the perimeter of the smaller hull is at most that of the larger. Thus if $k \geq 4n$ the convex hull has perimeter at most $4n$, so there should be some two consecutive edges whose lengths sum to at most $2$, hence have a product of at most $1$. The triangle with these edges as sides thus has area at most $\tfrac{1}{2}$. If $k \leq 4n$, we divide the convex hull into triangles as follows: first ignore the interior points, and triangulate the convex hull into $k-2$ triangles. Then, reintroduce one point at a time. Each point should lie strictly inside exactly one pre-existing triangle; draw the segments connecting the point to its vertices, increasing the number of triangles by $2$. Thus we have a total of $(k-2)+2((n+1)^2-k)=2n^2+4n-2 \geq 2n^2$ triangles, none of which overlap, hence some has area at most $\tfrac{1}{2}$. This finishes the problem. $\blacksquare$

Fedor Petrov wrote: It is classical subject. If $ N$ points are indside unit square, how large may be the least are of triangles they form? Heilbronn conjectured that the answer is $ \mathcal{O}\left(\frac{1}{n^2}\right)$, but it turns out that it's possible that all areas are logarithmically larger. So now refined Heilbronn's conjecture is that the least area is $ \mathcal{O}(n^{\epsilon-2})$ for any $ \epsilon>0$. The best known estimate is (as I know) $ n^{\epsilon-5/4}$. As for the problem proposed, it may be solved by triangulation the convex hull of these points. There are two cases, when convex hull contains "many" points on its boundary (in this case we find a triangle with vertices on the convex hull boundary) or "not many" points, in this case triangulation has many triangles and the Pigeonhole Principle works. Update but the best known estimate is now $n^{-\frac{8}{7} - \frac{1}{2000}}$ btw.

Suppose the convex hull of the $(n+1)^2$ points has $k$ points. If $k > 4n$, then let the vertices of the convex hull $\mathcal P$ be $A_1, A_2, \dots, A_k$ and consider triangles of the form $A_iA_{i+1}A_{i+2}$. The product of the areas of these triangles is equal to $$\prod_{i=1}^k [A_iA_{i+1}A_{i+2}] \leq \frac 1{2^k} \prod_{i=1}^k (P_iP_{i+1})^2 \leq \frac {P(\mathcal P)^{2k}}{(2k^2)^k} < \left(\frac{16n^2}{2k^2}\right)^k < \left(\frac 12\right)^k$$because the perimeter of $\mathcal P$ is at most $4n$ by convexity. Hence one of these triangles has area at most $\frac 12$. If $k \leq 4n$, then we perform a triangulation of the $k$-gon into $k-2$ triangles. Every one of the remaining $n^2+2n+1-k$ points must belong in one of the triangles; thus, when we incorporate it into the triangulation, we create exactly $2$ more triangles. Upon complete triangulation, there are $$k-2+2(n^2+2n-k+1) = 2n^2+4n-k \geq 2n^2$$triangles that cover an area of at most $n^2$. Hence one of these triangles has area at most $\frac 12$ again. Remark: We omitted the $\sin(\angle A_iA_{i+1}A_{i+2})$'s in our computation for the first part. If we include them, we actually get a better bound of $\frac{16\pi \cdot n^2}{k^3}$, but this is not necessary (or entirely that helpful either) for the problem in question.

This problem is so nice :0 Consider the Convex Hull of our $(n+1)^2$ points, call it $\mathcal{X}$, with area $[\mathcal{X}]$. Suppose that this convex hull contains $k$ vertices, call them $A_1$, $A_2$, $\dots$, $A_k$. Now consider a point $I$ inside $\mathcal{X}$, note that by AM-GM $$\sqrt[k]{[IA_1A_2]\cdot[IA_2A_3]\cdots[IA_{k-1}A_k] \cdot [I A_k A_1]} \le \frac{[\mathcal{X}]}{k} \le \frac{n^2}{k}$$So by the averaging principal there exists $A_i$, $A_{i+1}$ such that $[IA_{i}A_{i+1}] \le \frac{n^2}{k}$, thus if $k \ge 4n$ we are finished. So now suppose $k < 4n$, triangulate the convex hull into $k-2$ triangles. Then every other point must lie in one of these triangles, triangulate these points one at a time, into the drawn triangles they are in. Each new point contributes $2$ new triangles, so we have a total of $k-2+2(n^2+2n+1-k)= 2n^2+4n-k$, so by pigeonhole there will exist a triangle with area at most $\frac{n^2}{2n^2+4n-k} $ which is less than $\frac{1}{2}$ if $k < 4n$. Thus we can conclude.

Assume no three points collinear as then it is trivial. Suppose the convex hull has $\ge 4n$ points. Then its perimeter is $\le 4n$ (e.g. project onto sides and triangle inequality) so by pigeonhole there are two consecutive sides of the hull summing to $\le 2.$ Now by AM-GM the triangle with these two sides has area at most $\tfrac12.$ Suppose the convex hull has $k \le 4n$ points. Triangulate it using the $(n+1)^2$ points. Then all points in the interior count for $360^\circ,$ or two triangles, and the convex hull counts $180(k-2),$ or $k-2$ triangles, thus a total of $2(n+1)^2-k-2=2n^2+4n-k\ge 2n^2.$ Then pigeonhole gives at least one of these with area at most $\tfrac12.$