IMO 1998 SL 27

Origin: BLR

Problem

Ten points such that no three of them lie on a line are marked in the plane. Each pair of points is connected with a segment. Each of these segments is painted with one of k colors in such a way that for any k of the ten points, there are k segments each joining two of them with no two being painted the same color. Determine all integers k, 1 \leqk \leq10, for which this is possible.

Solution

Since this is essentially a graph problem, we call the points and segments vertices and edges of the graph. We first prove that the task is impossible if k \leq4. Cases k \leq2 are trivial. If k = 3, then among the edges from a vertex A there are two of the same color, say AB and AC, so we don’t have all the three colors among the edges joining A, B, C. Now let k = 4, and assume that there is a desired coloring. Consider the edges incident with a vertex A. At least three of them have the same color, say blue. Suppose that four of them, AB, AC, AD, AE, are blue. There is a blue edge, say BC, among the ones joining B, C, D, E. Then four of the edges joining A, B, C, D are blue, and we cannot complete the coloring. So, exactly three edges from A are blue: AB, AC, AD. Also, of the edges connecting any three of the 6 vertices other than A, B, C, D, one is blue (because the edges joining them with A are not so). By a classical result, there is a blue triangle EFG with vertices among these six. Now one of EB, EC, ED must be blue as well, because none of BC, BD, CD is. Let it be EB. Then four of the edges joining B, E, F, G are blue, which is impossible. For k = 5 the task is possible. Label the vertices 0, 1, . . . , 9. For each color, we divide the vertices into four groups and paint in this color every edge

joining two from the same group, as shown below. Then among any 5 vertices, 2 must belong to the same group, and the edge connecting them has the considered color. yellow: 01 12 20 36 69 93 red: 23 34 42 58 81 15 blue: 45 56 64 70 03 37 green: 67 78 86 92 25 59 orange: 89 90 08 14 47 71 26. A desired coloring can be made for k \geq6 as well. Paint the edge ij in the (i + j)th color for i < j \leq8, and in the 2ith color if j = 9 (the addition being modulo 9). We can ignore the edges painted with the extra colors. Then the edges of one color appear as five disjoint segments, so that any complete k-graph for k \geq5 contains one of them.