Sum and Product Puzzle——像程序员一样思考
问题引入
翻译一下。
我们有两个整数。两整数均大于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)\)这一种分解方式。
整理一下第一句话得到的信息:
- 两个数不能同时为质数。
- 两个数的乘积不能为质数的三次方。
- 两个数中不能有大于50的质数。
显然,提前建好质数表可以稍微降低一点时间复杂度。这里我们利用之前提到过的埃氏筛法来建立质数表,代码如下。
1 | # build prime table |
根据第一句话得到的信息,可以写出以下的代码来判断两个数是否满足条件。
1 | def assertion1(x, y): |
第二句话
A说自己知道B不知道这两个数是什么,也就是说,从两个数的和就可以判断出这两个数:
- 不都是质数
- 乘积不是质数的三次方
- 没有大于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不知道这两个数是什么”相矛盾了。
综上,我们又有以下条件:
- 两数之和是奇数,且\(s-2\)不为质数
- \(s<55\)
可以写出以下代码判断。
1 | def assertion2(x, y): |
第三句话
听到A说的话之后,B就知道这两个数是什么了。这句话能带给我们什么信息呢?说明在\(p\)的所有分解情况中,满足之前所有条件的,只有一种。还需要往下进行数学上的分析吗?笔者起初确实有进行这种尝试,但是最后仍有几个个例需要进行手动排查,非常不优雅。
在此,我们可以转换一下思路,利用好我们任劳任怨的计算机。根据在\(p\)的所有分解情况中,满足之前所有条件的,只有一种这句话,直接写代码就行了。首先我们要获得\(p\)的所有分解情况,根据基本的乘除法知识,可以写出以下函数。
1 | from math import sqrt |
接着遍历这些数对,判断满足前两句话的数对是否只有一个。代码如下:
1 | def assertion3(x, y): |
第四句话
与第三句话非常类似,我们得到的信息也就是在\(s\)的所有分解情况中,满足之前所有条件的,只有一种。相同地,先写出分解\(s\)的程序。
1 | def sumDecomp(s): |
接着遍历这些数对,判断满足前三句话条件的数对只有一个。代码如下:
1 | def assertion4(x, y): |
打印结果
1 | ans = [] |
得到结果:
1 | So the values of these two numbers are 4 and 13. |
总结
需要人工筛除个例的方法不是好方法,在理论上遇到瓶颈的时候,工程上的解决方法也许非常简单。挺有意思的一个puzzle。