IMO 1989 SL 17

Origin: MON

Problem

Given seven points in the plane, some of them are connected by segments so that: (i) among any three of the given points, two are connected by a segment; (i) the number of segments is minimal. How many segments does a figure satisfying (i) and (ii) contain? Give an example of such a figure.

Solution

A figure consisting of 9 lines is shown below. b b b b b b b

H H H HHHHHH

@ @ @

Now we show that 8 lines are not sufficient. Assume the opposite. By the pigeonhole principle, there is a vertex, say A, that is joined to at most 2 other vertices. Let B, C, D, E denote the vertices to which A is not joined, and F, G the other two vertices. Then any two vertices of B, C, D, E must be mutually joined for an edge to exist within the triangle these two points form with A. This accounts for 6 segments. Since only two segments remain, among A, F, and G at least two are not joined. Taking these two and one of B, C, D, E that is not joined to any of them (it obviously exists), we get a triple of points, no two of which are joined; a contradiction. Second solution. Since (a) is equivalent to the fact that no three points make a “blank triangle,” by Turan’s theorem the number of “blank edges” cannot exceed [72/4] = 12, leaving at least 7 \cdot 6/2 −12 = 9 segments. For general n, the answer is [(n −1)/2]2.