加倍交換數字遊戲（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.