能否把 $1,1,2,2,3,3, \cdots, 1986,1986$ 这些数重新排成一行，使得两个 $1$ 之间夹着一个数，两个 $2$ 之间夹着两个数，$\cdots$，两个 $1986$ 之间夹着一千九百八十六个数？请证明你的结论．
【难度】
【出处】
1986第1届CMO试题
【标注】
【答案】
略
【解析】
为了使结果更一般些，我们考虑 $ 1,1,2,2,\cdots,n-1,n-1,n,n $，这 $ 2n $ 个数的重排的可能性问题，要求还是：两个 $ k $ 之间夹着 $ k $ 个数，这里 $ k $ 取 $ 1,2,\cdots,n-1,n $ 中的每一个值．
以下给出三种证法．这一种证法多少带有高等数学的色彩，主要的思想与 $ n $ 阶行列式的理论基础—置换—有些关系；第二种证法简单一些，只涉及前若干个自然数的求和公式，这时高中数学课本中的内容；第三种证法几乎不需要多少知识，但体现着巧妙地思考，这一证法，是参加冬令营的一位上海女同学的答卷．
证法一
对于 $ 1,1,2,2,\cdots,n,n $ 的任一排列，用一个大写字母，例如 $ P $ 来表示．设想对于 某一确定的排列 $ P $，在其中，两个 $ k $ 之间夹着 $ R_k $ 个数，这里 $ k=1,2,\cdots,n $，定义 $ R(P)=R_{1}+R_{2}+\cdots+R_{n} $ 它是一个非负整数，我们称 $ R(P)$ 为排列 $ P $ 的"指数"．
现在，对调 $ P $ 中某相邻两个数，例如 $ i,j $，无妨设 $ i\ne j $，其余的数均保留在原来的位置上，得出了一个新的排列 $ Q $．我们来看两个指数 $ R(P)$ 与 $ R(Q)$ 之间的关系．
设 $ P=\begin{vmatrix}\begin{array}{c|c|c|c|c|c|c|c}\hline
\cdots & i & \cdots & i & j & \cdots & j & \cdots\\\hline
\end{array}\end{vmatrix} $ 故 $ Q=\begin{vmatrix}\begin{array}{c|c|c|c|c|c|c|c}\hline
\cdots & i & \cdots & j & i & \cdots & j & \cdots\\\hline
\end{array}\end{vmatrix} $
设在 $ P $ 中两个 $ i $ 之间夹着 $ R_i $ 个数，两个 $ j $ 之间夹着 $ R_j$ 个数，显然，在 $Q$ 中，两个 $i$ 之间夹着 $R_i+1$ 个数，而两个 $j$ 之间夹着 $R_j+1$ 个数．由于其他各对数的位置没有变化，因此 $R(Q)=R(P)+2$．此式也可写为 $R(P)=R(Q)-2$．再设 $ P=\begin{vmatrix}\begin{array}{c|c|c|c|c|c|c|c}\hline
\cdots & j & \cdots & i & \cdots & i & j & \cdots\\\hline
\end{array}\end{vmatrix} $ 故 $ Q=\begin{vmatrix}\begin{array}{c|c|c|c|c|c|c|c}\hline
\cdots & j & \cdots & i & \cdots & j & i & \cdots\\\hline
\end{array}\end{vmatrix} $ 在排列 $Q$ 中，显然两个 $i$ 之间夹的数的个数为 $R_i+1$，两个 $j$ 之间夹的数的个数为 $R_j-1$，由此可知 $R(Q)=R(P)$．
所以，不论 $P$ 为怎样的一个排列，如果只对换 $P$ 中的相邻的两数，保持其余的各数不变，得出的排列为 $Q$，那么必有 $R(P)=R(Q)\pm 2$．这就是说，这样的两个排列 $P$ 与 $Q$，其指数具有相同的奇偶性．
经过有限次的相邻两数之间的对换，任一排列 $P$ 总可以变为排列 $ P_0=\begin{vmatrix}\begin{array}{c|c|c|c|c|c|c|c|c}\hline
1 & 1 & 2 & 2 & 3 & 3 & \cdots & n & n\\\hline
\end{array}\end{vmatrix} $ 显然 $R\left(P_{0}\right)=0+0+\cdots+0=0$，结合上述推理可知：$1,1,2,2,\cdots,n,n$ 的任一排列的指数只能为偶数．今设所要求的排列存在，记为 $P^{\ast}$．这一排列的指数是 $R\left(P^{*}\right)=1+2+\cdots+n=n(n+1) / 2$ 按前面的说法，它应当为偶数，记为 $2t$，于是 $n(n+1)=4 t$ 这里 $t$ 为正整数．当 $n$ 为奇数时，$4$ 应整除 $n+1$，亦即 $n=4m+3$，这里 $m$ 为非负整数，当 $n$ 为偶数时，$n+1$ 为奇数，这时 $4$ 必整除 $n$，所以 $n=4m$，这里 $m$ 为某一正整数．
这就是说，如果具有所有要求的性质的排列存在，那么必须有 $n\equiv 0$ 或 $3\pmod{4}$．当 $n=1986$ 时，此数被 $4$ 除之余 $2$，不满足上述关系，因此，一定不能排成所要求的形式．
证法二
对一行上的 $2n$ 个位置，按从左到右的次序依次编上 $1,2,3,4, \cdots, 2 n-1,2 n$ 号．对任一 $i \in\{1,2, \cdots, n-1, n\}$，设其中一 $i$ 占据 $a_i$ 号位，另一 $i$ 占据 $b_i$ 号位，无妨设 $a_i<b_i$．如果所要求的排列 $P^{\ast}$ 存在，应有 $b_{i}-a_{i}=i+1, i=1,2, \cdots, n$ 由此得 $a_{i}+b_{i}=2 a_{i}+i+1$ 将上式双方求和 $\displaystyle \sum\limits_{i=1}^{n}\left(a_{i}+b_{i}\right)=\sum_{i=1}^{n} 2 a_{i}+\sum_{i=1}^{n}(i+1)$ 上式左方是一切位置号码之和，应等于 $1+2+\cdots+2 n=n(2 n+1)$ 可是 $\displaystyle \sum\limits_{i=1}^{n} 2 a_{i}+\sum_{i=1}^{n}(i+1)=$ 偶数 $+n+\frac{n(n+1)}{2}$ 因此，我们有 $2 n^{2}=$ 偶数 $+\frac{n(n+1)}{2}$ 也可以说 $\dfrac{n(n+1)}{2}$ 为一偶数，达到了证法一所得的同样的结论．
证法三
如果说前一证法中还要用到若干个自然数之和的公式，那么当前这一证法更为初等，几乎不同任何特殊的知识．在证法二中，我们已经得到 $a_{i}+b_{i}=2 a_{i}+i+1$，这也可以说成 $a_{i}+b_{i}=$ 偶数 $i+1$ 仔细观察上式可知，若 $i$ 为偶数时，$a_i+b_i$ 等于奇数，这表明 $a_i$ 与 $b_i$ 奇偶性不同．也就是说，对于偶数 $i$，其中的一个被排在奇号位置上，另一个一定被排在偶号位置上．若 $i$ 为奇数时，则 $a_i+b_i$ 等于偶数，即 $a_i$ 与 $b_i$ 有相同的奇偶性，那就是说，如果 $a_i$ 是奇数，$b_i$ 必为奇数．或者说，对于奇数 $i$，若有一个 $i$ 出现在奇号位置上，那么另一个 $i$ 也将出现在奇号位置上．这表明，奇号位上的奇数必为偶数个，设此数为 $2m$（$m$ 为非负整数）．但是，编号为奇数的位置有 $n$ 个，而 $1,2, \cdots, n$ 中，偶数的个数为 $[\dfrac{n}{2}]$，这里 $[x]$ 表示不超过 $x$ 的最大整数．这样，我们得出等式 $n=\left[\dfrac{n}{2}\right]+2 m$ 当 $n=1986$ 时，上式变为 $1986=993+2 m$，由此可导出 $993$ 是一偶数，是一矛盾．这个矛盾说明，所要求的排列不存在．
一般地，当 $n \equiv 1,2(\bmod 4)$ 时，代入 $n[n / 2]+2 m$ 都将产生同样的矛盾．而当 $n \equiv 0,3(\bmod 4)$ 时，都不会产生明显的矛盾．因此，这里得出的结论，同前面证法得出的结论是完全相同的．
条件 $n \equiv 0,3(\bmod 4)$ 对于所要求的排列的存在性是否也是充分的呢？国外有人已经作出了肯定的回答．
以下给出三种证法．这一种证法多少带有高等数学的色彩，主要的思想与 $ n $ 阶行列式的理论基础—置换—有些关系；第二种证法简单一些，只涉及前若干个自然数的求和公式，这时高中数学课本中的内容；第三种证法几乎不需要多少知识，但体现着巧妙地思考，这一证法，是参加冬令营的一位上海女同学的答卷．
证法一
对于 $ 1,1,2,2,\cdots,n,n $ 的任一排列，用一个大写字母，例如 $ P $ 来表示．设想对于 某一确定的排列 $ P $，在其中，两个 $ k $ 之间夹着 $ R_k $ 个数，这里 $ k=1,2,\cdots,n $，定义 $ R(P)=R_{1}+R_{2}+\cdots+R_{n} $ 它是一个非负整数，我们称 $ R(P)$ 为排列 $ P $ 的"指数"．
现在，对调 $ P $ 中某相邻两个数，例如 $ i,j $，无妨设 $ i\ne j $，其余的数均保留在原来的位置上，得出了一个新的排列 $ Q $．我们来看两个指数 $ R(P)$ 与 $ R(Q)$ 之间的关系．
设 $ P=\begin{vmatrix}\begin{array}{c|c|c|c|c|c|c|c}\hline
\cdots & i & \cdots & i & j & \cdots & j & \cdots\\\hline
\end{array}\end{vmatrix} $ 故 $ Q=\begin{vmatrix}\begin{array}{c|c|c|c|c|c|c|c}\hline
\cdots & i & \cdots & j & i & \cdots & j & \cdots\\\hline
\end{array}\end{vmatrix} $
设在 $ P $ 中两个 $ i $ 之间夹着 $ R_i $ 个数，两个 $ j $ 之间夹着 $ R_j$ 个数，显然，在 $Q$ 中，两个 $i$ 之间夹着 $R_i+1$ 个数，而两个 $j$ 之间夹着 $R_j+1$ 个数．由于其他各对数的位置没有变化，因此 $R(Q)=R(P)+2$．此式也可写为 $R(P)=R(Q)-2$．再设 $ P=\begin{vmatrix}\begin{array}{c|c|c|c|c|c|c|c}\hline
\cdots & j & \cdots & i & \cdots & i & j & \cdots\\\hline
\end{array}\end{vmatrix} $ 故 $ Q=\begin{vmatrix}\begin{array}{c|c|c|c|c|c|c|c}\hline
\cdots & j & \cdots & i & \cdots & j & i & \cdots\\\hline
\end{array}\end{vmatrix} $ 在排列 $Q$ 中，显然两个 $i$ 之间夹的数的个数为 $R_i+1$，两个 $j$ 之间夹的数的个数为 $R_j-1$，由此可知 $R(Q)=R(P)$．
所以，不论 $P$ 为怎样的一个排列，如果只对换 $P$ 中的相邻的两数，保持其余的各数不变，得出的排列为 $Q$，那么必有 $R(P)=R(Q)\pm 2$．这就是说，这样的两个排列 $P$ 与 $Q$，其指数具有相同的奇偶性．
经过有限次的相邻两数之间的对换，任一排列 $P$ 总可以变为排列 $ P_0=\begin{vmatrix}\begin{array}{c|c|c|c|c|c|c|c|c}\hline
1 & 1 & 2 & 2 & 3 & 3 & \cdots & n & n\\\hline
\end{array}\end{vmatrix} $ 显然 $R\left(P_{0}\right)=0+0+\cdots+0=0$，结合上述推理可知：$1,1,2,2,\cdots,n,n$ 的任一排列的指数只能为偶数．今设所要求的排列存在，记为 $P^{\ast}$．这一排列的指数是 $R\left(P^{*}\right)=1+2+\cdots+n=n(n+1) / 2$ 按前面的说法，它应当为偶数，记为 $2t$，于是 $n(n+1)=4 t$ 这里 $t$ 为正整数．当 $n$ 为奇数时，$4$ 应整除 $n+1$，亦即 $n=4m+3$，这里 $m$ 为非负整数，当 $n$ 为偶数时，$n+1$ 为奇数，这时 $4$ 必整除 $n$，所以 $n=4m$，这里 $m$ 为某一正整数．
这就是说，如果具有所有要求的性质的排列存在，那么必须有 $n\equiv 0$ 或 $3\pmod{4}$．当 $n=1986$ 时，此数被 $4$ 除之余 $2$，不满足上述关系，因此，一定不能排成所要求的形式．
证法二
对一行上的 $2n$ 个位置，按从左到右的次序依次编上 $1,2,3,4, \cdots, 2 n-1,2 n$ 号．对任一 $i \in\{1,2, \cdots, n-1, n\}$，设其中一 $i$ 占据 $a_i$ 号位，另一 $i$ 占据 $b_i$ 号位，无妨设 $a_i<b_i$．如果所要求的排列 $P^{\ast}$ 存在，应有 $b_{i}-a_{i}=i+1, i=1,2, \cdots, n$ 由此得 $a_{i}+b_{i}=2 a_{i}+i+1$ 将上式双方求和 $\displaystyle \sum\limits_{i=1}^{n}\left(a_{i}+b_{i}\right)=\sum_{i=1}^{n} 2 a_{i}+\sum_{i=1}^{n}(i+1)$ 上式左方是一切位置号码之和，应等于 $1+2+\cdots+2 n=n(2 n+1)$ 可是 $\displaystyle \sum\limits_{i=1}^{n} 2 a_{i}+\sum_{i=1}^{n}(i+1)=$ 偶数 $+n+\frac{n(n+1)}{2}$ 因此，我们有 $2 n^{2}=$ 偶数 $+\frac{n(n+1)}{2}$ 也可以说 $\dfrac{n(n+1)}{2}$ 为一偶数，达到了证法一所得的同样的结论．
证法三
如果说前一证法中还要用到若干个自然数之和的公式，那么当前这一证法更为初等，几乎不同任何特殊的知识．在证法二中，我们已经得到 $a_{i}+b_{i}=2 a_{i}+i+1$，这也可以说成 $a_{i}+b_{i}=$ 偶数 $i+1$ 仔细观察上式可知，若 $i$ 为偶数时，$a_i+b_i$ 等于奇数，这表明 $a_i$ 与 $b_i$ 奇偶性不同．也就是说，对于偶数 $i$，其中的一个被排在奇号位置上，另一个一定被排在偶号位置上．若 $i$ 为奇数时，则 $a_i+b_i$ 等于偶数，即 $a_i$ 与 $b_i$ 有相同的奇偶性，那就是说，如果 $a_i$ 是奇数，$b_i$ 必为奇数．或者说，对于奇数 $i$，若有一个 $i$ 出现在奇号位置上，那么另一个 $i$ 也将出现在奇号位置上．这表明，奇号位上的奇数必为偶数个，设此数为 $2m$（$m$ 为非负整数）．但是，编号为奇数的位置有 $n$ 个，而 $1,2, \cdots, n$ 中，偶数的个数为 $[\dfrac{n}{2}]$，这里 $[x]$ 表示不超过 $x$ 的最大整数．这样，我们得出等式 $n=\left[\dfrac{n}{2}\right]+2 m$ 当 $n=1986$ 时，上式变为 $1986=993+2 m$，由此可导出 $993$ 是一偶数，是一矛盾．这个矛盾说明，所要求的排列不存在．
一般地，当 $n \equiv 1,2(\bmod 4)$ 时，代入 $n[n / 2]+2 m$ 都将产生同样的矛盾．而当 $n \equiv 0,3(\bmod 4)$ 时，都不会产生明显的矛盾．因此，这里得出的结论，同前面证法得出的结论是完全相同的．
条件 $n \equiv 0,3(\bmod 4)$ 对于所要求的排列的存在性是否也是充分的呢？国外有人已经作出了肯定的回答．
答案
解析
备注
