猜数字游戏

Wanakachi原创大约 5 分钟

使用超过700px宽度的web浏览器查看以获得最佳阅读体验。

从2-80之间（包括2和80）选两个自然数，将他们的积与和分别告诉甲乙两人，假设甲乙两人足够聪明。下面是两人的对话：

乙：甲不论如何也猜不到是哪两个数字。
甲：我知道了。
乙：我也知道了。

请问是哪两个数字？

逻辑分析

乍一看题面根本没有告诉读者有关这两个数字的任何信息，但是仔细思考就会发现：

从题面来看，甲拿到的是两数之积，乙拿到的是两数之和。由于甲乙两人足够聪明，如果甲拿到的是两素数之积，他一定能够猜到这两个数字。
第一句话展示了乙对甲猜不出这两个数字的绝对自信，这表示乙拿到的和不能被分解为两素数之和，否则甲完全有可能拿到这两个素数的积。
第二句话可以理解为：甲将拿到的数因式分解，并对得到的两个数求和，此时有且仅有一种情况，使得这两个数之和不能被分解为两素数之和，这样便可以唯一确定这两个数。
最后一句话也用同样方式理解：乙将拿到的数进行分解，对每种情况进行第3点中甲的计算，能够满足第3点的分解即为正确的分解情况。

问题详解

以下解答由博主本人构思并撰写，可能不规范，请见谅。

设这两个数分别为 $x$ 和 $y$ （ $x, y \in [2, 80]$ ），那么甲拿到的是 $xy$ ，记为 $M$ ；乙拿到的是 $x+y$ ，记为 $N$ 。

首先，对于 $N$ 的所有分解， $x$ 和 $y$ 不能同时为素数。记 $[2, 80]$ 里的素数集合为 $\mathbb{S}$ ，则

\tag{1} \forall (x, y) \in \{x+y=N \mid x, y \in [2, 80]\} \quad s.t. \quad (x, y) \notin \mathbb{S} \times \mathbb{S}

其次，对于满足 $(1)$ 式的 $(x^*, y^*)$ ，因为 $M$ 的限制，又有

\tag{2} \forall N \in \{x+y \mid xy=M \land x, y \in [2, 80] \land (x, y) \neq (x^*, y^*)\} \quad s.t. \quad \neg (1)

满足 $(2)$ 式的 $(x, y)$ 是确定值，即最终的答案。

因此解题步骤应为：枚举 $N \to$ 对满足 $(1)$ 式的 $(x, y)$ 计算 $M \to$ 判断是否满足 $(2)$ 式。

注

如果你是甲，你只需要挑选出和你拿到的 $M$ 相等的 $(x, y)$ 进行计算。

如果你是乙，你不需要枚举 $N$ 。

接下来采用启发式搜索：

$N=4$ ：只有1种分解 $(2, 2)$ ，排除。
$N=5$ ：只有1种分解 $(2, 3)$ ，排除。
$N=6$ ：有2种分解，其中 $(3, 3)$ 是两素数，故排除。
$N=7$ ：有2种分解，其中 $(2, 5)$ 是两素数，故排除。
$N=8$ ：有3种分解，其中 $(3, 5)$ 是两素数，故排除。
$N=9$ ：有3种分解，其中 $(2, 7)$ 是两素数，故排除。
$N=10$ ：有4种分解，其中 $(3, 7)$ 是两素数，故排除。
$N=11$ $N = 11$ ：有4种分解。
- $(2, 9)$ ： $M=18$ ， $N' \in \{11, 9\}$ ，只有 $11$ 不能被分解为两素数。满足要求。
- $(3, 8)$ ： $M=24$ ， $N' \in \{11, 10\}$ ，只有 $11$ 不能被分解为两素数。满足要求。
- 此时满足要求的 $(x, y)$ 已经多于一个，故排除。
$N=12$ ：有5种分解，其中 $(5, 7)$ 是两素数，故排除。
$N=13$ ：有5种分解，其中 $(2, 11)$ 是两素数，故排除。
$N=14$ ：有6种分解，其中 $(7, 7)$ 是两素数，故排除。
$N=15$ ：有6种分解，其中 $(2, 13)$ 是两素数，故排除。
$N=16$ ：有7种分解，其中 $(3, 13)$ 是两素数，故排除。
$N=17$ $N = 17$ ：有7种分解。
- $(2, 15)$ ： $M=30$ ， $N' \in \{17, 13, 11\}$ ， $17$ 和 $11$ 都不能被分解为两素数。排除。
- $(3, 14)$ ： $M=42$ ， $N' \in \{17, 23, 13\}$ ， $17$ 和 $23$ 都不能被分解为两素数。排除。
- $(4, 13)$ ： $M=52$ ， $N' \in \{17, 28\}$ ，只有 $17$ 不能被分解为两素数。满足要求。
- $(5, 12)$ ： $M=60$ ， $N' \in \{17, 32, 23, 19, 16\}$ ， $17$ 和 $23$ 都不能被分解为两素数。排除。
- $(6, 11)$ ： $M=66$ ， $N' \in \{17, 35, 25\}$ ， $17$ 和 $35$ 都不能被分解为两素数。排除。
- $(7, 10)$ ： $M=70$ ， $N' \in \{17, 37, 19\}$ ， $17$ 和 $37$ 都不能被分解为两素数。排除。
- $(8, 9)$ ： $M=72$ ， $N' \in \{17, 38, 27, 22\}$ ， $17$ 和 $27$ 都不能被分解为两素数。排除。
- 满足要求的结果有且仅有 $(4, 13)$ 。

因此结果为 $(4, 13)$ 。

程序验证

靠人力去挨个遍历肯定是行不通的，要想囊括 $[2, 80]$ 里的所有情况，就不得不进行程序验证。

于是按照上述的解题步骤，就有了以下的代码：

Python demo

# Made by Wanakachi
primelist = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
            73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157]

def divide_n(n):
    product = []
    for i in range(2, n//2+1):
        # can be divided by 2 prime numbers
        if i in primelist and n-i in primelist:
            return [], False
        # too big
        if n-i > 80:
            continue
        product.append(i*(n-i))
    return product, True

def divide_m(product):
    res = []
    for m in product:
        good = []
        # from product to sum
        for i in range(2, int(m**0.5)+1):
            # too big
            if i > 80 or m//i > 80:
                continue
            if m%i == 0:
                sum = i+m//i
                _, no_prime = divide_n(sum)
                if no_prime:
                    good.append([i, m//i])
        # only one sum cannot be divided by 2 prime numbers (where the product comes from)
        if len(good) == 1:
            res.append(good[0])
    # only one product satisfies the condition -> correct numbers
    if len(res) == 1:
        return res[0], True
    return [], False

def main():
    for i in range(4, 161):
        if i == 160:
            pass
        product, no_prime = divide_n(i)
        if not no_prime:
            continue
        res, good = divide_m(product)
        if good:
            print(res)

if __name__ == '__main__':
    main()

运行这份代码，控制台只会输出 $[4, 13]$ 这一对数字，看来这应该就是该范围内唯一的一组解了。