作者: 张志强

, 发表于 2022-07-14

, 共 5069 字 , 共阅读 5 次

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

1、问题原题

假设有 N 个数字，a1,a2,⋯,an，递增排列，每次操作可以选择两个数ai, aj，将前者加倍，后者扣减相应数值，即变成2ai和aj−ai，操作后将数字重新按照增序排列。

比如初始序列是(3,4,8)时，如果我们对前两个数做操作，将得到(6,1,8)，排序后为(1,6,8)。

下面一系列操作可以清空第一个数：

现在给定初始序列：

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

• 请用最多 20 步清零至少一个数。
• 调整序列的一些值（只能增加不能减少），总调整值不能超过 30000000 ，使得可以经过一系列操作，将所有数值集中到一个，即最终序列的前 9 个值都是 0。

2、第二问

这个题目蛮有意思的。其实第二问要比第一问更简单一点。我们很容易证明下面命题：

一个序列a1,a2,⋯,an能经过若干步操作，将所有数值集中到一个数上，当且仅当初始序列每个数都是p的倍数，其中p是S=∑ai的最大奇因数。

2.1、充分性

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

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

2.2、必要性

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

2.3、第二问的解答

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

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

2.4、如何增加尽量少的数

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

• 如果q为偶数，对(p,t)做加倍交换，得到(2p,2p×q2,t−p)。
• 如果q为奇数，对(p,pq)做加倍交换，得到(2p,2p×q−12,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.