将 $16$ 个数 $\dfrac{1}{2002}, \dfrac{1}{2003}, \cdots, \dfrac{1}{2017}$ 分成两组，每组 $8$ 个数记其中一组的 $8$ 个数之和为 $A$，另一组的 $8$ 个数之和为 $B$．请给出一种分组方案使得 $|A-B|$ 最小，并说明理由．
【难度】
【出处】
2017第16届CGMO试题
【标注】
【答案】
略
【解析】
换个描述方式：记 $M=2002$，把集合 $T=\{0,1,2, \cdots, 15\}$ 分成两个互补的八元子集 $A、B$．记 $\displaystyle A^{*}=\sum\limits_{t \in A} \frac{1}{t+M}, B^{*}=\sum_{t \in B} \frac{1}{t+M}$，我们的目标是 $\left|A^{*}-B^{*}\right|$ 最小化．
对非负整数 $m$，记集合 $A、B$ 的元素的 $m$ 次方之和分别是 $\displaystyle A_{m}=\sum\limits_{t \in A} t^{m}$ 与 $\displaystyle B_{m}=\sum\limits_{t \in B} t^{m}$，（其中 $A_{0}=B_{0}=8$ 是元素个数）．我们注意到：
$A_{1}+B_{1}=\sum_{t=0}^{15} t=120$
$A_{2}+B_{2}=\sum_{t=0}^{15} t^{2}=1240$
$A_{3}+B_{3}=\sum_{t=0}^{15} t^{3}=14400$
断言 $\left|A^{*}-B^{*}\right|$ 的大小与 $\left|A_{0}-B_{0}\right|,\left|A_{1}-B_{1}\right|, \cdots,\left|A_{m}-B_{m}\right|, \cdots$ 的大小很有关系．存在唯一的正整数 $k$ 使得 $A_{0}=B_{0}, A_{1}=B_{1}, \cdots, A_{k-1}=B_{k-1}$，但 $ A_{k} \neq B_{k}$．
如果找到一个 $k+1$ 次首一多项式 $G_{k}(t)=t^{k+1}+g_{k, k} t^{k}+\cdots+g_{k, 1} t+g_{k, 0}$ 满足对每个 $t \in T=\{0,1,2, \cdots, 15\}$ 都有 $C_{k}^- \leqslant C_{k}(t) \leqslant C_{k}^{+}$，其中下界 $C_{k}^{-} \leqslant 0$，上界 $C_{k}^{+} \geqslant 0$，并且上下界之差 $C_{k}=C_{k}^{+}-C_{k}^{-}$ 不是很大，我们就可以对 $\left|A^{*}-B^{*}\right|$ 做估计：
我们考虑多项式 $G_k(t)$ 除以一次多项式 $t+M$ 的结果，应该得到余式是常数多项式 $R_{k}=G_{k}(-M)$，以及商式是 $k$ 次首一多项式：$\dfrac{G_{k}(t)-G_{k}(-M)}{t+M}=t^{k}+c_{k, k-1} t^{k-1}+\cdots+c_{k,0}$
其中 $C_{k, k-1}, \cdots, \quad C_{k,0}$ 是固定的但不必具体计算的系数．这时：$\begin{aligned} \dfrac{G_{k}(t)}{t+M} &=\dfrac{G_{k}(t)-G_{k}(-M)}{t+M}+\dfrac{G_{k}(-M)}{t+M} =t^{k}+c_{k, k-1} t^{k-1}+\cdots+c_{k,0}+\dfrac{R_{k}}{t+M} \in\left[\dfrac{C_{k}^{-}}{M}, \dfrac{C_{k}^{+}}{M}\right] \end{aligned}$
上式分别对于集合 $A、B$ 中的 $8$ 个元素求和可得：
$8\times\dfrac{C_k^-}{M}\leqslant A_k+c_{k,k-1}A_{k-1}+\cdots+c_{k,0}A_0+R_k\times A^{\ast}\leqslant 8\times\dfrac{C_k^+}{M}$
$8\times\dfrac{C_k^-}{M}\leqslant B_k+c_{k,k-1}B_{k-1}+\cdots+c_{k,0}B_0+R_k\times B^{\ast}\leqslant 8\times\dfrac{C_k^+}{M}$
上面两式相减，并由已知的 $A_{0}=B_{0}, A_{1}=B_{1}, \cdots, A_{k-1}=B_{k-1}$，可得 $-8 \times \dfrac{C_{k}}{M} \leqslant\left(A_{k}-B_{k}\right)+R_{k} \times\left(A^{*}-B^{*}\right) \leqslant 8 \times \dfrac{C_{k}}{M}$
即 $\dfrac{1}{\left|R_{A}\right|}\times\left(\left|A_{k}-B_{k}\right|+\dfrac{8 C_{k}}{M}\right) \geqslant\left|A^{*}-B^{*}\right| \geqslant \dfrac{1}{\left|R_{A}\right|} \times\left(\left|A_{k}-B_{k}\right|-\dfrac{8 C_{k}}{M}\right)$．
若 $k=1, A_{1} \neq B_{1}$，由奇偶性可知 $\left|A_{1}-B_{1}\right|$ 至少是 $ 2$．取多项式 $G_1(t)=t(t-15)$ 满足 $-56 \leqslant G_1(t) \leqslant 0$，对任意 $t \in T$，上下界之差 $C_{1}=56$，余数 $R_{1}=M(M+15)=2002 \times 2017$，我们有 $\left|A^{*}-B^{*}\right| \geqslant \dfrac{1}{\left|R_{1}\right|} \times\left(\left|A_{1}-B_{1}\right|-\dfrac{8 C_{1}}{M}\right) \geqslant \dfrac{2-0.25}{R_{1}}>0.4 \times 10^{-6}$ 差比较大．
若 $k=2, A_{2} \neq B_{2}$，由奇偶性知 $\left|A_{2}-B_{2}\right|$ 至少是 $ 2$．取多项式 $G_2(t)=t(t-11)^2$ 满足 $0 \leqslant G_2(t) \leqslant 240$，对任意 $t \in T$，这时 $C_{2}=240$，$R_{2}=-M(M+11)^{2}=-2002 \times 2013^{2}$．我们有 $\left|A^{*}-B^{*}\right| \geqslant \dfrac{1}{\left|R_{2}\right|} \times\left(\left|\Lambda_{2}-B_{2}\right|-\dfrac{8 C_{2}}{M}\right) \geqslant \dfrac{2-1}{R_{2}}>0.12 \times 10^{-9}$ 差也比较大．
若 $k=3, A_{3} \neq B_{3}$，注意到 $6 | t^{3}-t=(t-1) t(t+1)$，所以 $\dfrac{A_{3}-A_{1}}{6}$ 与 $\dfrac{B_{3}-B_{1}}{6}$ 都是整数，而两者之和是偶数，故两者之差也是偶数由于 $A_{1}=B_{1}$，我们得到 $A_{3}-B_{3}$ 一定是 $12$ 的倍数．$\left|A_{3}-B_{3}\right|$ 至少是 $12$．
取多项式 $G_{3}(t)=t(t-7)(t-8)(t-15)$ 满足 $-28^{2} \leqslant G_{3}(t) \leqslant 0$，对任意 $t\in T$，上下界之差 $C_{3}=784$．余数 $R_{3}=M(M+2)(M+8)(M+15)=2002 \times 2009 \times 2010 \times 2017$，我们有 $\begin{aligned}\left|A^{*}-B^{*}\right| & \geqslant \dfrac{1}{\left|R_{3}\right|} \times\left(\left|A_{3}-B_{3}\right|-\dfrac{8 C_{3}}{M}\right) \geqslant \dfrac{12-8 \times 0.4}{R_{3}}>0.5 \times 10^{-12} \end{aligned}$ 差还是比较大．
我们看到只有 $A_{1}=B_{1}, A_{2}=B_{2}, A_{3}=B_{3}$ 才可能使差 $\left|A^{*}-B^{*}\right|$ 变得更小．考虑 $0.1,2, \cdots, 15$ 的二进制表示中含奇数个 $1$ 还是偶数个 $1$ 来给出一个分组：
$A=\{0,3,5,6,9,10,12,15\} ; B=\{1,2,4,7,8,11,13,14\}$；①
这个分组满足 $A_{1}=B_{1}, A_{2}=B_{2}, A_{3}=B_{3}$，同时 $A_{4}-B_{4}=1536$．
我们取多项式 $G_{4}(t)=t(t-5)^{2}(t-13)(t-14)$ 满足 $0 \leqslant G_{4}(t) \leqslant 3000$．对任意 $t \in T$，这时 $C_{4}=3000$，$R_{4}=-M(M+5)^{2}(M+13)(M+14)=-2002 \times 2007^{2} \times 2015 \times 2016$．我们有 $\left|A^{*}-B^{*}\right| \leqslant \dfrac{1}{\left|R_{4}\right|} \times\left(\left|A_{4}-B_{4}\right|+\dfrac{8 C_{4}}{M}\right)<\dfrac{1536+8 \times 1.5}{R_{4}}<50 \times 10^{-15}$，差比较小了．
最后我们证明当分组满足 $A_{1}=B_{1}, A_{2}=B_{2}, A_{3}=B_{3}$ 时，① 式是唯一的方式注意立方数模 $ 9$ 的余数很有特点．即当 $t $ 模 $3 $ 余 $0, 1, 2$ 时，$t^3$ 模 $9$ 的余数分别是 $0, 1, —1$，而 $(t+ 1)^3$ 模 $ 9 $ 的余数分别是 $1, -1, 0$．
由 $\displaystyle \sum\limits_{t=0}^{15} t^{3} \equiv 0(\bmod 9)$，可知 $\displaystyle \sum\limits_{t \in A} t^{3}=\sum_{t \in B} t^{3} \equiv 0(\bmod 9)$；
设在 $A$ 组中模 $3$ 余 $0、1、2$ 的元素个数分别为 $a_{0}, a_{1}, a_{2}$，在 $B$ 组中模 $3$ 余 $0、1、2$ 的元素个数分别为 $b_{0}, b_{1}, b_{2}$，我们有 $a_{1}-a_{2} \equiv 0(\bmod 9)$，$a_{0}-a_{1} \equiv 5(\bmod 9)$ 与 $b_{1}-b_{2} \equiv 0(\bmod 9), b_{0}-b_{1} \equiv 5(\bmod 9)$．
由于 $a_{0}, a_{1}, a_{2}, b_{0}, b_{1}, b_{2}$ 都是 $0\sim 6$ 的整数，我们可知 $a_{1}=a_{2}, b_{1}=b_{2}$ 并且 $a_{0}-a_{1}$ 与 $ b_{0}-b_{1}$ 只能是 $5$ 或 $-4$．另一方面由于 $\left(a_{0}-a_{1}\right)+\left(b_{0}-b_{1}\right)=1$，所以 $a_{0}-a_{1}$ 与 $ b_{0}-b_{1}$ 恰好是一个 $5$ 和一个 $-4$．不妨设 $a_{0}-a_{1}=5$，这样可得 $a_{0}=6, a_{1}=a_{2}=1$，即集合 $A$ 包含了 $T$ 中的六个 $3$ 的倍数 $\{0,3,6,9,12,15\}$．这时可算得集合 $A$ 中其他两个数的加和为 $15$，平方和为 $125$，它们是 $\{5,10\}$，故集合 $A=\{0,3,5,6,9,10,12,15\}$．所以满足 $A_{1}=B_{1}, A_{2}=B_{2},A_{3}=B_{3}$ 的分组方式是唯一的（在两组可交换的意义下）．
对非负整数 $m$，记集合 $A、B$ 的元素的 $m$ 次方之和分别是 $\displaystyle A_{m}=\sum\limits_{t \in A} t^{m}$ 与 $\displaystyle B_{m}=\sum\limits_{t \in B} t^{m}$，（其中 $A_{0}=B_{0}=8$ 是元素个数）．我们注意到：
$A_{1}+B_{1}=\sum_{t=0}^{15} t=120$
$A_{2}+B_{2}=\sum_{t=0}^{15} t^{2}=1240$
$A_{3}+B_{3}=\sum_{t=0}^{15} t^{3}=14400$
断言 $\left|A^{*}-B^{*}\right|$ 的大小与 $\left|A_{0}-B_{0}\right|,\left|A_{1}-B_{1}\right|, \cdots,\left|A_{m}-B_{m}\right|, \cdots$ 的大小很有关系．存在唯一的正整数 $k$ 使得 $A_{0}=B_{0}, A_{1}=B_{1}, \cdots, A_{k-1}=B_{k-1}$，但 $ A_{k} \neq B_{k}$．
如果找到一个 $k+1$ 次首一多项式 $G_{k}(t)=t^{k+1}+g_{k, k} t^{k}+\cdots+g_{k, 1} t+g_{k, 0}$ 满足对每个 $t \in T=\{0,1,2, \cdots, 15\}$ 都有 $C_{k}^- \leqslant C_{k}(t) \leqslant C_{k}^{+}$，其中下界 $C_{k}^{-} \leqslant 0$，上界 $C_{k}^{+} \geqslant 0$，并且上下界之差 $C_{k}=C_{k}^{+}-C_{k}^{-}$ 不是很大，我们就可以对 $\left|A^{*}-B^{*}\right|$ 做估计：
我们考虑多项式 $G_k(t)$ 除以一次多项式 $t+M$ 的结果，应该得到余式是常数多项式 $R_{k}=G_{k}(-M)$，以及商式是 $k$ 次首一多项式：$\dfrac{G_{k}(t)-G_{k}(-M)}{t+M}=t^{k}+c_{k, k-1} t^{k-1}+\cdots+c_{k,0}$
其中 $C_{k, k-1}, \cdots, \quad C_{k,0}$ 是固定的但不必具体计算的系数．这时：$\begin{aligned} \dfrac{G_{k}(t)}{t+M} &=\dfrac{G_{k}(t)-G_{k}(-M)}{t+M}+\dfrac{G_{k}(-M)}{t+M} =t^{k}+c_{k, k-1} t^{k-1}+\cdots+c_{k,0}+\dfrac{R_{k}}{t+M} \in\left[\dfrac{C_{k}^{-}}{M}, \dfrac{C_{k}^{+}}{M}\right] \end{aligned}$
上式分别对于集合 $A、B$ 中的 $8$ 个元素求和可得：
$8\times\dfrac{C_k^-}{M}\leqslant A_k+c_{k,k-1}A_{k-1}+\cdots+c_{k,0}A_0+R_k\times A^{\ast}\leqslant 8\times\dfrac{C_k^+}{M}$
$8\times\dfrac{C_k^-}{M}\leqslant B_k+c_{k,k-1}B_{k-1}+\cdots+c_{k,0}B_0+R_k\times B^{\ast}\leqslant 8\times\dfrac{C_k^+}{M}$
上面两式相减，并由已知的 $A_{0}=B_{0}, A_{1}=B_{1}, \cdots, A_{k-1}=B_{k-1}$，可得 $-8 \times \dfrac{C_{k}}{M} \leqslant\left(A_{k}-B_{k}\right)+R_{k} \times\left(A^{*}-B^{*}\right) \leqslant 8 \times \dfrac{C_{k}}{M}$
即 $\dfrac{1}{\left|R_{A}\right|}\times\left(\left|A_{k}-B_{k}\right|+\dfrac{8 C_{k}}{M}\right) \geqslant\left|A^{*}-B^{*}\right| \geqslant \dfrac{1}{\left|R_{A}\right|} \times\left(\left|A_{k}-B_{k}\right|-\dfrac{8 C_{k}}{M}\right)$．
若 $k=1, A_{1} \neq B_{1}$，由奇偶性可知 $\left|A_{1}-B_{1}\right|$ 至少是 $ 2$．取多项式 $G_1(t)=t(t-15)$ 满足 $-56 \leqslant G_1(t) \leqslant 0$，对任意 $t \in T$，上下界之差 $C_{1}=56$，余数 $R_{1}=M(M+15)=2002 \times 2017$，我们有 $\left|A^{*}-B^{*}\right| \geqslant \dfrac{1}{\left|R_{1}\right|} \times\left(\left|A_{1}-B_{1}\right|-\dfrac{8 C_{1}}{M}\right) \geqslant \dfrac{2-0.25}{R_{1}}>0.4 \times 10^{-6}$ 差比较大．
若 $k=2, A_{2} \neq B_{2}$，由奇偶性知 $\left|A_{2}-B_{2}\right|$ 至少是 $ 2$．取多项式 $G_2(t)=t(t-11)^2$ 满足 $0 \leqslant G_2(t) \leqslant 240$，对任意 $t \in T$，这时 $C_{2}=240$，$R_{2}=-M(M+11)^{2}=-2002 \times 2013^{2}$．我们有 $\left|A^{*}-B^{*}\right| \geqslant \dfrac{1}{\left|R_{2}\right|} \times\left(\left|\Lambda_{2}-B_{2}\right|-\dfrac{8 C_{2}}{M}\right) \geqslant \dfrac{2-1}{R_{2}}>0.12 \times 10^{-9}$ 差也比较大．
若 $k=3, A_{3} \neq B_{3}$，注意到 $6 | t^{3}-t=(t-1) t(t+1)$，所以 $\dfrac{A_{3}-A_{1}}{6}$ 与 $\dfrac{B_{3}-B_{1}}{6}$ 都是整数，而两者之和是偶数，故两者之差也是偶数由于 $A_{1}=B_{1}$，我们得到 $A_{3}-B_{3}$ 一定是 $12$ 的倍数．$\left|A_{3}-B_{3}\right|$ 至少是 $12$．
取多项式 $G_{3}(t)=t(t-7)(t-8)(t-15)$ 满足 $-28^{2} \leqslant G_{3}(t) \leqslant 0$，对任意 $t\in T$，上下界之差 $C_{3}=784$．余数 $R_{3}=M(M+2)(M+8)(M+15)=2002 \times 2009 \times 2010 \times 2017$，我们有 $\begin{aligned}\left|A^{*}-B^{*}\right| & \geqslant \dfrac{1}{\left|R_{3}\right|} \times\left(\left|A_{3}-B_{3}\right|-\dfrac{8 C_{3}}{M}\right) \geqslant \dfrac{12-8 \times 0.4}{R_{3}}>0.5 \times 10^{-12} \end{aligned}$ 差还是比较大．
我们看到只有 $A_{1}=B_{1}, A_{2}=B_{2}, A_{3}=B_{3}$ 才可能使差 $\left|A^{*}-B^{*}\right|$ 变得更小．考虑 $0.1,2, \cdots, 15$ 的二进制表示中含奇数个 $1$ 还是偶数个 $1$ 来给出一个分组：
$A=\{0,3,5,6,9,10,12,15\} ; B=\{1,2,4,7,8,11,13,14\}$；①
这个分组满足 $A_{1}=B_{1}, A_{2}=B_{2}, A_{3}=B_{3}$，同时 $A_{4}-B_{4}=1536$．
我们取多项式 $G_{4}(t)=t(t-5)^{2}(t-13)(t-14)$ 满足 $0 \leqslant G_{4}(t) \leqslant 3000$．对任意 $t \in T$，这时 $C_{4}=3000$，$R_{4}=-M(M+5)^{2}(M+13)(M+14)=-2002 \times 2007^{2} \times 2015 \times 2016$．我们有 $\left|A^{*}-B^{*}\right| \leqslant \dfrac{1}{\left|R_{4}\right|} \times\left(\left|A_{4}-B_{4}\right|+\dfrac{8 C_{4}}{M}\right)<\dfrac{1536+8 \times 1.5}{R_{4}}<50 \times 10^{-15}$，差比较小了．
最后我们证明当分组满足 $A_{1}=B_{1}, A_{2}=B_{2}, A_{3}=B_{3}$ 时，① 式是唯一的方式注意立方数模 $ 9$ 的余数很有特点．即当 $t $ 模 $3 $ 余 $0, 1, 2$ 时，$t^3$ 模 $9$ 的余数分别是 $0, 1, —1$，而 $(t+ 1)^3$ 模 $ 9 $ 的余数分别是 $1, -1, 0$．
由 $\displaystyle \sum\limits_{t=0}^{15} t^{3} \equiv 0(\bmod 9)$，可知 $\displaystyle \sum\limits_{t \in A} t^{3}=\sum_{t \in B} t^{3} \equiv 0(\bmod 9)$；
设在 $A$ 组中模 $3$ 余 $0、1、2$ 的元素个数分别为 $a_{0}, a_{1}, a_{2}$，在 $B$ 组中模 $3$ 余 $0、1、2$ 的元素个数分别为 $b_{0}, b_{1}, b_{2}$，我们有 $a_{1}-a_{2} \equiv 0(\bmod 9)$，$a_{0}-a_{1} \equiv 5(\bmod 9)$ 与 $b_{1}-b_{2} \equiv 0(\bmod 9), b_{0}-b_{1} \equiv 5(\bmod 9)$．
由于 $a_{0}, a_{1}, a_{2}, b_{0}, b_{1}, b_{2}$ 都是 $0\sim 6$ 的整数，我们可知 $a_{1}=a_{2}, b_{1}=b_{2}$ 并且 $a_{0}-a_{1}$ 与 $ b_{0}-b_{1}$ 只能是 $5$ 或 $-4$．另一方面由于 $\left(a_{0}-a_{1}\right)+\left(b_{0}-b_{1}\right)=1$，所以 $a_{0}-a_{1}$ 与 $ b_{0}-b_{1}$ 恰好是一个 $5$ 和一个 $-4$．不妨设 $a_{0}-a_{1}=5$，这样可得 $a_{0}=6, a_{1}=a_{2}=1$，即集合 $A$ 包含了 $T$ 中的六个 $3$ 的倍数 $\{0,3,6,9,12,15\}$．这时可算得集合 $A$ 中其他两个数的加和为 $15$，平方和为 $125$，它们是 $\{5,10\}$，故集合 $A=\{0,3,5,6,9,10,12,15\}$．所以满足 $A_{1}=B_{1}, A_{2}=B_{2},A_{3}=B_{3}$ 的分组方式是唯一的（在两组可交换的意义下）．
答案
解析
备注
