Silk Road Mathematics Competition

Consider a regular $2n$-gon (inscribed in a unit circle), which we label $n$ segments from the set of all sides and all diagonals. The problem is equivalent to the following one: prove that some of unlabelled segments (including endpoints) can be coloured in red in such way that each red vertex belongs to exactly $n$ red segments. We define k-segment as a segment spanning an arc of the length $\pi k/n$. The following cases are possible: Case 1. Let some two labelled segments have a common vertex. Then we choose this vertex and other $n-2$ vertices in such way that at least a vertex is chosen in each labelled segment (so, totally we choose $1+(n-2)=n-1$ vertices). The other vertices will form a complete graph (i.e. a clique) with $n+1$ vertices: each two vertices are connected by an unlabeled segment. Colour these segments in red and we are done. Case 2. The labelled segments have no common points.

Subcase 2.1. $n$ is even. W.l.o.g. (using an appropriate numeration of vertices) we can assume that all longest diagonals (i.e. $n$-segments) are labelled. Colour all $k$-segments for $k=1,2,\dots ,n/2$ in red and we are done. Subcase 2.2. $n$ is odd. W.l.o.g. (using an appropriate numeration of vertices again) we can assume that $n$ 1-segments are labelled (i.e. $n$ sides of the polygon, in alternating manner). Colour all unlabeled $k$-segments for $k=1,2,\dots ,(n+1)/2$ in red and we are done.