XLVIII OM - II - Problem 3

Given a set of $ n $ points ($ n \geq 2 $), no three of which are collinear. We color all segments with endpoints in this set such that any two segments sharing a common endpoint have different colors. Determine the smallest number of colors for which such a coloring exists.
Let's assume that the given points are vertices of some $n$-gon (if $n = 2$, of course, one color is enough). All segments of the same color determine disjoint pairs of vertices of the polygon. The maximum number of disjoint two-element subsets of an $n$-element set is $[n/2]$. Therefore, the number of colors is not less than

We will show that this number of colors is sufficient to meet the desired condition.
When $n$ is an odd number, we take the set of vertices of an $n$-sided regular polygon and paint the side and all diagonals parallel to it with the same color; segments not parallel are painted with different colors. We used $n$ colors.
When $n$ is an even number, we take the set of vertices of an $(n-1)$-sided regular polygon $V$ and one more point $P_0$. We color the sides and diagonals of the polygon $V$ in the manner described above, using $n - 1$ colors. For each family of parallel segments of the same color $k_i$, there remains one vertex $P_i$ of the polygon $V$ that is not an endpoint of any of these segments. We paint the segment $P_0P_i$ with color $k_i$. We used $n - 1$ colors, meeting the required condition.