IBM 的 Ponder This 项目每个月会发出一个谜题，这个月的题目是加倍交换数字游戏。
1、问题原题
假设有 N 个数字，$a_1, a_2, \cdots, a_n$，递增排列，每次操作可以选择两个数$a_i$, $a_j$，将前者加倍，后者扣减相应数值，即变成$2a_i$和$a_j-a_i$，操作后将数字重新按照增序排列。
比如初始序列是$(3, 4, 8)$时，如果我们对前两个数做操作，将得到$(6,1,8)$，排序后为$(1,6,8)$。
比如下面一系列操作可以清零第一个数：
现在给定初始序列：
(855661, 1395050, 1402703, 1575981, 2956165, 4346904, 5516627, 5693538, 6096226, 7359806)
问题：
- 请用最多 20 步加倍交换操作清零至少一个数。
- 调整序列的一些值（只能增加不能减少），总调整值不能超过 30000000 ，使得可以经过一系列操作，将所有数值集中到一起，即最终序列的前 9 个值都是 0。
2、第二问
这个题目蛮有意思的。其实第二问要比第一问更简单一点。我们很容易证明下面命题：
一个序列$a_1, a_2, \cdots, a_n$能经过若干步操作，将所有数值集中到一个数上，当且仅当初始序列每个数都是$p$的倍数，其中$p$是$S=\sum a_i$的最大奇因数。
2.1、充分性
若初始序列每个数都是$p$的倍数，其中$p$是$S=\sum a_i$的最大奇因数，很显然可以假设$p=1$，即所有数字之和是 2 的幂次。
由于所有数字之后为偶数，那么我们必然会有偶数个奇数存在，那么对这些奇数两两做加倍交换操作，所有序列都成为偶数了。这样将序列所有数都除以 2 ，继续后面的操作，若干步之后，必然归约到所有数字之和是 1 的情况，此时序列前面的数字都被清零，只留下最后一个 1。
2.2、必要性
我们假设$q$是所有数字的最大奇数公约数，然后可以看到，在做加倍交换操作时，这个最大奇数公约数是保持不变的。如果最后所有数都集中到一个数时，此时所有书的最大奇数公约数为$p$，所以必然$p=q$，即初始序列每个数就都是$p$的倍数。
2.3、第二问的解答
根据上面的充分性，第二问就能简单了，只需要保证序列所有数字之和为 2 的幂次即可。我们只需要给初始序列的最后一个数加上 29910203 ，这样序列所有数字之和是$2^{26}$：
(855661, 1395050, 1402703, 1575981, 2956165, 4346904, 5516627, 5693538, 6096226, 37270009)
2.4、如何增加尽量少的数
根据充分必要性，可以枚举所有数之和$S=2^kp$，然后向上调整所有数到$p$的倍数，调整后的数字之和不大于$S$就是一种可选方案。
我们可以用 Python 做一个简单的搜索：
import math
a = [855661, 1395050, 1402703, 1575981, 2956165, 4346904, 5516627, 5693538, 6096226, 7359806]
def ceil_to(p):
return [ p * int(math.ceil(x / p)) for x in a ]
s = sum(a)
while True:
s += 1
p = s
while p % 2 == 0:
p = p // 2
c = ceil_to(p)
if sum(c) <= s:
c[-1] += s - sum(c)
print(c)
print(sum(c), sum(a), sum(c) - sum(a), p, sum(c) / p)
break
直接输出结果：
(855692, 1395079, 1402747, 1575987, 2956227, 4346904, 5516629, 5693561, 6096273, 7385349)
总调整幅度是 25787 ，远远低于上面的 29910203。这也是最佳答案。
3、第一问
第一问其实更难一些，至少我没想到确切的结论。
3.1、简单归约，倍数时可清空一个数
一个办法是先从 2 个数或三个数开始。只要我们发现序列里有三个数字满足下面特性，即一个数是另外一个数的倍数，且第三个数大很多，就能清空一个数：
如果$q>0$，我们可以归约解决：
- 如果$q$为偶数，对$(p,t)$做加倍交换，得到$(2p,2p\times \frac{q}2,t-p)$。
- 如果$q$为奇数，对$(p,pq)$做加倍交换，得到$(2p,2p\times\frac{q-1}2,t)$。
通过若干次归约，必然会让$q=0$，问题解决。
3.2、搜索操作使得出现倍数关系
接下来，我们就需要想想怎么才能操作，使得其中一个数为另外一个倍数。一个简单的办法是做一个随机搜索：
import sys
import random
for _ in range(1000000):
a = [855661, 1395050, 1402703, 1575981, 2956165, 4346904, 5516627, 5693538, 6096226, 7359806]
action = []
for __ in range(5):
i = random.randint(0, 9)
j = random.randint(0, 9)
if i == j:
continue
action.append([i, j])
if a[i] > a[j]: a[i], a[j] = a[j], a[i]
a[i], a[j] = 2 * a[i], a[j] - a[i]
if a[i] == 0:
print("0 found", action, a)
sys.exit(-1)
z = [x for x in a
if (x > a[i] and x % a[i] == 0) or (x > a[j] and x % a[j] == 0)]
if z:
print("div found", action, a, z, a[i], a[i])
sys.exit(-1)
结果发现直接对第二项和第三项做一次操作，就会出现一个数为另外一个数的倍数的情况：
(855661, 7653, 2790100, 1575981, 2956165, 4346904, 5516627, 5693538, 6096226, 7359806)
其中 4346904 是 7653 的倍数。
3.3、输出最终结果
将上面 2 步结合起来，输出最终的操作序列：
import math
arrays = [
[855661, 1395050, 1402703, 1575981, 2956165, 4346904, 5516627, 5693538, 6096226, 7359806],
[855661, 7653, 2790100, 1575981, 2956165, 4346904, 5516627, 5693538, 6096226, 7359806]
]
i = 1
j = 5
current = arrays[1]
while current[j] != 0:
new = list(current)
q = new[j] / new[i]
if q % 2 == 0:
new[9] -= new[i]
else:
new[j] -= new[i]
new[i] *= 2
arrays.append(new)
current = new
if new[j] == 0:
break
for idx, a in enumerate(arrays):
arrays[idx] = tuple(sorted(a))
print(arrays)
输出结果为：
((855661, 1395050, 1402703, 1575981, 2956165, 4346904, 5516627, 5693538, 6096226, 7359806), (7653, 855661, 1575981, 2790100, 2956165, 4346904, 5516627, 5693538, 6096226, 7359806), (15306, 855661, 1575981, 2790100, 2956165, 4346904, 5516627, 5693538, 6096226, 7352153), (30612, 855661, 1575981, 2790100, 2956165, 4346904, 5516627, 5693538, 6096226, 7336847), (61224, 855661, 1575981, 2790100, 2956165, 4346904, 5516627, 5693538, 6096226, 7306235), (122448, 855661, 1575981, 2790100, 2956165, 4285680, 5516627, 5693538, 6096226, 7306235), (244896, 855661, 1575981, 2790100, 2956165, 4163232, 5516627, 5693538, 6096226, 7306235), (489792, 855661, 1575981, 2790100, 2956165, 3918336, 5516627, 5693538, 6096226, 7306235), (855661, 979584, 1575981, 2790100, 2956165, 3918336, 5516627, 5693538, 6096226, 6816443), (855661, 1575981, 1959168, 2790100, 2956165, 3918336, 5516627, 5693538, 5836859, 6096226), (855661, 1575981, 2790100, 2956165, 3877691, 3918336, 3918336, 5516627, 5693538, 6096226), (0, 855661, 1575981, 2790100, 2956165, 3877691, 5516627, 5693538, 6096226, 7836672))
Q. E. D.
