Maths Olympiad Prep

Library / /73 of 94

Geometry Difficulty 6.7 National Olympiad Prove it Hong Kong

Suppose 20172017 points in a plane are given such that no three points are collinear. Among the triangles formed by any three of these 20172017 points, those triangles having the largest area are said to be good. Prove that there cannot be more than 20172017 good triangles.

Solution

We shall prove the assertion for any positive integer nn when 20172017 is replaced by nn.

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

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

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

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

Figure 1

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

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

The only possibility is the one we claim. \square

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

Figure 2
Figure 3

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

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

Figure 4

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

Suppose the vertices of P\mathcal{P} are A1,A2,,AnA_1, A_2, \dots, A_n in that order. Suppose there are mm good triangles AaiAbiAciA_{a_i}A_{b_i}A_{c_i} where ai<bi<cia_i < b_i < c_i. WLOG, the indices can be rearranged in dictionary order. This means a1a2ama_1 \le a_2 \le \dots \le a_m. If ai=ai+1a_i = a_{i+1}, then bibi+1b_i \le b_{i+1}. If ai=ai+1a_i = a_{i+1} and bi=bi+1b_i = b_{i+1}, then ci<ci+1c_i < c_{i+1}.

Claim 4. We have
a1a2amb1b2bmc1c2cm. 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 a1a2ama_1 \le a_2 \le \dots \le a_m follows from the construction. Next, to show that b1b2bmb_1 \le b_2 \le \dots \le b_m, we first assume on the contrary that bi>bi+1b_i > b_{i+1} for some ii. Note that aiai+1a_i \ne a_{i+1} by construction. Then Aai,Aai+1,Abi+1,AbiA_{a_i}, A_{a_{i+1}}, A_{b_{i+1}}, A_{b_i} are distinct and lie in that order. No matter AciA_{c_i} equals Aci+1A_{c_{i+1}} or not, claim 2 or claim 3 is violated.

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

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

Let si=ai+bi+cis_i = a_i + b_i + c_i. By claim 4, {si}\{s_i\} is an increasing sequence. Note that it is strictly increasing since the good triangles are distinct. As
sms1=cm+(bmc1)+(amb1)a1n+0+01=n1, 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 nn terms, meaning that at most nn good triangles are possible. This completes the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.