IMO 1972 SL 2

Origin: CZS

Problem

We are given 3n points A1, A2, . . . , A3n in the plane, no three of them collinear. Prove that one can construct n disjoint triangles with vertices at the points Ai.

Solution

We use induction. For n = 1 the assertion is obvious. Assume that it is true for a positive integer n. Let A1, A2, . . . , A3n+3 be given 3n+3 points, and let w.l.o.g. A1A2 . . . Am be their convex hull. Among all the points Ai distinct from A1, A2, we choose the one, say Ak, for which the angle \angleAkA1A2 is minimal (this point is uniquely deter- mined, since no three points are collinear). The line A1Ak separates the plane into two half-planes, one of which contains A2 only, and the other one all the remaining 3n points. By the inductive hypothesis, one can con- struct n disjoint triangles with vertices in these 3n points. Together with the triangle A1A2Ak, they form the required system of disjoint triangles.