Problem 1570

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.

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_{\substack{1 \le i < j \le n \\ 2 \mid i+j}} (x_j - x_i)(x_j - x_{i+1})(x_{j+1} - x_i)(x_{j+1} - x_{i+1}) = \prod_{\substack{1 \le i < j \le n \\ 2 \mid i+j}} 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$