Bulgarian Winter Tournament

Put $n$ instead of 11 and let the points be $A_1,A_2,\dots ,A_n$. We may assume that the points are vertices of a regular $n$-gon. Let us first calculate the maximum number of diagonals that we can draw so that any diagonal meets no more than one other diagonal at an interior point. Note that we exclude the sides of the $n$-gon, and are interested only in its diagonals. We denote this number by $R(n)$. Obviously $R(2)=0$, $R(3)=0$. We will prove by induction that $$R(n)=\lceil \frac{3(n-3)}{2}\rceil ,n\ge 3$$ For small cases of $n$ it is checked directly. For example $R(4)=2$, $R(5)=3$, $R(6)=5$. Assume the formula is already checked for all values less than $n$ for some $n\in \mathbb{N}$, $n\ge 5$. Let $A_1{A}_j$ and $A_i{A}_k$ be diagonals of an extremal configuration of $n$ points. Denote by $G_1$ the group of vertices that lie between $A_1$ and $A_k$ (including $A_1$ and $A_k$) and let their number be $n_1$. In the same way let $G_2,G_3,G_4$ be the groups of vertices that lie respectively between $A_k$ and $A_j$, $A_j$ and $A_i$, $A_i$ and $A_1$ and their corresponding numbers be $n_2,n_3,n_4$. The key observation is that all the other diagonals connect points that are in the same group. The maximum number of diagonals that connect points in $G_1$ is $R(n_1)$. Note that if $n_1\ge 2$ then $A_1{A}_k$ connects non-adjacent vertices and this diagonal takes part in $R(n)$ but doesn't take part in $R(n_1)$ (the dotted diagonals on fig. 1). The same holds for the other groups. The red diagonals also should



be added so we obtain, $$R(n)=\sum _{i=1}^{4}R(n_i)+\sum _{i=1}^4{1}_{n_i>2}+2.$$ Here, by $1_{n_i>2}$ we mean the indicator function that shows whether $n_i$ is greater than 2, i.e. $1_{n_i>2}=1$ if $n_i>2$ and 0 otherwise. Hence, $$R(n)=\sum _{i=1}^4\lceil \frac{3(n_i-3)}{2}\rceil +\sum _{i=1}^4{1}_{n_i>2}+2(1).$$ and completes the induction step. Back to the original problem. Remove the sides of the $n$-gon. Fix a color. The number of diagonals of that color is at most $\lfloor \frac{3(n-3)}{2}\rfloor$. The same holds for the other color. Adding the sides of the $n$-gon, which can be colored as we want, we get that the greatest number of segments is at most $$2\lfloor \frac{3(n-3)}{2}\rfloor +n.$$ There is no problem to give an example of this number of segments that satisfy the condition. □