四季歌文学社区

标题: 灌水：一道只需加减乘除的题 [打印本页]

作者: 紫荆棘鸟 时间: 2020-10-1 03:55
标题: 灌水：一道只需加减乘除的题
除了加减乘除外，解答本题无需别的要求：不需知道开平方，不需知道对数或者三角函数之类，反正只需加减乘除就成了。不过此题虽然无需特别的背景，但需要有比较清晰的逻辑思维。这不是啥脑筋急转弯之类的题，而是纯粹的逻辑推理和计算。

相传此题是大数学家希尔伯特出给同行们消遣的，不知真假，可能系谣传。无论如何，出题人是很厉害的，因为他事先得有很强的直觉，能判断出原来这种题也是可解的。

题：某天，老师拿了一叠卡片，卡片一共 99 张，上面分别写有从 2 - 100 的各数，每张卡片一个数。老师随机抽取两张卡片，将两个数的和告诉甲同学，将两个数的乘积告诉乙同学。当然甲乙两人不能偷看对方的数，否则这题就是小学低年级学生的游戏了。

老师的目的是让同学们猜出这两个数是多少。于是有以下对话。

甲：我不知这两个数是什么，但是我肯定你也不知道。
乙：我本来是不知道这两个数的，你这么一说的话，那我就知道了。
甲：那我也知道了。

问题：这两个数是多少？

作者: 紫荆棘鸟 时间: 2021-6-9 20:18
解答比较长，看完需要一定的耐心。若是看明白了，还是有意思的。

先统一记号，假设这两个数为 (a，b)，其中
      2 <= a < b <= 100，s = a + b，p = a*b
这样甲得到的数字是 s （表示和 sum），乙得到的数字是 p （表示乘积 product）。(a，b) 总共有 C(99,2)=99*98/2 = 4851 种组合。

先来看第一句话。“ 甲：我不知道那两个数字是什么，但是我肯定你也不知道”，这句话意味什么？这意味着 s (甲手中的数字) 不能表达为两个素数的和，否则的话，例如如果 s = 8 = 3 + 5，乙手中的数 p 就可能是 15，而 15 只能分解成 3*5，于是乙能断言这两个数是 (3，5), 因此甲没法断言 “......但是我肯定你也不知道”.

因为 5 <= s <= 199，所以 s 总共有最多 195 种可能。我们将所有 s 构成的集合 S 分为两个子集 S1、S2，其中 S1 是 S 中所有能表示为两个素数之和的数的集合，S2 为剩余的数的集合。显然，从第一句对话，我们可以推断出，a+b=s 不能在 S1 中，只能在 S2 中。

鉴于小于 200 的素数大约有 200/ln200 = 38 个素数，而且所有的偶数都能表示为两个素数的和，而且（2 + 奇素数）都是奇数，所以作为大体上的估算，S1 中大约有 95 + 37 = 132 个数，S2 中大约有 63 个数，所以从第一句对话中，我们就能去掉大约 2/3 的(a，b) 组合，可能的候选者大约只有 1500 种组合。当然这是一种大体上的估算，和真正的推理计算没啥关系。

这里四海八荒猜测的组合（16，32）显然不满足第一句话的检测，因为甲的数是 48，因此乙的数就可能是 41*7=287。因此乙能够断言这两个数是（7，41），因为 287 只有这么一种素数分解。

再考察第二句话：“我本来是不知道这两个数的，你这么一说的话，那我就知道了”。
乙手里的数字是(a，b) 的乘积 p = a*b。假设将 p 分解成素数的乘积，p = p1^n1 * p2^n2 *...* pk^nk，其中 p1，...，pk 是素数，n1，...，nk >= 1，例如 90 = 2 * 3^2 * 5，72 = 2^3 * 3^2, 等等。这时 p 所对应的 (a，b) 组合，若不论 a、b < 100 这个约束，就有 n = (n1+1)*(n2+1)*...*(nk+1) / 2 -1 种可能的组合，例如对 90 而言，它可能的组合有 (1+1)(2+1)(1+1)/2 -1 = 5 种可能：90 = 2*45=3*30=5*18=6*15=9*10。
现在乙能根据甲的第一句话能推断出这两个数是什么，这意味着什么？这意味着总共 n 种 (a, b) 组合中，他能恰好排除 (n-1) 种可能。或者等价地说，p 对应的 n 个 a+b，恰好有 (n-1) 个属于集合 S1 中，有且只有 1 个属于 S2 中。
我们看个具体的实例，p = 90，它能分解成 5 种可能的 a*b：
p1)：90 = 2*45，2+45=47，属于 S2 (因为们47 不能表示为两个素数的和)；
p2)：90 = 3*30，3+30=33 = 2+31，属于 S1；
p3)：90 = 5*18，5+18=23，属于S2；
p4)：90 = 6*15，6+15=21=2+19，属于 S1；
p5)：90 = 9*10，9+10=19=2+17，属于 S1。
显然，这里 90 不满足这个检测，因为乙的这个数所有可能的分解中，除去那些越界的，必须恰好有且仅有一种分解，其和在集合S2中，这里我们却有两个组合在 S2 中。

我们再来看看四海八荒随后猜测的组合（2，9）。这个组合能满足第一句话的检测，因为 2+9=11 不能表达为两个素数的和。咱们具体看看能否满足第二句话的检测。这时乙手中的数是 18. 而 18 有如下两种分解：
p1）：18 = 2×9，2+9=11 属于 S2;
p2）：18 = 3×6，3+6=9  属于 S1.
因此（2，9）能通过第二句话的检测，因为它的乘积的所有可能的因式分解中，有且只有一种，其和在 S2 中。

这里眼尖一点的同学可能留意到了，90 有 5 钟分解，18 只有两种，显然分解的可能性越大，通过第二句话检测的可能性也就越小。

再看另一可能的组合（4，13）。因为 4+13=17 不能表达为两个素数的和，因此它能通过第一句话的检测。再考察第二句话。因为 p = 52 = 4*13 = 2*26，4 + 13 属于 S2，2+26 是偶数，属于 S1，所以它能满足第二步的检测。

我们接下来考虑第三句话。
第三句话是：“甲：那我也知道了”。注意甲手里的数字是 s = a+b，通常，s 能表达为多种 a + b，例如 8 = 2 + 6 = 3 + 5，两种；11 = 2+9=3+8=4+7=5+6，四种。一般，除去极端情形，s 不超过 100，s 能表示成 [ (s+1)/2] -2 种不同的 (a，b) 之和，这里 [x] 表示 x 的整数部分。若 s 超过 100，那么 s 就只能表示成总共 98 种表示 (考虑越界)。这句话的意思无非是说，甲看到手里的 s 后，对所有可能的总共 min ([ (s+1)/2] -2，[ (197-s)/2])  种可能的 (a、b)，乙所对应的总共 min ([ (s+1)/2] -2，[ (197-s)/2]) 种可能的乘积 p，恰好存在一种组合使得乙能判断出 (a，b)。亦即在这么多不同的 p 中间，有且只有一个组合，满足第一步和第二步的检测。

很明显，随着 s 的增加，min ([ (s+1)/2] -2，[ (197-s)/2]) 也在增加 (然后变小)，要满足第三个检测 (亦即存在唯一一个组合使得乙能判断) 也越来越困难。因此如果不依赖程序、只依赖手工去寻找这个组合，那么先应该去从小 s 中寻找才能保证更高的机率。

具体看 s = 17。从上面的例子我们可以看出，(4、13) 是满足前两步检测的。我们就以 s = 17 来看甲能否说“那我也知道了〃。我们有：
s = 17 = 2+15=3+14=4+13=5+12=6+11=7+10=8+9 总共 7 种组合。
情形1)：p=30=2*15=3*10=5*6，S1：3+10，S2：2+15，5+6；乙不能判断；
情形2)：p=42=2*21=3*14=6*7，S1：6+7；S2：2+21，3+14；乙不能判断；
情形3)：p=52=2*26=4*13，根据上面的讨论，乙能判断；
情形4)：p=60=2*30=3*20=4*15=5*12=6*10，其中3*20、5*12都属于S2，所以乙不能判断；
情形5)：p=66=2*33=3*22=6*11，其中2*33、6*11都属于S2，所以乙不能判断；
情形6)：p=70=2*35=5*14=7*10，其中2*35、7*10 都属于S2，所以乙不能判断；
情形7)：p=72=2*36=3*24=4*18=6*12=8*9，其中3*24、8*9 都属于S2，所以乙不能判断。

所以，对 s = 17，对所有可能的 7 种 a+b 组合，存在且唯一存在一种组合4+13，使得乙能判断，以及甲能判断。

所以，答案之一是 (4，13)。至于这答案是否唯一，靠手工计算，很很烦了。不过即使不唯一，满足条件的答案估计也就那么几个，而且数字不会很大。

我们再来看看组合（2，9），根据楼上的分析，（2，9）能通过前面两句话的检测。我们来看看它能否通过第三句话的检测。类似的，我们有：
s=11=2+9=3+8=4+7=5+6, 总共四种可能的组合。逐一考察：
情形1): p=18=2*9=3*6, 根据上面的讨论，乙能判断；
情形2): p=24=2*12=3*8=4*6, S1: 2+12, 4+6; S2: 3+8. 乙能判断；
情形3): 从略
情形4): 从略
为啥“从略”呢？因为无论是情形1 还是情形2，乙都能判断，因此甲就吃不准乙的数到底是哪种情形（说不定还可能是情形3&4），因此甲就没法断言“那我也知道了”。

欢迎光临四季歌文学社区 (http://www.shijiwenxue.top/)