题目

查看数据源：5d12d999210b28021fc7785c

已知 $a_{1}, a_{2}, \cdots, a_{11}$ 为给定的 $11$ 个互不相同的正整数，且总和小于 $2 007$．在黑板上依次写若 $1,2, \cdots, 2 007$ 这 $2 007$ 个数．将连续的 $22$ 次操作定义为一个操作组：第 $i$ 次操作可以从黑板上现有的数中任选一个数，当 $1 \leqslant i \leqslant 11$ 时，加上 $a_i$ 当 $12 \leqslant i \leqslant 22$ 时，减去 $a_{i-11}$．如果最终结果为 $1,2, \cdots, 2007$ 的偶排列 $^ ① $ 。则称这个操作组为优的；如果最终结果为 $1,2,\cdots,2007$ 的奇排列，则称这个操作组为次优的．问优的操作组与次优的操作组哪种多，多多少？

【难度】

【出处】

2007第22届CMO试题

【标注】

知识点
>
二试组合部分

【答案】

略

【解析】

优的操作组更多，多了 $\displaystyle \prod\limits_{i=1}^{11} a_{i}$ 个．
我们引人一般的记号：如果黑板上写着 $1,2,\cdots,n$ 这 $n$ 个数，一个操作组被定义为 $l$ 次连续操作：第i 次操作可以从黑板上现有的数中任选出一个，加上 $b_i$，这里 $b_{i} \in \mathbf{Z}(1 \leqslant i \leqslant l)$，如果最终结果为 $1,2, \cdots,n$ 的偶（奇）排列，则称这操作组为优（次优）的，优的操作组的数目与次优的操作组的数目之差记为 $f\left(b_{1}, b_{2}, \cdots, b_{l};n\right)$ 以下先来讨论 $f$ 的性质．
首先，对任意 $1\leqslant i,j\leqslant l$，交换 $b_i$ 与 $b_j$ 的取值不会影响 $f$．事实上，只须要将操作组的第 $i$ 次与第 $j$ 次操作对调；换言之，第 $i$ 次操作时进行原来的第 $j$ 次操作，把原来计划进行的第 $j$ 次操作选定的数加上 $b_j$，而第 $j$ 次操作时进行原来的第 $i$ 次操作．对调后操作组的结果不变，因而优（次优）操作组的数目不变，故 $f$ 不变．

答案解析备注

① $1,2, \cdots, n$ 的一个排列 $x_{1}, x_{2}, \cdots, x_{n}$ $x_{1}, x_{2}, \cdots, x_{n}$ 称为偶排列，如果 $\prod_{i>j}\left(x_{i}-x_{j}\right)$ 为正数，否则 称为奇排列． 其次，我们只须要计算这样的优的（次优的）操作组的数目：每一步操作后，黑板上没有任何两个数相同，这样的操作组称为具有性质 $P$ 的操作组．可以证明，具有性质 $P$ 的优的操作组数目与次优的操作组数目之差也等于 $f\left(b_{1}, b_{2}, \cdots, b_{l} ; n\right)$． 事实上，只要证明，在不具有性质 $P$ 的操作组中，优的操作组 与次优的操作组一样多．如果一个操作组最先第 $i$ 步操作导致黑板上出现两个相等的数，例如第 $p$ 个数和第 $q$ 个数相等 $(1 \leqslant p<q \leqslant n )$，那么对该操作组的后 $l-i$ 步操作进行如下的改动：对第 $p$ 个数的操作改成对第 $q$ 个数进行，对第 $q$ 个数的操作改成对第 $p$ 个数进行，那么这个新的操作组最终显示的结果将是在原操作组的结果上对第 $p,q$ 个数进行了对换，不难发现，对换一个排列中 任何两个数都会导致排列的奇偶性改变．所以，优的操作组通过 上述改动可以和次优的操作组构成一一对应，因而不具备性质 $P$ 的操作组中，优的与次优的一样多． 现在我们对 $m$ 用数学归纳法证明如下的结果：$a_{1}, a_{2}, \cdots, a_{m}$ 为 $m$ 个互不相同的正整数且总和小于 $n$，则 $\displaystyle f\left(a_{1}, a_{2}, \cdots, a_{m},-a_{1},-a_{2}, \cdots,-a_{m} ; n\right)=\prod\limits_{j=1}^{m} a_{j}$ ① 当 $m= 1$ 时，考虑具有性质 $P$ 的优的和次优的操作组，必然 是从后 $a_1$ 个数中选上某个数加上 $a_1$，然后再将这个数加上 $-a_1$（否则得不到 $1,2,\cdots,n$ 的排列），所以优的操作组有 $a_1$ 个，次优的操作组有 $0$ 个，故 ① 成立． 假设 $m-1$ 时命题成立考虑 $m$ 时的命题．不妨设 $a_{1}<a_{2}<\cdots<a_n$．根据前面的讨论 $f\left(a_{1}, a_{2}, \cdots, a_{m},-a_{1},-a_{2}, \cdots,-a_{m} ; n\right)=f\left(a_{1},-a_{2},-a_{3}, \cdots,-a_{m}, a_{2}, a_{3}, \cdots, a_{m},-a_{1} ; n\right)$ 这时对于具有性质 $P$ 的优的和次优的操作组来说，第 $1$ 步操作可以从末 $a_1$ 个数中选取某数加上 $a_1$，而第 $2$ 步操作只能对前 $a_2$ 个数进行，第 $3$ 步操作只能对前 $a_2+a_3$ 个数进行，．．．，第 $m$ 步操作只能对前 $a_{2}+\cdots+a_{m}<n-a_{1}$ 个数进行，而第 $m+1 \sim 2 m-1$ 步操作也只能对前 $n-a_1$ 个数进行，否则前 $n-a_1$，个数最终的和小于 $1+2+\cdots+\left(n-a_{1}\right)$，操作组结束后黑板上的 $n$ 个数不为 $1,2, \cdots,n$ 的排列，第 $2m$ 步操作只能对第 $1$ 步操作时选定的数进行． 因此，第 $2\sim 2m -2$ 步操作必然是对前 $n-a_1$ 个数进行，它的结果也要得到 $1,2,\cdots,n -a_1$ 的偶（奇）排列，才能使总共 $2m$ 步 操作的结果得到 $1,2,\cdots,n$ 的偶（奇）排列．所以，中间 $2m-2$ 步操 作构成的对 $n-a_1$ 个数进行的每个具有性质 $P$ 的优（次优）的操 作组都可以对应 $a_1$ 个原来的具有性质 $P$ 的优（次优）的操作组，于是 $f\left(a_{1},-a_{2},-a_{3}, \cdots,-a_{m}, a_{2}, a_{3}, \cdots, a_{m},-a_{1} ; n\right)=a_{1} \cdot f\left(-a_{2},-a_{3}, \cdots,-a_{m}, a_{2}, a_{3}, \cdots, a_{m} ; n-a_{1}\right)$ 根据归纳假设 $\displaystyle f\left(-a_{2},-a_{3}, \cdots,-a_{m}, a_{2}, a_{3}, \cdots, a_{m} ; n-a_{1}\right)=f\left(a_{2}, a_{3}, \cdots, a_{m},-a_{2},-a_{3}, \cdots,-a_{m} ; n-a_{1}\right)=\prod\limits_{j=2}^{m} a_{j}$ 故 ① 在 $m $ 时亦成立． 所以由归纳法，① 得证． 在 ① 中取 $n = 2007,m = 11$，即得到本题的答案 $\displaystyle \prod\limits_{j=1}^{11} a_{j}$．