China Girls' Mathematical Olympiad

Without loss of generality, we may assume that the numbers written on the vertices are $1,2,\dots ,n$. Let $A$ be the number of crossings, and $B$ be the number of positive edges. We will prove that the parity of $S$ remains the same if we exchange numbers $i$ and $i+1$. We distinguish two cases.

Case 1. The numbers $i$ and $i+1$ are written on adjacent vertices, i.e., the endpoints of edge $e_k$. Once we exchange $i$ and $i+1$, the number of positive edges is modified by 1, thus the parity of $B$ is changed. On the other hand, the only two-edge subset that will become a new crossing (or change from a crossing to a non-crossing) is $\{e_{k-1},e_{k+1}\}$ (the subindices are to be understood modulo $n$), all the other two-edge subsets will not be affected. So the parity of $A$ will change.

Case II. The numbers $i$ and $i+1$ are written on non-adjacent vertices. Assume that they are written on the (common) endpoints of $e_j$, $e_{j+1}$ and of $e_k$, $e_{k+1}$, respectively. Once we exchange $i$ and $i+1$, every positive edge will remain positive, so are non-positive ones. Therefore, $B$ is unchanged. Now, for number of crossings, if a two-edge subset does not involve at the same time $i$ and $i+1$, then whether it is a crossing or not is not affected by the operation. So the only two-edge subsets to be considered are the two that have both $i$ and $i+1$ written on their vertices and the sum of the edge number is even. They will both become crossing after the exchange if they are not before, and vice-versa. Hence, the parity of $A$ remains the same.

Now obviously, every pattern can be obtained from a finite number of such exchange if we start from writing $1,2,\dots ,n$ consecutively in a clockwise way, and in the initial situation, $B=n-1,A=0$. So $A$ and $B$ have different parity.

---

Alternative solution.

Starting from one vertex, we denote the numbers written on the vertices by $x_1,x_2,\dots ,x_n$ in a clockwise way. We may assume that the numbers written on the endpoints of edge $e_i$ are $x_i,x_{i+1}$, $i=1,2,\dots ,n$, where $x_{n+1}=x_1$. Apparently $e_i$ is positive if and only if $x_{i+1}-x_i>0$. Now, let $A$ be the number of positive edges, and $B$ be the number of crossings. Write $$\beta =\prod _{i=1}^n(x_{i+1}-x_i).$$ As $n$ is even, the sign of $\beta$ is just $(-1{)}^A$.

On the other hand, $\{e_i,e_j\}$ is a crossing if and only if $2\mid i+j$ and $$(x_j-x_i)(x_{j+1}-x_{i+1})(x_{j+1}-x_i)(x_{j+1}-x_{i+1})<0.$$ We denote by $f(e_i,e_j)$ the left-hand side of the above inequality, obviously $f(e_i,e_j)=f(e_j,e_i)$. This quantity is negative if and only if the two-edge set is a crossing. Now, define $$\alpha =\prod _{\begin{array}{c}1\le i<j\le n\\ 2\mid i+j\end{array}}(x_j-x_i)(x_j-x_{i+1})(x_{j+1}-x_i)(x_{j+1}-x_{i+1})=\prod _{\begin{array}{c}1\le i<j\le n\\ 2\mid i+j\end{array}}f(e_i,e_j),$$ then the sign of $\alpha$ is $(-1{)}^B$. Let us calculate the sign of $\alpha \beta$. For $1\le i<j\le n$, consider the times of appearance, and the sign of $x_j-x_i$ in $\alpha$ and $\beta$, respectively. We distinguish several cases.

Case I. $j-i=1$, $x_j-x_i$ appears once in $\beta$ with a positive sign, and once in $\alpha$. If $i>1$, it appears in $f(e_{i-1},e_{i+1})$ with a positive sign. If $i=1$, $x_2-x_1$ appears in $f(e_2,e_n)$ with a negative sign. The product of these numbers has a negative sign.

Case II. $2\le j-i<n-1$, then $x_j-x_i$ does not appear in $\beta$, and appear in $\alpha$ twice. Among $(i-1,j-1)$ and $(i-1,j)$, there is exactly one pair that is of the same parity, among $(i,j-1)$ and $(i,j)$, there is also exactly one such pair. The sign of $x_j-x_i$ in each appearance is always positive. For $i=1$, its appearance in $f(e_{j-1},e_n)$ or $f(e_j,e_n)$ comes with a negative sign. Hence, there is a negative sign for each pair $(i,j)$ ($i=1,j=3,4,\dots ,n-1$). This part of the product has the sign $(-1{)}^{n-3}=-1$.

Case III. $i=1,j=n$, then $x_n-x_1$ appears once in $\beta$ with a negative sign, and once in $\alpha$ (in $f(e_{n-1},e_1)$) with a positive sign. This part of the product has a negative sign.

In brief, the sign of $\alpha \beta$ is negative, i.e., $A+B$ is odd. $\square$