2004 IMO Shortlist Problems/C2

Problem

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

This was also Problem 6 of the 2005 German Pre-TST.

Solution

The answer is $\displaystyle k=2$ and $n \le 3$ , or $3 \le k \le n$ . We must have $\displaystyle k \le n$ , since there are $\displaystyle n$ colors.

If $\displaystyle k=1$ , then all points on any circle must be the same color, so all points must be the same color and $\displaystyle n=1$ , a contradiction.

For $\displaystyle {} k=n=2$ , we have two circles, and we color their intersection points distinct colors. For $\displaystyle k=2, n=3$ , we have three circles. We associate with each distinct pair of circles a distinct color, which we use for both points common to the pair of circles.

We will prove that the problem's situation is impossible for $\displaystyle k=2, n>3$ . Suppose, on the contrary, that we have such a coloring. Then with each circle there are associated two distinct colors, and any two circles have at least one color in common. We claim that there is one color common to all circles. Suppose the contrary. Then there is a circle with colors 1,2. Since 1 is not common to all circles, there must be some circle with colors 2,3. But 2 is not common to all circles, so there must be some circle without the color 2, which must nonetheless have a color in common with both of the first two circles, so this third circle must have colors 1,3. But any more circles must have at least one color in common with each of our initial circles, i.e., they must have at least two of the colors 1,2,3. But since a circle only has two distinct colors, there are only 3 distinct colors in all the circles, so $\displaystyle n=3$ , a contradiction. Thus there is a color 0 common to all circles. This means that no circle can hold more than 1 of the other colors. But since each color must occur on at least two circles, there are at most $\displaystyle n/2$ colors other than 0, a contradiction.

We will now prove that there exist colorings as described in the problem for all $\displaystyle 3\le k\le n$ . We proceed by induction on $\displaystyle k$ .

For the base case $\displaystyle k=3$ , let our circles be $\displaystyle C_1, \ldots, C_n$ . For each $1\le i \le n-1$ , we will color one of the intersection points between $\displaystyle C_i$ and $\displaystyle C_{i+1}$ the color $\displaystyle i$ . Furthermore, we will color one intersection point between $\displaystyle C_1, C_n$ the color 1, and the other the color $\displaystyle n-1$ . Thus far, we have used $\displaystyle n-1$ colors, each circle has two distinct colors, and each circle has at least one uncolored intersection points. Therefore if we color all remaining points color $\displaystyle n$ we have a desired coloring.

Now, suppose that there is such a coloring for $k-1 \ge 3$ , $n-1 \ge k-1$ , with circles $C_1, \ldots, C_{n-1}$ and colors $1, \ldots, n-1$ . We claim that there exist distinct circles $R_1, \ldots, R_{k-1} \in \{ C_{i} \}_{i=1}^{n-1}$ such that circle $\displaystyle R_i$ has at least one point of color $\displaystyle f(i)$ such that all the $\displaystyle f(i)$ are distinct. Suppose the contrary. Consider the maximal $\displaystyle m$ for which there exist such circles $R_1, \ldots R_m$ . This means that no circle other than the $\displaystyle R_i$ has any color other than $f(1), \ldots, f(m)$ . But since $\displaystyle m < k-1 \le n-1$ by assumption, this means that there are some circles with less than $\displaystyle k-1$ colors on them, a contradiction. Now, we add a circle $\displaystyle C_n$ . For each $\displaystyle i \le k-1$ , we color exactly one intersection point of $\displaystyle R_i$ and $\displaystyle C_n$ the color $\displaystyle f(i)$ . We color all other new intersection points a new color $\displaystyle n$ . Now there are $\displaystyle n$ distinct colors used, and each circle uses $\displaystyle k$ distinct colors.