2004 IMO Shortlist Problems/C2
Problem
(Germany)
Let and
be positive integers. There are given
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
distinct colors so that each color is used at least once and exactly
distinct colors occur on each circle. Find all values of
and
for which such a coloring is possible.
This was also Problem 6 of the 2005 German Pre-TST.
Solution
The answer is and
, or
. We must have
, since there are
colors.
If , then all points on any circle must be the same color, so all points must be the same color and
, a contradiction.
For , we have two circles, and we color their intersection points distinct colors. For
, 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 . 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
, 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
colors other than 0, a contradiction.
We will now prove that there exist colorings as described in the problem for all . We proceed by induction on
.
For the base case , let our circles be
. For each
, we will color one of the intersection points between
and
the color
. Furthermore, we will color one intersection point between
the color 1, and the other the color
. Thus far, we have used
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
we have a desired coloring.
Now, suppose that there is such a coloring for ,
, with circles
and colors
. We claim that there exist distinct circles
such that circle
has at least one point of color
such that all the
are distinct. Suppose the contrary. Consider the maximal
for which there exist such circles
. This means that no circle other than the
has any color other than
. But since
by assumption, this means that there are some circles with less than
colors on them, a contradiction. Now, we add a circle
. For each
, we color exactly one intersection point of
and
the color
. We color all other new intersection points a new color
. Now there are
distinct colors used, and each circle uses
distinct colors.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.