Suppose points in a plane are given such that no three points are collinear. Among the triangles formed by any three of these points, those triangles having the largest area are said to be good. Prove that there cannot be more than good triangles.
Solution
We shall prove the assertion for any positive integer when is replaced by .
Claim 1. If the points lie inside or on the boundary of a polygon , then does not exceed the area of one of the triangles formed by the vertices of . When equality holds, must lie on the boundary of .
Proof. If lies in the interior of , we can move away from the line in the direction perpendicular to until lies on the boundary of . The area is increased. In the same way, we may assume lie on the boundary of . Next, suppose lies on the side where and are vertices of . WLOG assume the distance from to is at least that from to . Then and we can move to . Similarly, we can move all three points to some vertices of . The area is no less than the original .
Let be the convex hull of the points. Using claim 1, all points inside cannot form a good triangle. WLOG we may assume the given points form the convex -gon .
Claim 2. Let be a convex pentagon. If both and are good triangles where , then these triangles must be and .

Proof. Suppose and are good triangles. As , we have . Similarly, as , we have . These yield , which is impossible.
Suppose and are good triangles. As , we have . Since , we have . This implies , which contradicts the former inequality.
The only possibility is the one we claim.
Claim 3. Suppose and are good. Construct such that is the medial triangle of . Then the points must lie in the regions II, III, IV as shown and no two of them lie in the same region.


Proof. Firstly, if lies on different sides of as , then . Thus cannot be good. In the same way, all of must lie in . By our assumption on the points, none of can lie inside , which is region I. If all of lie in the same region, say II, then . This contradicts .
WLOG, it remains to consider the case when lie in region II and lies in region III. WLOG assume is convex and the points lie in this order. Since , we have . But this cannot be true. Indeed, let and meet the line at and respectively. In view of the configuration, must lie in that order. We find that

This shows no two of can lie in the same region as desired.
Suppose the vertices of are in that order. Suppose there are good triangles where . WLOG, the indices can be rearranged in dictionary order. This means . If , then . If and , then .
Claim 4. We have
Proof. The relation follows from the construction. Next, to show that , we first assume on the contrary that for some . Note that by construction. Then are distinct and lie in that order. No matter equals or not, claim 2 or claim 3 is violated.
Next, to show , we assume on the contrary that for some . If , then we must have . This contradicts claim 2. If , no matter equals or not, claim 2 or claim 3 is violated.
It remains to show and . For the former inequality, we first assume . If equals one of , then claim 2 is violated. If is distinct from , then claim 3 is violated. Thus, we must have . By symmetry (reversing the role of the two triangles), we obtain the latter inequality as well. This completes the proof of claim 4.
Let . By claim 4, is an increasing sequence. Note that it is strictly increasing since the good triangles are distinct. As
the sequence contains at most terms, meaning that at most good triangles are possible. This completes the proof.