加倍交换数字游戏（IBM Ponder This July 2022）

IBM 的 Ponder This 项目每个月会发出一个谜题，这个月的题目是 加倍交换数字游戏 。

1、 问题原题

假设有 N 个数字， $a_1, a_2, \cdots, a_n$ $a_1, a_2, \cdots, a_n$ ，递增排列，每次操作可以选择两个数 $a_i$ $a_i$ , $a_j$ $a_j$ ，将前者加倍，后者扣减相应数值，即变成 $2a_i$ $2a_i$ 和 $a_j-a_i$ $a_j-a_i$ ，操作后将数字重新按照增序排列。

比如初始序列是 $(3, 4, 8)$ $(3, 4, 8)$ 时，如果我们对前两个数做操作，将得到 $(6,1,8)$ $(6,1,8)$ ，排序后为 $(1,6,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$ $a_1, a_2, \cdots, a_n$ 能经过若干步操作，将所有数值集中到一个数上，当且仅当初始序列每个数都是 $p$ $p$ 的倍数，其中 $p$ $p$ 是 $S=\sum a_i$ $S=\sum a_i$ 的最大 奇 因数。

2.1、 充分性

若初始序列每个数都是 $p$ $p$ 的倍数，其中 $p$ $p$ 是 $S=\sum a_i$ $S=\sum a_i$ 的最大奇因数，很显然可以假设 $p=1$ $p=1$ ，即所有数字之和是 2 的幂次。

由于所有数字之后为偶数，那么我们必然会有偶数个奇数存在，那么对这些奇数两两做加倍交换操作，所有序列都成为偶数了。这样将序列所有数都除以 1 ，继续后面的操作，若干步之后，必然归约到所有数字之和是 1 的情况，此时序列前面的数字都被清零，只留下最后一个 1。

2.2、 必要性

我们假设 $q$ $q$ 是所有数字的最大奇数公约数，然后可以看到，在做加倍交换操作时，这个最大奇数公约数是保持不变的。如果最后所有数都集中到一个数时，此时所有书的最大奇数公约数为 $p$ $p$ ，所以必然 $p=q$ $p=q$ ，即初始序列每个数就都是 $p$ $p$ 的倍数。

2.3、 第二问的解答

根据上面的充分性，第二问就能简单了，只需要保证序列所有数字之和为 2 的幂次即可。我们只需要给初始序列的最后一个数加上 29910203 ，这样序列所有数字之和是 $2^{26}$ $2^{26}$ ：

(855661, 1395050, 1402703, 1575981, 2956165, 4346904, 5516627, 5693538, 6096226, 37270009)

2.4、 如何增加尽量少的数

根据充分必要性，可以枚举所有数之和 $S=2^kp$ $S=2^kp$ ，然后向上调整所有数到 $p$ $p$ 的倍数，调整后的数字之和不大于 $S$ $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=1$ $q=1$ ，一个操作直接解决。如果 $q>1$ $q>1$ ，我们同样可以归约解决：

• 如果 $q$ $q$ 为偶数，对 $(p,t)$ $(p,t)$ 做加倍交换，得到 $(2p,2p\times \frac{q}2,t-p)$ $(2p,2p\times \frac{q}2,t-p)$ 。
• 如果 $q$ $q$ 为奇数，对 $(p,pq)$ $(p,pq)$ 做加倍交换，得到 $(2p,2p\times\frac{q-1}2,t)$ $(2p,2p\times\frac{q-1}2,t)$ 。

通过若干次归约，必然会让 $q=0$ $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.