30th IMO 1989 shortlist Problem 14 Given 7 points in the plane, how many segments (each joining two points) are needed so that given any three points at least two have a segment joining them? Solution
: 9. 9 is obviously sufficient. Take points A, B, C and P, Q, R, S with segments AB, BC, CA, and PQ, PR, PS, QR, QS, RS. If the three points are A, B, C or three of P, Q, R, S, then they are all joined. Any other three points must include either two from A, B, C (which will be joined) or two from P, Q, R, S (which will be joined). Now suppose we have only 8 points. Suppose that we cannot find three points without a segment between them. If every point is joined to at least three others, then there are at least 7.3/2 segments. Contradiction. So there is a point A which is not joined to any of B, C, D, E. If two of B, C, D, E are not joined, then with A they form three points with no segments. Contradiction. So there are 6 segments between B, C, D, E. Let the remaining two points be X, Y. Two of the points A, X, Y cannot be joined (because there are only 2 segments available outside B, C, D, E). One of the points B, C, D, E cannot be joined to either of these two points (since there are at most 2 segments available), so we have three points with no segments. Contradiction. 30th IMO shortlist 1989 © John Scholes jscholes@kalva.demon.co.uk 28 Dec 2002 Last corrected/updated 28 Dec 02