加倍交换数字游戏(IBM Ponder This July 2022)

作者: , 共 5081 字 , 共阅读 0

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)$

比如下面一系列操作可以清零第一个数:

$$[(3, 4, 8), (1, 6,8),(2,6,7),(4,4,7),(0,7,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 的幂次。

由于所有数字之后为偶数,那么我们必然会有偶数个奇数存在,那么对这些奇数两两做加倍交换操作,所有序列都成为偶数了。这样将序列所有数都除以 1 ,继续后面的操作,若干步之后,必然归约到所有数字之和是 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 个数或三个数开始。只要我们发现序列里有三个数字满足下面特性,即一个数是另外一个数的倍数,且第三个数大很多,就能清空一个数:

$$(p, p\times q, t), \text{ s.t. } t > pq-p$$

如果$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.

类似文章:
数学 » Ponder this, 几何
今年 IBM 七月份的 Ponder This 问题(原题在这里,英文):
相似度: 0.080
前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至原问题
相似度: 0.080
注:此游戏很有名,有同学问我其算法,我在网上找了一下,居然没多少中文资料,这里按照以前看过的一份答案回忆整理贴出。
数学 » 数学游戏, 概率
蚁迹寻踪及其他数学探索》提到一个游戏:
利用线性代数可以给某些问题很精妙的证明,Matrix67 就给出了一个这样的例子,这也让我想起以前看见的另外一个例子,分享如下:
数学 » 数学游戏, 概率
600 个人站一排,每次随机杀掉一个奇数位的人,几号最安全?
春节到了,又是了抢红包的时节。不过我对于这背后的数学和算法更感兴趣。
相似度: 0.057
编程 » Python
Python 在搜索模块时,依次搜索sys.path里的位置,直到找到模块为止。下面命令可以查看当前的搜索路径:
相似度: 0.055
Alice 和 Bob 两人玩一种硬币游戏。游戏在一个$ 2\times2$ 的棋盘上进行,棋盘上每个格子上都有一枚硬币。在每一回合, Alice 可以决定选择翻转某两枚或者一枚硬币,接着 Bob 可以选择将棋盘旋转 90 , 180 或者 270 度,也可以什么都不做。
如果一个日期(或者时间),如果用字符串,比如"2010-10-04"的形式,各个系统都没有什么区别。在某些时候,将日期用数字表示,将大大增加对日期查找、比较的效率。而如果用数字来表示日期,在不同的系统之间差别就大了。
这两天斯里兰卡国家破产话题很热,我最关心的是咱们到底会亏多少钱。好奇查到一个网址 https://publicfinance.lk/en/topics-list/debt,上面提供了一些有意思的数据。
碎碎念 » IMO, 奥数
中国队在2022 年国际数学奥林匹克比赛中,六名队员都获得满分,总成绩 252。更厉害的是,这个总成绩比第二名的韩国队多了整整 44 分,也就是说中国队只用五个人,仍是团体第一名。