IMO 1991 SL 8

Origin: NET

Problem

Let S be a set of n points in the plane. No three points of S are collinear. Prove that there exists a set P containing 2n −5 points satisfying the following condition: In the interior of every triangle whose three vertices are elements of S lies a point that is an element of P.

Solution

Let P1(x1, y1), P2(x2, y2), . . . , Pn(xn, yn) be the n points of S in the co- ordinate plane. We may assume x1 < x2 < \cdot \cdot \cdot < xn (choosing adequate axes and renumbering the points if necessary). Define d to be half the minimum distance of Pi from the line PjPk, where i, j, k go through all possible combinations of mutually distinct indices. First we define a set T containing 2n −4 points: T = {(xi, yi −d), (xi, yi + d) | i = 2, 3, . . ., n −1}. Consider any triangle PkPlPm, where k < l < m. Its interior contains at least one of the two points (xl, yl\pmd), so T is a set of 2n−4 points with the required property. However, at least one of the points of T is useless. The convex hull of S is a polygon with at least three points in S as vertices. Let Pj be a vertex of that hull distinct from P1 and Pn. Clearly one of the points (xj, yj \pm d) lies outside the convex hull, and thus can be left out. The remaining set of 2n −5 points satisfies the conditions.