Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

The required maximum is $k = (n-1)(4n-1)$. Clearly, $|S| = 2(n-1)(4n-1)$. To begin, we show that $k \le (n-1)(4n-1)$. Otherwise, some $S_i$ is a singleton set, say $S_i = \{\delta\}$. Let $m$ be the number of vertices on one side of $\delta$, so the number of vertices on the other side is $4n - m - 3$, and the total number of diagonals crossing $\delta$ is $m(4n - m - 3) \le 2(n-1)(2n-1)$. Notice that each $S_j$, $j \ne i$, contains such a diagonal, to infer that $k \le 2(n-1)(2n-1)+1 = (n-1)(4n-1)-(n-2) \le (n-1)(4n-1)$ and thereby reach a contradiction.

To exhibit a partition of $S$ into $(n-1)(4n-1)$ sets satisfying the condition in the statement, label the vertices of the $(4n-1)$-gon in circular order, $A_1, A_2, \dots, A_{4n-1}$, and set
$$S_{i,j} = \{A_i A_{i+j}, A_{i+j-1} A_{i+2n}\}, \quad i = 1, 2, \dots, 4n-1, \quad j = 2, 3, \dots, n,$$
where indices are reduced modulo $4n-1$.

It is easily seen that the $S_{i,j}$ form a partition of $S$. To show that they satisfy the condition in the statement, consider two such, say $S_{i,j}$ and $S_{i',j'}$. By cyclic symmetry, we may (and will) assume that $i = 0$. Notice that for a diagonal $\delta$ to cross no diagonal in $S_{0,j}$ it is necessary and sufficient that its endpoints both fall in one of the sets below:
$$\{A_0, A_1, \dots, A_{i-1}\}, \quad \{A_i, A_{i+1}, \dots, A_{2n}\}, \quad \{A_{2n}, A_{2n+1}, \dots, A_{4n-1}\} \quad (*)$$
(recall that $A_{4n-1} = A_0$); if this is the case, we say that that set covers $\delta$. Now, since each set $(*)$ encompasses at most $2n$ consecutive vertices, none of these sets can cover both diagonals in $S_{i',j'}$. On the other hand, since the latter cross one another, they cannot be covered by different sets $(*)$ each either. Consequently, some diagonal in $S_{0,j}$ must cross some diagonal in $S_{i',j'}$ and the conclusion follows.