IMO 2004 SL C2

Origin: GER | Category: Combinatorics

Problem

Let n and k be positive integers. There are given n circles in the plane. Every two of them intersect at two distinct points, and all points of intersection they determine are distinct. Each intersection point must be colored with one of n distinct colors so that each color is used at least once, and exactly k distinct colors occur on each circle. Find all values of n \geq2 and k for which such a coloring is possible.

Solution

Obviously we must have 2 \leqk \leqn. We shall prove that the possible values for k and n are 2 \leqk \leqn \leq3 and 3 \leqk \leqn. Denote all colors and circles by 1, . . . , n. Let F(i, j) be the set of colors of the common points of circles i and j. Suppose that k = 2 < n. Consider the ordered pairs (i, j) such that color j appears on the circle i. Since k = 2, clearly there are exactly 2n such pairs. On the other hand, each of the n colors appears on at least two circles, so there are at least 2n pairs (i, j), and equality holds only if each color appears on exactly 2 circles. But then at most two points receive each of the n colors and there are n(n −1) points, implying that n(n −1) = 2n, i.e., n = 3. It is easy to find examples for k = 2 and n = 2 or 3. Next, let k = 3. An example for n = 3 is given by F(i, j) = {i, j} for each 1 \leqi < j \leq3. Assume n \geq4. Then an example is given by F(1, 2) =

{1, 2}, F(i, i + 1) = {i} for i = 2, . . . , n −2, F(n −1, n) = {n −2, n −1} and F(i, j) = n for all other i, j > i. We now prove by induction on k that a desired coloring exists for each n \geqk \geq3. Let there be given n circles. By the inductive hypothesis, circles 1, 2, . . . , n −1 can be colored in n −1 colors, k of which appear on each circle, such that color i appears on circle i. Then we set F(i, n) = {i, n} for i = 1, . . . , k and F(i, n) = {n} for i > n. We thus obtain a coloring of the n circles in n colors, such that k + 1 colors (including color i) appear on each circle i.