Maths Olympiad Prep

Library / /22 of 39

Geometry Difficulty 5.5 AIME, harder Prove it Ireland

Let SS be a set of nn different points in the plane so that no three lie on a line. Show that there are at least n(n2)3\frac{n(n-2)}{3} triangles whose vertices are among the points of SS and such that the triangles do not contain any other points of SS.

Solution

Choose two points XX and YY from SS, and consider the half plane hh with boundary the line XYXY, and containing at least one other point of SS. Now select a point ZZ of SS in the interior of hh whose distance from the line XYXY is a minimum. If there are several such points, choose an arbitrary one.

Now claim that the triangle XYZXYZ does not contain any other point of SS, apart from XX, YY, and ZZ. Suppose there is a point ASA \in S which is in the interior of the triangle XYZXYZ. Then area(AXY)<area(ZXY)\operatorname{area}(AXY) < \operatorname{area}(ZXY) and so the altitude from AA of the triangle AXYAXY is less than the altitude from ZZ of the triangle ZXYZXY. This contradicts the choice of ZZ.

Suppose that there are kk pairs (X,Y)(X, Y) of points in SS with the property that the whole of the set SS lies in one of the two half planes with boundary the line XYXY. Such pairs are adjacent vertices of the convex hull of SS and so knk \le n. For each of these pairs (X,Y)(X, Y) we have shown that there is at least one triangle XYZ,ZSXYZ, Z \in S, which is “empty”, that is it does not contain any of the remaining n3n-3 points of SS.

The remaining (n2)k\binom{n}{2} - k pairs (X,Y)(X, Y) have the property that there are at least two “empty” triangles XYZ,ZSXYZ, Z \in S. Now sum all these triangles over all the pairs (X,Y)(X, Y) and we get in all
k+2((n2)k)=n(n1)kn(n1)n=n(n2) k + 2 \left( \binom{n}{2} - k \right) = n(n-1) - k \geq n(n-1) - n = n(n-2)
such triangles. Each is counted at most three times so the number of “empty” triangles is at least n(n2)3\frac{n(n-2)}{3}.

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 and solution reproduced as published; topic and difficulty added by this site.