China Hong Kong Mathematical Olympiad

We shall prove the assertion for any positive integer $n$ when $2017$ is replaced by $n$.

Claim 1. If the points $X, Y, Z$ lie inside or on the boundary of a polygon $\mathcal{P}$, then $[XYZ]$ does not exceed the area of one of the triangles formed by the vertices of $\mathcal{P}$. When equality holds, $X, Y, Z$ must lie on the boundary of $\mathcal{P}$.

Proof. If $X$ lies in the interior of $\mathcal{P}$, we can move $X$ away from the line $YZ$ in the direction perpendicular to $YZ$ until $X$ lies on the boundary of $\mathcal{P}$. The area is increased. In the same way, we may assume $X, Y, Z$ lie on the boundary of $\mathcal{P}$. Next, suppose $X$ lies on the side $PQ$ where $P$ and $Q$ are vertices of $\mathcal{P}$. WLOG assume the distance from $P$ to $YZ$ is at least that from $X$ to $YZ$. Then $[PYZ] \ge [XYZ]$ and we can move $X$ to $P$. Similarly, we can move all three points to some vertices of $\mathcal{P}$. The area is no less than the original $[XYZ]$. $\square$

Let $\mathcal{P}$ be the convex hull of the $n$ points. Using claim 1, all points inside $\mathcal{P}$ cannot form a good triangle. WLOG we may assume the $n$ given points form the convex $n$-gon $\mathcal{P}$.

Claim 2. Let $ABCDE$ be a convex pentagon. If both $\triangle AWX$ and $\triangle AYZ$ are good triangles where $\{W, X, Y, Z\} = \{B, C, D, E\}$, then these triangles must be $\triangle ABD$ and $\triangle ACE$.

Proof. Suppose $\triangle ABC$ and $\triangle ADE$ are good triangles. As $[ABC] \ge [ABD]$, we have $\angle B + \angle C \le 180^\circ$. Similarly, as $[ADE] \ge [ACE]$, we have $\angle D + \angle E \le 180^\circ$. These yield $\angle A \ge 180^\circ$, which is impossible.

Suppose $\triangle ABE$ and $\triangle ACD$ are good triangles. As $[ABE] \ge [ACE]$, we have $\angle A + \angle B \le 180^\circ$. Since $[ACD] \ge [ABD]$, we have $\angle B + \angle BAD \ge 180^\circ$. This implies $\angle B + \angle A > 180^\circ$, which contradicts the former inequality.

The only possibility is the one we claim. $\square$

Claim 3. Suppose $\triangle ABC$ and $\triangle XYZ$ are good. Construct $\triangle A'B'C'$ such that $\triangle ABC$ is the medial triangle of $\triangle A'B'C'$. Then the points $X, Y, Z$ must lie in the regions II, III, IV as shown and no two of them lie in the same region.

Proof. Firstly, if $X$ lies on different sides of $B'C'$ as $B$, then $[XBC] > [ABC]$. Thus $\triangle ABC$ cannot be good. In the same way, all of $X, Y, Z$ must lie in $\triangle A'B'C'$. By our assumption on the $n$ points, none of $X, Y, Z$ can lie inside $\triangle ABC$, which is region I. If all of $X, Y, Z$ lie in the same region, say II, then $[XYZ] < [ABC'] = [ABC]$. This contradicts $[XYZ] = [ABC]$.

WLOG, it remains to consider the case when $X, Y$ lie in region II and $Z$ lies in region III. WLOG assume $AXYB$ is convex and the points lie in this order. Since $[XYZ] \ge [XBZ]$, we have $\angle ZXY + \angle XYB \le 180^\circ$. But this cannot be true. Indeed, let $ZX$ and $XY$ meet the line $C'A'$ at $P$ and $Q$ respectively. In view of the configuration, $P, Q, B$ must lie in that order. We find that
$$\angle ZXY + \angle XYB \ge \angle ZXQ + \angle XQB = 180^\circ + \angle ZPB > 180^\circ.$$

This shows no two of $X, Y, Z$ can lie in the same region as desired. $\square$

Suppose the vertices of $\mathcal{P}$ are $A_1, A_2, \dots, A_n$ in that order. Suppose there are $m$ good triangles $A_{a_i}A_{b_i}A_{c_i}$ where $a_i < b_i < c_i$. WLOG, the indices can be rearranged in dictionary order. This means $a_1 \le a_2 \le \dots \le a_m$. If $a_i = a_{i+1}$, then $b_i \le b_{i+1}$. If $a_i = a_{i+1}$ and $b_i = b_{i+1}$, then $c_i < c_{i+1}$.

Claim 4. We have
$$a_1 \le a_2 \le \dots \le a_m \le b_1 \le b_2 \le \dots \le b_m \le c_1 \le c_2 \le \dots \le c_m.$$
Proof. The relation $a_1 \le a_2 \le \dots \le a_m$ follows from the construction. Next, to show that $b_1 \le b_2 \le \dots \le b_m$, we first assume on the contrary that $b_i > b_{i+1}$ for some $i$. Note that $a_i \ne a_{i+1}$ by construction. Then $A_{a_i}, A_{a_{i+1}}, A_{b_{i+1}}, A_{b_i}$ are distinct and lie in that order. No matter $A_{c_i}$ equals $A_{c_{i+1}}$ or not, claim 2 or claim 3 is violated.

Next, to show $c_1 \le c_2 \le \dots \le c_m$, we assume on the contrary that $c_i > c_{i+1}$ for some $i$. If $a_i = a_{i+1}$, then we must have $b_i < b_{i+1}$. This contradicts claim 2. If $a_i < a_{i+1}$, no matter $A_{b_i}$ equals $A_{b_{i+1}}$ or not, claim 2 or claim 3 is violated.

It remains to show $a_m \le b_1$ and $b_m \le c_1$. For the former inequality, we first assume $a_m > b_1$. If $c_1$ equals one of $a_m, b_m, c_m$, then claim 2 is violated. If $c_1$ is distinct from $a_m, b_m, c_m$, then claim 3 is violated. Thus, we must have $a_m \le b_1$. By symmetry (reversing the role of the two triangles), we obtain the latter inequality $b_m \le c_1$ as well. This completes the proof of claim 4. $\square$

Let $s_i = a_i + b_i + c_i$. By claim 4, $\{s_i\}$ is an increasing sequence. Note that it is strictly increasing since the good triangles are distinct. As
$$s_m - s_1 = c_m + (b_m - c_1) + (a_m - b_1) - a_1 \le n + 0 + 0 - 1 = n - 1,$$
the sequence contains at most $n$ terms, meaning that at most $n$ good triangles are possible. This completes the proof.