Prove that number of triangles formed with area $1$ and vertices chosen from $n$ points (no $3$ are collinear) is not greater than $2(n^2-n) /3$

Question

There are $n$ points in a plane of which no $3$ are collinear. Prove that the number of triangles whose vertices are chosen from $n$ points and whose area is $1$ is not greater than $2(n^2-n)/3$. The bound can be simplified by ${1\over3} \cdot(2+2)$ multiplied by $n\choose 2$. I have tried by the Pigeonhole Principle but that didn't help. Can anyone suggest me an alternate method? Or how can I prove it by the Pigeonhole principle? Any help would be appreciated.

Answer 1

I found this question listed in AoPS as 2010 Iran MO Round 2 P2. I could not find any solutions there. So, here is this answer which becomes obvious once you see the meaning behind the given bound. Since the solution is not difficult, I'll instead walk you through my reasoning as I went.

1. There must be something about $\frac{2(n^2-n)}{3}$. Since it is not obvious, let's factorize this.
2. Okay, we have $\frac23 n(n-1)$. Not that helpful unless you have seen the expression for the number of line segments made by $n$ points of which no $3$ are collinear. That is $n(n-1)/2$. (Since I applied it after a long time, I had forgotten the 'divide by $2$' part while I was trying to solve it, but thanks to @MikeEarnest I corrected my error.) I'll try to explain why this is so in short. A line segment has $2$ endpoints. You can choose the first endpoint in $n$ ways, and the second one in $n-1$ ways. So you multiply them to get the total line segments. But the trouble is, you've counted every line segment twice ($AB$ is the same as $BA$), so you divide by $2$.
3. Now we have reasoned out that this expression is a multiple of the number of possible line segments, precisely, $\frac{4}{3}$ times $\frac{n(n-1)}{2}$. We need to figure out why we have $4/3$. Our inequality is completely based on counting the maximum number of triangles with area of $1$, so maybe we divide by $3$ to account for counting every triangle thrice.
4. The $4$ cannot be understood unless you get to the solving problem itself by using the reasoning of why the expression is as it is.

Let $k_n$ be the maximal number of triangles formed by $n$ points which are arranged in the most optimal way. Throughout this answer, we will only try to find the maximum value of $k_n$.
Suppose you choose any line segment (can be done in $n(n-1)/2$ ways). This line segment will have some arbitrary length, say $l$. If this segment is the base (that is, one of the sides) of a required triangle, we can find the height $h$: $$0.5lh = 1 \implies h = \frac2l$$ This height may vary for segment to segment. Suppose there are $4$ points at a distance of $2/l$ from the segment (by the Pigeonhole principle, you have $2$ holes on either side of the line, and each hole can accommodate $2$ points, or pigeons at max because a third point at the same distance on the same side of the line would make $3$ points collinear). This is the maximal case: you can form $4$ required triangles from each line segment. So, you have $4n(n-1)/2 = 2n(n-1)$ required triangles. But, you have counted every triangle thrice (you must have taken all three sides of the triangle as bases while choosing the base), so divide by $3$ to get the final expression: $$\frac{2n(n-1)}{3}$$Thus, $$\color{green}{k_n \le \frac{2(n^2-n)}{3}}$$ QED.