All-Russian Olympiad Problem 4

Suppose the circle has $m$ points and there are $n$ colors denoted $\{1,2,...,n\}$ , where $n$ divides $m$ . Let $k = m/n$ . We claim that the maximal number of chords (which we denote as $N_{m,n} = N_{k}$ ) is $N_{m,n} = N_{k} = \frac{m}{n} - 1 = k - 1$ . (So the answer to the problem is $2006/17 - 1 = 117$ .) We prove this claim via induction on $k$ (where $n$ is fixed). For $k = 1$ , clearly $N_{n,n} = 0$ . Now suppose the claim is true for $k - 1 \geq 1$ . Consider a circle with $m = k n$ points. Either there are exactly $k$ points of each color (Case II), or there are $k+1$ points of the same color C (Case I).

In Case I, there must be two points of color C which are at most $n-1$ points apart (i.e., between these two points there are $k-2$ other points). Join these two points by a line. This divides the circle into two new "circles," the larger of which has at least $m - (k-2) - 2 = (k - 1)n$ points colored with the $n$ colors. So by the induction hypothesis, we can draw $1 + (k-1 - 1) = k - 1$ chords in the entire circle.

In Case II, there must be two points of color C which are at most $n-1$ points apart, or points of each color are exactly $n$ points apart. In the former subcase, we are back in Case I. In the latter subcase, WLOG, the circle's points are labeled $1,2,...,n, 1,2,..., n, …., 1,2,..., n$ (when traversing the circle in the natural order). It is easy to see that we can draw $k - 1$ chords in this specific case.

So we have shown that the maximal number of chords in a circle with $k n$ points and $n$ colors is at least $k-1$ . It remains to show that we cannot do better than this. For this, consider again the circle whose points are labeled $1,2,...,n, 1,2,..., n, …., 1,2,..., n$ (when traversing the circle in the natural order). We want to prove that we cannot draw more than $k-1$ chords in this specific circle. This is straightforward to prove with induction on $k$ , and I will omit it for brevity.