怎样将一群人分成两组，使他们各自的总体实力「旗鼓相当」？
在生活中，我们经常会遇到这样的场景：把一群人分成两组，使得两组人的实力尽可能相近。这个问题看起来简单，但实际操作的时候，却常常令人头疼。
**********
举个例子：一共有 16 个人，并且已知他们的实力排序（分别为第 1、2……16 名），把这 16 个人分成两组，每组 8 人，如何分组使得这两个小组的实力尽可能接近呢？
**********
一个最简单的思路是，要把最强的两个人分开（第 1 名在 A 组，第 2 名在 B 组），剩下的人随机分组（我们打篮球时就经常这么干）。
但这么分组偶然性太大了，如果第 3 名、第 4 名分在了同一组，那么这组的实力就太强了。
于是我们细化分组方案：把第 3 名和第 4 名也分开，考虑到当前第 1 名所在的 A 组实力比较强，所以就把较弱第 4 名分在 A 组，较强的第 3 名分在 B 组。
分好前 4 名的小组后，我们再来分第 5~8 名。第 8 名最弱，所以把他和第 1 名所在的 A 组分在一起，然后把第 7 名分在 B 组，而这个时候 A 组好像又比 B 组弱一点了，于是把第 5 名分到 A 组，第 6 名分到 B 组……
…………
细心的你大概会发现，这样的分组方式和「单败淘汰赛」的分组方式有点接近：
这种分组方式被用在了很多场景中，比如网球公开赛、NBA 季后赛等等。
通过这种分组方式，我们将所有人按照实力分成两组：
- A 组：1、4、5、8、9、12、13、16；
- B 组：2、3、6、7、10、11、14、15。
这种分组方式很合理吧？
未必。
**********
上面的分组方式，的确很适合淘汰赛，但是如果是分组对抗的话，还是有点问题的。
我们得知道这样一个事实：不同名次之间的实力差距，往往并不正比于他们的名次差。在大多数情况下，名次越高，名次之间的实力差距就越大。
比如说，对于前 8 名选手，我们觉得他们的实力和名次之间是线性关系，他们的实力可以量化为 8 分、7 分、6 分…… 2 分、1 分。但实际上，他们的实力和名次之间更接近于二次函数的关系，第 1 名到第 8 名的实力评分可能分别为：64 分、49 分、36 分…… 4 分、1 分。
如果这种关系成立，那么对于前 8 名来说，两个组的评分分别为：
- A组：8^{2} +5^{2} +4^{2} +1^{2}=106
- B组：7^{2} +6^{2} +3^{2} +2^{2}=98
这么看，似乎是 A 组更强一些了。
怎么消除这个差距呢？
我灵机一动：对于第 5 ~ 8 名这四个人，两组的人交换一下（「交叉分组」）试试？这样，A 组有第 1、4、6、7 名，B 组有第 2、3、5、8 名，他们的名次和依然相同，而他们评分的平方和：
- A组：8^{2} +5^{2} +3^{2} +2^{2}=102
- B组：7^{2} +6^{2} +4^{2} +1^{2}=102
也恰好相等！（P.S. 他们名次的平方和也同样相等）
似乎我们有了一些方向。对于第 9 ~ 16 名，我们可以进行类似的「交叉分组」：
- 把前 8 名在 A 组的 4 个人名次 +8 后，把对应的 4 个名次的人放到 B 组去；把前 8 名在 B 组的 4 个人名次 +8 后，把对应的 4 个名次放到 A 组去；
（如：因为 第 1 名在 A 组，所以 第 9 名就分到 B 组）
于是我们得到了最终的分组情况：
- A 组：1、4、6、7、10、11、13、16；
- B 组：2、3、5、8、9、12、14、15。
于是我们得到：
1+4+6+7+10+11+13+16=68=2+3+5+8+9+12+14+151^{2}+4^{2}+6^{2}+7^{2}+10^{2}+11^{2}+13^{2}+16^{2}=748=2^{2}+3^{2}+5^{2}+8^{2}+9^{2}+12^{2}+14^{2}+15^{2}
与此同时，我们还意外地发现：
1^{3}+4^{3}+6^{3}+7^{3}+10^{3}+11^{3}+13^{3}+16^{3}=9248=2^{3}+3^{3}+5^{3}+8^{3}+9^{3}+12^{3}+14^{3}+15^{3}连立方和都相等！
这是一个巧合吗？并不是！
**********
实际上，我们有更强的结论。用数学的语言说：
对于数字 1 到 2^{n} （n\in N,n\geq 2），如果我们按照以下方式分组：
- 1 在 A 组，2 在 B 组；
- 假设 1 到 2^{k} （k\in N,k\geq 1）已经分组完毕，其中 A 组从小到大依次是 a_{1}, a_{2},...,a_{2^{k-1}}，B 组从小到大依次是 b_{1}, b_{2},...,b_{2^{k-1}}，那么，将 2^{k} +1 到 2^{k+1} 按照如下方式分组：a_{2^{k-1}+t}=b_{t}+2^{k} ，b_{2^{k-1}+t}=a_{t}+2^{k} （t=1,2,...,2^{k-1}）。
那么，对于最终的分组：A:a_{1}, a_{2},...,a_{2^{n-1}}，B:b_{1}, b_{2},...,b_{2^{n-1}}，它们的 p 次幂和（p=1,2,...,n-1）都相等。
————
证明：
用归纳法。当 n=2 时，1 + 4 = 2 + 3，结论成立，
假设 n = k 时， A:a_{1}, a_{2},...,a_{2^{k-1}}，B:b_{1}, b_{2},...,b_{2^{k-1}}，两组数的 1,2,...k-1 次幂和都相等。
那么当 n = k + 1 时，
A:a_{1}, a_{2},...,a_{2^{k-1}},b_{1}+2^{k},b_{2}+2^{k},....,b_{2^{k-1}}+2^{k}B:b_{1}, b_{2},...,b_{2^{k-1}},a_{1}+2^{k},a_{2}+2^{k},....,a_{2^{k-1}}+2^{k}计算他们各自的 1,2,...k 次幂和，定义c_{i}=\sum_{j=1}^{2^{k-1}}{a_{j}^{i} } =\sum_{j=1}^{2^{k-1}}{b_{j}^{i} } (i=1,2,...k-1)
容易验证，对于1,2,...k-1 次幂和，两组数展开后都是关于c_{i}的多项式，且系数相等，所以总和相等，而对于 k 次幂和，两组数展开后关于 k 次幂的项完全相同，而不大于 k-1 次幂的项也可以表示成关于c_{i}的系数相等的多项式，所以总和也相等。所以 n= k+1 时，两组数的 1,2,...k-1 次幂和都相等。
证毕。
**********
【注1】上面的结论有一个简单的推论：
- 如果对于任意一个数 t ，对应函数 f(t) 只要是不高于 n-1 阶的多项式，那么 A 组和 B 组各自的 f(t) 的和也是相等的，这意味着 A 组 和 B 组的数的 1,2,...,n-1 阶矩 （平均值、方差、偏度、峰度……）也是相等的。
这说明，如果我们按照这种方式分组，两组的性质真的非常非常接近。我们终于找了了一种方法，将一群人分成两组，使他们各自的总体实力「旗鼓相当」。
————
【注2】如何迅速判断一个数 t 应该在 A 组 还是 B 组呢？
一个有趣的判断方式： 观察 t-1 的二进制表示中 1 的个数，如为偶数个，则在 A 组，如为奇数个，则在 B 组。如：要判断 12 在哪个组，判断 11=(1011)_{2}，有奇数个 1，所以 12 在 B 组中。
证明从略。
————
【注3】以上种种，其实也是「等幂和问题」的一个应用场景。
可以参见回答：非常神奇的数学结论有哪些？ - 曾加的回答
————
【注4】以上所提供的，是只知道排名，不知道各个名次对应权重时的一种选取方法，如果你知道更多的信息，如：每个人的确切权重，那本问题就转化为「背包问题」了，并不在本问题的讨论内，可移步：求一个算法，把一组数据切成两组数据，使两组数据和之差的绝对值最小？ - 数据结构
**********
（本文可以转发，如需转载，请私信作者。）
