Sum and Product Puzzle——像程序员一样思考

Posted on Edited on Views:

问题引入

翻译一下。

我们有两个整数。两整数均大于1，并且它们的和小于100。

A只知道这两个数的和是多少，B只知道这两个数的乘积是多少。接着两人进行了如下对话：

B: 我不知道这两个数是多少。

A: 我知道你不知道这两个数是多少。

B: 现在我知道这两个数是多少了。

A: 如果你知道了，那我也知道了。

问题分析

假设这两个数是\(x\)和\(y\)。A知道\(x+y\)，我们记作\(s\)。B知道\(x\cdot y\)，我们记作\(p\)。

第一句话

B先开口，说自己不知道这两个数。什么意思呢，首先考虑一下，什么时候我们可以从乘积一眼看出两个因数。比如15，我们一看就知道是\(3\times 5\)，比如21，我们一看就是\(3\times 7\)。显然，如果一个数是两个质数的乘积，那么我们就可以从乘积推出来这两个数。

根据算数基本定理，每个合数可以分解为若干个质数的乘积。上面我们已经提到只能分为两个质数的情况。除此之外还有没有其他情况呢？假设\(p\)有三个质因数，分别是\(a, b\)和\(c\)。把\(p\)分为两个数的乘积，有以下三种方式。

\[ \begin{align*} p & = a(bc)\\ p & = b(ac)\\ p & = c(ab) \end{align*} \] 然而，当\(a = b = c\)时，这三种分解方式相同。即：如果\(p\)是质数的三次方，那么我们也能从乘积推出来这两个数。

别忘了，我们还有一个限制——两个数的和小于100， 这也就意味着两个数也都小于100。对于上面的例子，如果\(a, b\)和\(c\)中有一个数是大于50的，那么它也只能有一种分解方式。我们用一个具体的例子推一下这个结论。假设\(p = abc\)，\(a, b\)和\(c\)为\(p\)的三个质因数，且\(a > 50\)，那么\(ac\)和\(ab\)都会大于100，所以只有\(p = a(bc)\)这一种分解方式。

整理一下第一句话得到的信息：

  1. 两个数不能同时为质数。
  2. 两个数的乘积不能为质数的三次方。
  3. 两个数中不能有大于50的质数。

显然，提前建好质数表可以稍微降低一点时间复杂度。这里我们利用之前提到过的埃氏筛法来建立质数表，代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# build prime table
def buildPrimeTable(n):
    is_prime = [True for i in range(0, n+1)]
    if n<2:
        for i in range(len(is_prime)):
            is_prime[i] = False
        return is_prime
    is_prime[0] = is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            for j in range(i+i, n+1, i):
                is_prime[j] = False
    return is_prime

table = buildPrimeTable(100)

根据第一句话得到的信息，可以写出以下的代码来判断两个数是否满足条件。

1
2
3
4
5
6
7
8
9
10
def assertion1(x, y):
    if(x > 100 or y > 100):
        return False
    if(table[x] and table[y]):
        return False
    if((table[y] and x == y**2) or (table[x] and y == x**2)):
        return False
    if((table[x] and x >= 53) or (table[y] and y >= 53)):
        return False
    return True

第二句话

A说自己知道B不知道这两个数是什么，也就是说，从两个数的和就可以判断出这两个数：

  1. 不都是质数
  2. 乘积不是质数的三次方
  3. 没有大于50的质数

根据哥德巴赫猜想呢，所有大于2的偶数都可以写成两个质数的和。所以，我们就可以推出，这两个数的和一定不是偶数（即一定是奇数）。可能有人会觉得奇怪，为什么我们可以拿“猜想”来进行逻辑推理呢？事实上，我们讨论的数字范围之内，哥德巴赫猜想是可证的，即100以内的所有大于2的偶数都可以写成两个质数的和。所以，我们知道，这两个数的和一定是奇数。此外，考虑到2也是质数，而2和其他奇质数的和也是奇数，所以我们需要保证\(s-2\)不是质数。

好，现在看条件3，\(x\)和\(y\)要满足什么条件，才能使得，根据\(x+y\)，就能推出\(x\)和\(y\)其中没有大于50的质数呢？其实非常简单粗暴，只要\(x+y\)小于55就可以了。因为如果手上有\(s>=55\)，那么总能拆成\(53+(s-53)\)，也就导致了B可以直接从乘积得到两个因数，与A说的“我知道B不知道这两个数是什么”相矛盾了。

综上，我们又有以下条件：

  1. 两数之和是奇数，且\(s-2\)不为质数
  2. \(s<55\)

可以写出以下代码判断。

1
2
3
4
5
6
7
8
def assertion2(x, y):
    if (x+y)%2 == 0:
        return False
    if x+y >= 55:
        return False
    if table[x+y-2]:
        return False
    return True

第三句话

听到A说的话之后，B就知道这两个数是什么了。这句话能带给我们什么信息呢？说明在\(p\)的所有分解情况中，满足之前所有条件的，只有一种。还需要往下进行数学上的分析吗？笔者起初确实有进行这种尝试，但是最后仍有几个个例需要进行手动排查，非常不优雅。

在此，我们可以转换一下思路，利用好我们任劳任怨的计算机。根据在\(p\)的所有分解情况中，满足之前所有条件的，只有一种这句话，直接写代码就行了。首先我们要获得\(p\)的所有分解情况，根据基本的乘除法知识，可以写出以下函数。

1
2
3
4
5
6
7
8
from math import sqrt
def productDecomp(p):
    ans = []
    sq = int(sqrt(p))
    for i in range(2, sq+1):
        if p%i == 0:
            ans.append((i, int(p/i)))
    return ans

接着遍历这些数对，判断满足前两句话的数对是否只有一个。代码如下：

1
2
3
4
5
6
7
8
9
def assertion3(x, y):
    p_decomp = productDecomp(x*y)
    cnt = 0
    for pair in p_decomp:
        if assertion1(pair[0], pair[1]) and assertion2(pair[0], pair[1]):
            cnt += 1
        if cnt > 1:
            return False
    return True

第四句话

与第三句话非常类似，我们得到的信息也就是在\(s\)的所有分解情况中，满足之前所有条件的，只有一种。相同地，先写出分解\(s\)的程序。

1
2
3
4
5
def sumDecomp(s):
    ans = []
    for i in range(2, int(s/2)):
        ans.append((i, s-i))
    return ans

接着遍历这些数对，判断满足前三句话条件的数对只有一个。代码如下：

1
2
3
4
5
6
7
8
9
def assertion4(x, y):
    s_decomp = sumDecomp(x+y)
    cnt = 0
    for pair in s_decomp:
        if assertion1(pair[0], pair[1]) and assertion2(pair[0], pair[1]) and assertion3(pair[0], pair[1]):
            cnt += 1
        if cnt > 1:
            return False
    return True

打印结果

1
2
3
4
5
6
ans = []
for i in range(2, 101):
    for j in range(i, 101):
        if assertion1(i, j) and assertion2(i, j) and assertion3(i, j) and assertion4(i, j):
            ans.append((i, j))
print("So the values of these two numbers are %d and %d." % (ans[0][0], ans[0][1]))

得到结果：

1
So the values of these two numbers are 4 and 13.

总结

需要人工筛除个例的方法不是好方法，在理论上遇到瓶颈的时候，工程上的解决方法也许非常简单。挺有意思的一个puzzle。