9.1. On a circle, 1000 points are marked, each colored in one of $k$ colors. It turns out that among any five pairwise intersecting segments, whose endpoints are 10 different marked points, there will be at least three segments, each of which has endpoints of different colors. For what smallest $k$ is this possible?

(S. Berlov)
Answer. For $k=143$.

Solution. Suppose there are 8 points of one color (say, red) on the circle. Add two more marked points to them, forming a decagon $A_{1} A_{2} \ldots A_{5} B_{1} B_{2} \ldots B_{5}$. Then the segments $A_{1} B_{1}, A_{2} B_{2}, \ldots, A_{5} B_{5}$ intersect each other, and among them, there are three segments with all endpoints red. This contradicts the condition. Therefore, there are no more than seven points of each color, so $k \geqslant \frac{1000}{7}$, that is, $k \geqslant 143$.

For $k=143$, mark an additional, 1001st, point and divide all marked points into 143 groups of 7 consecutive points each. Color each group with its own color. Let $A_{1} B_{1}, \ldots$, $A_{5} B_{5}$ be five pairwise intersecting segments with endpoints at the marked points. We can assume that the points $A_{1}, A_{2}, \ldots, A_{5}, B_{1}$, $B_{2}, \ldots, B_{5}$ are located on the circle in this order. Suppose the segment $A_{1} B_{1}$ has endpoints of the same color (say, red). Then either all points $A_{1}, A_{2}, \ldots, A_{5}$, or all points $B_{1}, B_{2}, \ldots, B_{5}$ are red. In the first case, at most two of the points $B_{1}, B_{2}, \ldots, B_{5}$ are red. But then three segments not containing these points will have endpoints of different colors. The second case is analogous.