设 $n\geqslant 4$ 是偶数．在正 $n$ 边形的顶点处任意方式标上 $n$ 个互不相同的实数，从某条边起按顺时针方向依次将边记为 $e_1 , e_2 , \ldots , e_n$．一条边称为"正边"，若其两个端点所标之数按顺时针方向是递增的．两条不同的边构成的无序边对 $\{e_i , e_j \}$ 称为"交错"的，若 $2|(i+j)$，且将它们四个端点上所标数按递增顺序记为 $a<b<c<d$ 后，$a,c$ 是其中一条边的两端点所标之数．求证：交错的边对的个数与正边的个数具有不同的奇偶性．
【难度】
【出处】
2013第12届CGMO试题
【标注】
【答案】
略
【解析】
证法一
不妨设所标的 $n$ 个实数即为 $1,2,\ldots,n$，设 $A$ 是交错的边对个数，
$B$ 是正边个数，$S=A+B$．我们证明将标数 $i$ 和 $i+1$ 交换后 $S$ 的奇偶性不改变．讨论两种情形．
情形一：标有 $i$ 和 $i+1$ 的顶点相邻，为边 $e_k$ 的两个端点，交换 $i$ 与 $i+1$ 后，$e_k$ 的正负性改变（我们把不是正边的边称为负边），其余边的正负性不改变，故 $B$ 改变奇偶性．另一方面除边对 $\{e_{k-1},e_{k+1}\}$（这里下标需按模 $n$ 理解）外，其余下标和为偶数的边对仍保持原先的交错性或不交错性，而 $\{e_{k-1},e_{k+i}\}$ 会改变其交错性，即若 $\{a,i\},\{b,i+1\}$ 是交错的（或非交错的），则交换 $i$ 和 $i+1$ 后，$\{a,i+1\},\{b,i\}$ 是非交错的（或交错的）．这是因为若 $\{a,i\},\{b,i+1\}$ 是交错的，则或者 $b<i<i+1<a$，或者 $i<i+1<a<b$，或者 $a<b<i<i+1$，不论何种情祝，$\{a,i+1\},\{b,i\}$ 是非交错的．若 $\{a,i\},\{b,i+1\}$ 是非交错的，则或者 $a<i<i+1<b$，或者 $b<a<i<i+l$，或者 $i<i+1<b<a$，不论何种情况，$\{a,i+1\},\{b,i\}$ 是交错的．这样 $A$ 改变奇偶性，$S$ 不改变奇偶性．
情形二：标有 $i$ 和 $i+1$ 的顶点不相邻，假设分别为边 $e_j , e_{j+1}$ 和 $e_k , e_{k+1}$ 的顶点，交换 $i$ 与 $i+1$ 后每条边的正负性不改变，即 $B$ 不改变．不同时包含 $i$ 与 $i+1$ 的边对的交错性也不改变，同时包含 $i$ 与 $i+1$ 的边对，且下标和为偶数的恰有两对，
由上面的讨论知这两对边的交错性改变，故 $A$ 的奇偶性不改变，$S$ 的奇偶性也不改变．
现通过上面的操作使得标数方式为从某个顶点开始顺时针依次标数为 $1,2,\ldots,n$．这是可以做到的，设某个顶点的标数为 $1$，若其顺时针下一个顶点上不是 $2$，为 $i>2$，则交换 $(i,i-1),(i-1,i-2),\ldots,(3,2)$，则 $2$ 在 $1$ 的顺时针下一个顶点上，类似方法可使得顺时针依次标数为 $1,2,\ldots,n$．由上述讨论知 $S$ 不改变奇偶性，此时 $B=n-1,A=0$，故 $S$ 为奇数．因此初始时 $S$ 也为奇数，即 $A$ 和 $B$ 具有不同奇偶性．
证法二
从某个顶点起顺时针方向将顶点上的数依次记为 $x_1 , x_2 , \ldots,x_n$，不妨设边 $e_i$ 的两端顶点的标数为 $x_i , x_{i+1},i=1,2,\ldots,n$，这里记 $x_{n+1}=x_1$．易知 $e_i$ 为正边当且仅当 $x_{i+1}-x_i >0$．
设交错边对个数为 $A$，正边个数为 $B$．记
$
\beta=\prod_{i=1}^{n}\left(x_{i+1}-x_{i}\right)
$
由于 $n$ 是偶数，$\beta$ 的符号即为 $(-1)^{B}$．另一方面 $\{e_i , e_j \}$ 是交错边对当且仅当 $2|i+j$，并且 $
\left(x_{j}-x_{i}\right)\left(x_{j}-x_{i+1}\right)\left(x_{j+1}-x_{i}\right)\left(x_{j+1}-x_{i+1}\right)<0
$
将上式左边记为 $f(e_i , e_j )$，显然 $f\left(e_{i}, e_{j}\right)=f\left(e_{j}, e_{i}\right)$．设边 $e_i$ 的两端数为 $a,c$，$a<c$，边 $e_j$ 的两端数为 $b,d$，
$b<d$，若 $e_i , e_j$ 是交错边对，则 $a<b<c<d$，或者 $b<a<d<c$，不论何种情形都有
$
f\left(e_{i}, e_{j}\right)=(b-a)(b-c)(d-a)(d-c)<0
$
若 $e_i , e_j$ 不是交错边对，则要么 $b<a<c<d$，要么 $a<c<b<d$，要么 $b<d<a<c$，要么 $a<b<d<c$，不论何种情形都有
$
f\left(e_{i}, e_{j}\right)=(b-a)(b-c)(d-a)(d-c)>0
$
再记
$\begin{aligned}
\alpha&=\prod_{\substack{1 \leqslant i<j \leqslant n\\ 2|i+j}}\left(x_{j}-x_{i}\right)\left(x_{j}-x_{i+1}\right)\left(x_{j+1}-x_{i}\right)\left(x_{j+1}-x_{i+1}\right)\\
&=\prod_{\substack{1 \leqslant i<j \leqslant n\\ 2|i+j}} f\left(e_{i}, e_{j}\right)
\end{aligned}$
则 $\alpha$ 的符号为 $(-1)^{A}$．下面计算 $\alpha\beta$ 的符号．对 $1\leqslant i<j\leqslant n$，考虑 $x_j - x_i$ 分别在 $\alpha$ 和 $\beta$ 中的出现次数和符号．分几种情形讨论．
情形一：$j-i=1$，$x_j - x_i$ 在 $\beta$ 中出现一次，符号为正，在 $\alpha$ 中也出现一次，若 $i>1$，则出现在 $f(e_{i-1} , e_{i+1})$ 中，符号为正，若 $i=1$，$x_2 - x_1$ 出现在 $f(e_2 , e_n )$ 中，符号为负．这部分数乘积的符号为负．
情形二：$2\leqslant j-i<n-1$，则 $x_j - x_i$ 在 $\beta$ 中不出现，在 $\alpha$ 中出现两次，$(i-1,j-1),(i-1,j)$ 中恰有一对是同奇偶性的，$(i,j-1),(i,j)$ 中恰有一对是同奇偶性的．$x_j - x_i$ 出现的符号都是正的，除了 $i=1$ 时，出现在 $f(e_{j-1},e_n )$ 或 $f(e_j , e_n )$ 中符号是负的．对 $i=1, j=3,4,\ldots,n-1$ 各产生一个负号，这部分数乘积的符号为 $(-1)^{n-3}=-1$．
情形三：$i=1, j=n$，则 $x_n - x_1$ 在 $\beta$ 中出现一次，为负号，在 $\alpha$ 中也出现一次，出现在 $f(e_{n-1},e_1 )$ 中，为正号．这部分数乘积的符号为负．
综上所述，$\alpha\beta$ 的符号为负，即 $A+B$ 为奇数，结论得证．
不妨设所标的 $n$ 个实数即为 $1,2,\ldots,n$，设 $A$ 是交错的边对个数，
$B$ 是正边个数，$S=A+B$．我们证明将标数 $i$ 和 $i+1$ 交换后 $S$ 的奇偶性不改变．讨论两种情形．
情形一：标有 $i$ 和 $i+1$ 的顶点相邻，为边 $e_k$ 的两个端点，交换 $i$ 与 $i+1$ 后，$e_k$ 的正负性改变（我们把不是正边的边称为负边），其余边的正负性不改变，故 $B$ 改变奇偶性．另一方面除边对 $\{e_{k-1},e_{k+1}\}$（这里下标需按模 $n$ 理解）外，其余下标和为偶数的边对仍保持原先的交错性或不交错性，而 $\{e_{k-1},e_{k+i}\}$ 会改变其交错性，即若 $\{a,i\},\{b,i+1\}$ 是交错的（或非交错的），则交换 $i$ 和 $i+1$ 后，$\{a,i+1\},\{b,i\}$ 是非交错的（或交错的）．这是因为若 $\{a,i\},\{b,i+1\}$ 是交错的，则或者 $b<i<i+1<a$，或者 $i<i+1<a<b$，或者 $a<b<i<i+1$，不论何种情祝，$\{a,i+1\},\{b,i\}$ 是非交错的．若 $\{a,i\},\{b,i+1\}$ 是非交错的，则或者 $a<i<i+1<b$，或者 $b<a<i<i+l$，或者 $i<i+1<b<a$，不论何种情况，$\{a,i+1\},\{b,i\}$ 是交错的．这样 $A$ 改变奇偶性，$S$ 不改变奇偶性．
情形二：标有 $i$ 和 $i+1$ 的顶点不相邻，假设分别为边 $e_j , e_{j+1}$ 和 $e_k , e_{k+1}$ 的顶点，交换 $i$ 与 $i+1$ 后每条边的正负性不改变，即 $B$ 不改变．不同时包含 $i$ 与 $i+1$ 的边对的交错性也不改变，同时包含 $i$ 与 $i+1$ 的边对，且下标和为偶数的恰有两对，
由上面的讨论知这两对边的交错性改变，故 $A$ 的奇偶性不改变，$S$ 的奇偶性也不改变．
现通过上面的操作使得标数方式为从某个顶点开始顺时针依次标数为 $1,2,\ldots,n$．这是可以做到的，设某个顶点的标数为 $1$，若其顺时针下一个顶点上不是 $2$，为 $i>2$，则交换 $(i,i-1),(i-1,i-2),\ldots,(3,2)$，则 $2$ 在 $1$ 的顺时针下一个顶点上，类似方法可使得顺时针依次标数为 $1,2,\ldots,n$．由上述讨论知 $S$ 不改变奇偶性，此时 $B=n-1,A=0$，故 $S$ 为奇数．因此初始时 $S$ 也为奇数，即 $A$ 和 $B$ 具有不同奇偶性．
证法二
从某个顶点起顺时针方向将顶点上的数依次记为 $x_1 , x_2 , \ldots,x_n$，不妨设边 $e_i$ 的两端顶点的标数为 $x_i , x_{i+1},i=1,2,\ldots,n$，这里记 $x_{n+1}=x_1$．易知 $e_i$ 为正边当且仅当 $x_{i+1}-x_i >0$．
设交错边对个数为 $A$，正边个数为 $B$．记
$
\beta=\prod_{i=1}^{n}\left(x_{i+1}-x_{i}\right)
$
由于 $n$ 是偶数，$\beta$ 的符号即为 $(-1)^{B}$．另一方面 $\{e_i , e_j \}$ 是交错边对当且仅当 $2|i+j$，并且 $
\left(x_{j}-x_{i}\right)\left(x_{j}-x_{i+1}\right)\left(x_{j+1}-x_{i}\right)\left(x_{j+1}-x_{i+1}\right)<0
$
将上式左边记为 $f(e_i , e_j )$，显然 $f\left(e_{i}, e_{j}\right)=f\left(e_{j}, e_{i}\right)$．设边 $e_i$ 的两端数为 $a,c$，$a<c$，边 $e_j$ 的两端数为 $b,d$，
$b<d$，若 $e_i , e_j$ 是交错边对，则 $a<b<c<d$，或者 $b<a<d<c$，不论何种情形都有
$
f\left(e_{i}, e_{j}\right)=(b-a)(b-c)(d-a)(d-c)<0
$
若 $e_i , e_j$ 不是交错边对，则要么 $b<a<c<d$，要么 $a<c<b<d$，要么 $b<d<a<c$，要么 $a<b<d<c$，不论何种情形都有
$
f\left(e_{i}, e_{j}\right)=(b-a)(b-c)(d-a)(d-c)>0
$
再记
$\begin{aligned}
\alpha&=\prod_{\substack{1 \leqslant i<j \leqslant n\\ 2|i+j}}\left(x_{j}-x_{i}\right)\left(x_{j}-x_{i+1}\right)\left(x_{j+1}-x_{i}\right)\left(x_{j+1}-x_{i+1}\right)\\
&=\prod_{\substack{1 \leqslant i<j \leqslant n\\ 2|i+j}} f\left(e_{i}, e_{j}\right)
\end{aligned}$
则 $\alpha$ 的符号为 $(-1)^{A}$．下面计算 $\alpha\beta$ 的符号．对 $1\leqslant i<j\leqslant n$，考虑 $x_j - x_i$ 分别在 $\alpha$ 和 $\beta$ 中的出现次数和符号．分几种情形讨论．
情形一：$j-i=1$，$x_j - x_i$ 在 $\beta$ 中出现一次，符号为正，在 $\alpha$ 中也出现一次，若 $i>1$，则出现在 $f(e_{i-1} , e_{i+1})$ 中，符号为正，若 $i=1$，$x_2 - x_1$ 出现在 $f(e_2 , e_n )$ 中，符号为负．这部分数乘积的符号为负．
情形二：$2\leqslant j-i<n-1$，则 $x_j - x_i$ 在 $\beta$ 中不出现，在 $\alpha$ 中出现两次，$(i-1,j-1),(i-1,j)$ 中恰有一对是同奇偶性的，$(i,j-1),(i,j)$ 中恰有一对是同奇偶性的．$x_j - x_i$ 出现的符号都是正的，除了 $i=1$ 时，出现在 $f(e_{j-1},e_n )$ 或 $f(e_j , e_n )$ 中符号是负的．对 $i=1, j=3,4,\ldots,n-1$ 各产生一个负号，这部分数乘积的符号为 $(-1)^{n-3}=-1$．
情形三：$i=1, j=n$，则 $x_n - x_1$ 在 $\beta$ 中出现一次，为负号，在 $\alpha$ 中也出现一次，出现在 $f(e_{n-1},e_1 )$ 中，为正号．这部分数乘积的符号为负．
综上所述，$\alpha\beta$ 的符号为负，即 $A+B$ 为奇数，结论得证．
答案
解析
备注
