Given two positive integers $n$ and $k$. In the plane, there are $n$ circles ($n \geq 2$) such that each circle intersects every other circle at two points, and all these intersection points are pairwise distinct.
Each intersection point is colored with one of $n$ colors such that each color is used at least once and on each of the circles, the same number $k$ of colors is represented.
Determine all values of $n$ and $k$ for which such a coloring is possible.
The answer is: $2 \leq k \leq n \leq 3$ or $3 \leq k \leq n$.
Obviously, $k \leq n$ according to the problem statement, and $k \geq 2$, because for $k=1$ all points would have the same color, while the number $n$ of colors should be $\geq 2$. We number the circles and the colors from 1 to n and denote by $F(i, j)$ the set of colors of the intersection points of circles i and j. $F(i, j)$ contains one or two elements.
Let $k=2$. For $n=2$, $F(1,2)=\{1,2\}$ is an allowed coloring. For $n=3$, $F(1,2)=\{3\}$, $F(2,3)=\{1\}, F(3,1)=\{2\}$ is an example of an allowed coloring. Now let $n \geq 4$. To each of the n circles, we assign the set $\{i, j\}$ of the two colors appearing on it. Each of these sets consists of two elements, and each of the n colors must appear in at least two sets, since each colored point is the intersection of two circles. Therefore, each color appears in exactly two sets. For the circle 1 with the set $\{i, j\}$, there are thus at most two other circles whose color sets contain i or j. Since $n \geq 4$, we always find a circle 2 with the set $\{k, l\}$ and $\{k, l\} \cap\{i, j\}=\{ \}$. The intersection points of circles 1 and 2 are then not allowed to be colored, contradiction!
Now we prove by induction a slightly stronger statement than required: For $n \geq k \geq 3$, there always exists an allowed coloring in which the color i appears on the circle i for all $i=1, \ldots, n$. For the base case, we give an example for $k=n=3$ with $F(1,2)=\{1,2\}$, $F(1,3)=\{1,3\}, F(2,3)=\{2,3\}$ and for $k=3, n>3$ the following example of an allowed coloring with the additional condition:
$F(1,2)=\{1,2\}, F(i, i+1)=\{i\}$ for $1<i<n-1, F(n-1, n)=\{n-2, n-1\}$ and $F(i, j)=\{n\}$ for the remaining pairs $(i, j)$ with $1 \leq i<j \leq n$.
Now assume that the stronger statement is true for some $k \geq 3$, and choose $n \geq k+1$. Since $n-1 \geq k \geq 3$, there exists an allowed coloring with the additional condition for the circles or colors 1,2,..., n-1. Now we color the intersection points of circle n: For each $i=1, \ldots, n-1$, one intersection point of circles i and n is colored with color n. Thus, on each of the circles i with $i=1, \ldots, n-1$, exactly $k+1$ colors appear; among them i and $n$. For $i=1, \ldots, k$, the second intersection point of circles i and n is colored with color i, so that now also on circle $n$ exactly $k+1$ colors lie, namely 1 to $k$ and $n$. All other new intersection points are colored with color n, so that no additional colors appear on any circle. This coloring satisfies all conditions.