Berroov S.L.

Petya is coloring 2006 points, located on a circle, using 17 colors. Then Kolya draws chords with endpoints at the marked points such that the endpoints of any chord are of the same color and the chords do not have any common points (including common endpoints). Kolya wants to draw as many chords as possible, while Petya tries to prevent him. What is the maximum number of chords that Kolya can definitely draw?
Note that $2006=17 \cdot 118$; therefore, there will be two colors in which at least $2 \cdot 118=236$ points are painted in total.

We will prove by induction on $k$ that through $2 k-1$ points of two colors, it is always possible to draw $k-1$ non-intersecting chords with same-colored endpoints.

Base case $(k=1,2)$ is obvious.

Inductive step. Suppose $k>2$. Then among the points, we will take two consecutive points of the same color. Connect them with a chord, remove them, and apply the induction hypothesis to the remaining points.

By selecting 235 points of two colors and applying the proven statement, we get that Kolya will always be able to draw 117 chords. It remains to provide an example where more chords cannot be drawn.

Suppose there are $17 k$ points on the circle, and Petya paints each point in a color corresponding to the remainder of its number when divided by 17.

We will prove by induction on $k$ that through these points, no more than $k-1$ chords can be drawn while satisfying the condition. The base case is obvious.

Inductive step. Suppose some number of chords have been drawn. Considering two connected points A and B at the minimum distance from each other, we get a chord $A B$ such that on one of the arcs into which it divides the circle, there are no endpoints of other drawn chords. Now erase the chord $A B$ and remove all points of this arc from the circle, including one of the chord's endpoints. We have obtained the initial coloring of $17 l$ points for $l<k$. They are connected by no more than $l-1$ chords, so initially, there were no more than $l-1+1 \leq k-1$ chords, as required.

## Answer

117 chords