能否把\(1\)到\(16\)这十六个整数分成两个各含\(8\)个数的集合，使得两个集合的元素之和相等、元素平方之和相等、元素立方之和也相等？
能。 一组解是
\[ A=\{1,4,6,7,10,11,13,16\},\qquad B=\{2,3,5,8,9,12,14,15\}.\]
\(1\)到\(16\)的总和、总平方和、总立方和分别是
\[ \sum_{n=1}^{16}n=136,\qquad \sum_{n=1}^{16}n^2=1496,\qquad \sum_{n=1}^{16}n^3=136^2=18496,\]
所以两个集合若三样都要相等，公共值只能取它们的一半，即\(68\)、\(748\)、\(9248\)。直接对上面的\(A,B\)求和：
\[ \sum_{a\in A}a=\sum_{b\in B}b=68,\qquad \sum_{a\in A}a^2=\sum_{b\in B}b^2=748,\qquad \sum_{a\in A}a^3=\sum_{b\in B}b^3=9248.\]
三样全部对上，且两集合各含\(8\)个数、并起来恰是\(1\)到\(16\)，所以这组解有效。
不过“凑出一组解”并不是故事的全部：\(A\)与\(B\)其实来自一个整齐的造法。下面先说造法，再说它为什么必然成功。
用「甲 / 乙」表示分出的两边（甲就是前面的 \(A\)，乙就是 \(B\)），数字连写表示同一组，例如「甲 14 / 乙 23」就是 甲\(=\{1,4\}\)、乙\(=\{2,3\}\)。
做法只有两步，反复用：先把已有的分法整体加上一个数，“照搬”到新数上；再把两边的名字对调。
先分 1、2。 甲 \(=1\)，乙 \(=2\)。
翻倍到 1、2、3、4。 把「甲 1 / 乙 2」整体 \(+2\) 搬上去，得模板「甲 3 / 乙 4」；再对调（3 和 4 换边）：
\[ \text{甲}=14,\qquad \text{乙}=23.\]
（两边各 2 个数，和都是 \(5\)。）
翻倍到 1..8。 把「甲 14 / 乙 23」整体 \(+4\) 搬上去，得模板「甲 58 / 乙 67」；再把两边对调（注意：换的是这两份的“归属”，所以 58 改归乙、67 改归甲）：
\[ \text{甲}=14+67=1467,\qquad \text{乙}=23+58=2358,\]
即 甲\(=\{1,4,6,7\}\)、乙\(=\{2,3,5,8\}\)。
翻倍到 1..16。 把「甲 1467 / 乙 2358」整体 \(+8\) 搬上去：\(1467\to 9,12,14,15\)，\(2358\to 10,11,13,16\)；再把两边对调：
\[ \text{甲}=\{1,4,6,7\}+\{10,11,13,16\},\qquad \text{乙}=\{2,3,5,8\}+\{9,12,14,15\}.\]
即 甲\(=\{1,4,6,7,10,11,13,16\}\)、乙\(=\{2,3,5,8,9,12,14,15\}\)——正是题目要的答案。
“对调”到底管什么用？ 看「翻倍到 1..8」那一步最清楚。如果不对调，得到的是 甲 \(=1458\)、乙 \(=2367\)：两边个数相等、和也都是 \(18\)，可是平方和是 \(106\) 与 \(98\)，并不相等。对调之后变成 甲 \(=1467\)、乙 \(=2358\)，平方和成了 \(102\) 与 \(102\)，也相等了。一次对调，换来多一项相等。最后一步（到 \(1..16\)）再对调一次，就把“立方和相等”也补上了。
一句话：每翻倍一次，就对调一次；每对调一次，就多保证一项相等。（为什么次次都成立，下一节算给你看。）
把上面的“照搬 + 对调”写成式子：若 \(\{1,\dots,m\}\) 已分成 \(P,Q\)，则 \(\{1,\dots,2m\}\) 分成
\[ A=P\cup(Q+m),\qquad B=Q\cup(P+m),\qquad (X+m=\{x+m:x\in X\}),\]
其中“对调”就是 \(Q+m\) 归 \(A\)、\(P+m\) 归 \(B\)。下面算一算，为什么这个做法每做一次就多管住一项。
记两个集合在各次幂上的差
\[ \Delta_i=\sum_{p\in P}p^i-\sum_{q\in Q}q^i\qquad(i=0,1,2,\dots).\]
其中\(\Delta_0=0\)表示两边个数相等（因\(\sum p^0=|P|\)），\(\Delta_1=0\)表示和相等，\(\Delta_2=0\)表示平方和相等，\(\Delta_3=0\)表示立方和相等。
引理. 若对\(i=0,1,\dots,j\)都有\(\Delta_i=0\)，则新分划\(A=P\cup(Q+m)\)、\(B=Q\cup(P+m)\)对\(i=0,1,\dots,j+1\)都有
\[ \Delta_i':=\sum_{a\in A}a^i-\sum_{b\in B}b^i=0.\]
证明. 把新的差凑成旧差：
\[ \Delta_i'=\Big[\sum_{p\in P}p^i+\sum_{q\in Q}(q+m)^i\Big]-\Big[\sum_{q\in Q}q^i+\sum_{p\in P}(p+m)^i\Big].\]
第一、三项合起来正是\(\Delta_i\)；对第二、四项用二项式定理\((x+m)^i=\sum_{t=0}^{i}\binom{i}{t}x^{t}m^{i-t}\)再逐项相减，得
\[ \sum_{q\in Q}(q+m)^i-\sum_{p\in P}(p+m)^i=-\sum_{t=0}^{i}\binom{i}{t}m^{i-t}\Delta_t.\]
代入即
\[ \Delta_i'=\Delta_i-\sum_{t=0}^{i}\binom{i}{t}m^{i-t}\Delta_t=-\sum_{t=0}^{i-1}\binom{i}{t}m^{i-t}\Delta_t,\]
最后一步用掉了\(t=i\)的那一项恰好是\(\Delta_i\)。当\(i\le j\)时，右边只含\(\Delta_0,\dots,\Delta_{i-1}\)；当\(i=j+1\)时，右边只含\(\Delta_0,\dots,\Delta_j\)。由假设这些全为\(0\)，故\(\Delta_i'=0\)。∎
把引理串起来。 起点\(\{1\}\mid\varnothing\)尚不满足\(\Delta_0=0\)，但翻倍一次得到的\(\{1\}\mid\{2\}\)两边各\(1\)个数，已有\(\Delta_0=0\)。此后每翻倍一次都能把条件往前推一格：
- \(\{1\}\mid\{2\}\)（\(\Delta_0=0\)）\(\longrightarrow\) \(\{1,4\}\mid\{2,3\}\)（\(\Delta_0=\Delta_1=0\)）；
- 再翻倍 \(\longrightarrow\) \(\{1,4,6,7\}\mid\{2,3,5,8\}\)（\(\Delta_0=\Delta_1=\Delta_2=0\)）；
- 再翻倍 \(\longrightarrow\) \(\{1,4,6,7,10,11,13,16\}\mid\{2,3,5,8,9,12,14,15\}\)（\(\Delta_0=\Delta_1=\Delta_2=\Delta_3=0\)）。
末行的\(\Delta_0=\Delta_1=\Delta_2=\Delta_3=0\)，正是“个数、和、平方和、立方和全都相等”。
第二节那一串“翻倍 + 对调”，翻译成二进制后会变成一个特别简单的口令：把 \(n-1\) 写成二进制，数一数里面有几个 \(1\)——偶数个进甲，奇数个进乙（\(n=1,2,\dots,16\)）。比如 \(n=11\)：\(11-1=10=1010_2\)，有两个 \(1\)，偶数个，所以 \(11\) 进甲（确实 \(11\) 在甲里）。
为什么数 \(1\) 的个数就行？ 关键还是那句“前一半照旧、后一半翻面”。换一种读法就是：
把 \(n-1\) 的二进制从最高位读到最低位——见到 \(1\) 就把甲、乙翻一次面，见到 \(0\) 就不动。
道理是：\(n\) 在不在“后一半”，正由 \(n-1\) 的最高位是不是 \(1\) 决定；去掉这一位，剩下的还是“缩小一半”的同一个问题，接着看下一位即可。所以每遇到一个 \(1\) 就翻一次面，遇到几个 \(1\) 就翻几次。起点 \(n=1\)（\(n-1=0\)，一次都没翻，在甲）出发，翻偶数次仍在甲、翻奇数次到乙。拿 \(n=11\)（\(n-1=1010_2\)）走一遍：读 \(1\) 翻到乙 → 读 \(0\) 不动 → 读 \(1\) 翻回甲 → 读 \(0\) 不动，停在甲。
把 \(1\) 到 \(16\) 核对一遍：
| \(n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| \(n-1\) 的二进制 | 0 | 1 | 10 | 11 | 100 | 101 | 110 | 111 |
| 其中 \(1\) 的个数 | 0 | 1 | 1 | 2 | 1 | 2 | 2 | 3 |
| 进甲还是乙 | 甲 | 乙 | 乙 | 甲 | 乙 | 甲 | 甲 | 乙 |
| \(n\) | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|
| \(n-1\) 的二进制 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
| 其中 \(1\) 的个数 | 1 | 2 | 2 | 3 | 2 | 3 | 3 | 4 |
| 进甲还是乙 | 乙 | 甲 | 甲 | 乙 | 甲 | 乙 | 乙 | 甲 |
两表合起来正是 甲\(=\{1,4,6,7,10,11,13,16\}\)、乙\(=\{2,3,5,8,9,12,14,15\}\)。这个“甲 乙 乙 甲 乙 甲 甲 乙 ……”的花样有个名字，叫 Thue–Morse 序列。
题名“Truly Even Split”也是一语双关：既是“真正均分”，又是按二进制里“偶数个 \(1\)”来分。
- 上面这条“按二进制数位和的奇偶分划，可使各次幂之和相等”的一般结论，叫作 Prouhet–Thue–Morse 定理：对任意\(k\ge1\)，把\(1,2,\dots,2^k\)按\((n-1)\)的数位和奇偶分成两半，则两个集合在\(i=0,1,\dots,k-1\)各次幂上的总和都相等。本题是\(k=4\)（\(2^4=16\)），恰好管到\(i=3\)，也就是立方和为止；若再翻倍到\(32\)，连四次方的和也能配上。
- 用生成函数可以写得更短：\(\prod_{i=0}^{k-1}\bigl(1-x^{2^i}\bigr)=\sum_{m=0}^{2^k-1}(-1)^{s_2(m)}x^m\)，其中\(s_2(m)\)是\(m\)的二进制中\(1\)的个数。这个乘积在\(x=1\)处有\(k\)阶零点（每个因子都含一个因式\(1-x\)），于是对\(j<k\)有\(\sum_m(-1)^{s_2(m)}m^j=0\)，与上面的结论一致。
- 就本题这一组解而言，还有一个顺带的现象：每个\(n\)都与它的“配对”\(17-n\)落在同一边——\(1\)与\(16\)、\(4\)与\(13\)、\(6\)与\(11\)、\(7\)与\(10\)同在\(A\)，\(2\)与\(15\)、\(3\)与\(14\)、\(5\)与\(12\)、\(8\)与\(9\)同在\(B\)。于是\(A,B\)各自都是若干“和为\(17\)的对”的并集，和相等这条一眼可见；但平方和、立方和的相等，仍要靠上面的引理。
- 顺便指出一个常见误解：在“\(1\)到\(16\)”这个规模上，满足条件的分法其实只有一组（把\(A,B\)互换视为同一组）——穷举\(\binom{16}{8}=12870\)种分法即可核实。换句话说，题目问的这组分法之所以“特别”，不只是因为它恰好凑出了平方和、立方和，而是因为它唯一；而它又恰好来自上面那个统一、可递归、能推广到任意\(2^k\)的造法。