IMO 1991 SL 9

Origin: FRA

Problem

In the plane we are given a set E of 1991 points, and certain pairs of these points are joined with a path. We suppose that for every point of E, there exist at least 1593 other points of E to which it is joined by a path. Show that there exist six points of E every pair of which are joined by a path. Alternative version. Is it possible to find a set E of 1991 points in the plane and paths joining certain pairs of the points in E such that every point of E is joined with a path to at least 1592 other points of E, and in every subset of six points of E there exist at least two points that are not joined?

Solution

Let A1, A2 be two points of E which are joined. In E \ {A1, A2}, there are at most 397 points to which A1 is not joined, and at most as much to which A2 is not joined. Consequently, there exists a point A3 which is joined to both A1 and A2. There are at most 3 \cdot 397 = 1191 points of E \ {A1, A2, A3} to which at least one of A1, A2, A3 is not joined, hence it is possible to choose a point A4 joined to A1, A2, A3. Similarly, there exists a point A5 which is joined to all A1, A2, A3, A4. Finally, among the remaining 1986 points, there are at most 5 \cdot 397 = 1985 which are not joined to one of the points A1, . . . , A5. Thus there is at least one point A6 joined to all A1, . . . , A5. It is clear that A1, . . . , A6 are pairwise joined. Solution of the alternative version. Let be given 1991 points instead. Number the points from 1 to 1991, and join i and j if and only if i −j is not a multiple of 5. Then each i is joined to 1592 or 1593 other points, and obviously among any six points there are two which are not joined.