一个有趣的问题——孙庞猜数

 关注
发布于: 4 小时前
题目：
孙膑，庞涓都是鬼谷子的徒弟。一天鬼谷子出了这道题目：
他从2到99中选出两个不同的整数a,b，把积a*b告诉孙，把和a+b告诉庞；
庞说：我虽然不能确定这两个数是什么，但是我肯定你也不知道这两个数是什么。
孙说：我本来的确不知道，但是听你这么一说，我现在能够确定这两个数字了。
庞说：既然你这么说，我现在也知道这两个数字是什么了。
请问这两个数字是什么？为什么？
﻿
解答过程：
第一个条件 
“庞说，我虽然不能确定这两个数是什么，但是我肯定你也不知道这两个数是什么。”
﻿
首先排除孙斌的积是两个素数a*b的可能性，因为这样孙斌就能猜出数字a和b。
﻿
另外，庞涓拿到a+b的结果在两个素数53~97之间的可能性也容易排除，因为容易分解为53+b的形式，而此时孙斌是可以确定a和b的。同理，大于97的数字则可以分解为97+b的形式，也排除。
﻿
即，我们第一步要做的，是排除4~53之间能够表示为两个素数和a+b的数字，最后得到庞涓可能拿到的结果，通过程序运行得知a+b的可能结果PossibleSum=[11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53]
﻿
例：庞涓拿到16，那么假设孙斌拿到55=5*11，可以猜出5和11，庞涓就不敢这么说了。
#判断a是否素数
def isPrime(a):
    if a<2:
        return False
    j = int(float(a)**0.5+1)
    for i in range(2,j):
        if a%i == 0:
            return False
    return True
PossibleSum = [i for i in range(4,54)]
for i in range(2,54):
    for j in range(i,54):
        if isPrime(i) and isPrime(j):
            if i+j in PossibleSum:
                PossibleSum.remove(i+j)
print(PossibleSum) #[11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53]
第二个条件 
“孙说：我本来的确不知道，但是听你这么一说，我现在能够确定这两个数字了”
﻿
这个条件的数学描述是，对于孙斌拿到的数字X，可以分解为乘子a和b（即X=a*b），使得a+b满足我们第一个条件里庞涓可能拿到的数字，即a+b∈PossibleSum，且可能性只有一种，这样孙斌才能确定。
﻿
例：孙斌拿到X=30，那么30可以分解为5*6和2*15，而5+6和2+15都在PossibleSum中，孙斌无法确定。
﻿
我会把所有的输出结果放到全文末，感兴趣的话可以看一下。
﻿
Sun = {}
for i in range(2,53):
    for j in range(i,53):
        if i+j in PossibleSum:
            if i*j not in Sun:
                Sun.setdefault(i*j, [(i,j)])
            else:
                Sun[i*j].append((i,j))
print("数字积, 孙斌可选的乘子组合")
for i in Sun:
    print(i, Sun[i])
第三个条件 
“庞说：既然你这么说，我现在也知道这两个数字是什么了”
﻿
这个条件的含义则是，对于孙斌在第二步中得到的所有a*b的组合（a，b），a+b的可能性只有一种，否则庞涓无法猜出a+b。
﻿
例：孙斌在第二步中可能的乘子组合有 (2, 9), (3, 8), (4, 7)，假设孙斌拿到18，而18只有一种分解形式a*b使得a+b∈PossibleSum，那么孙斌可以确定是2和9。同理，孙斌拿到24，则可以确定3和8。但是此时庞涓是无法分辨孙斌到底是拿了2、9还是3、8的，因为他拿到的11有多种组合方式，而任一种方式孙斌都可以猜到结果。
﻿
根据程序最后的输出结果，只有17=4+13满足条件，即为正解。
Pang = {}
for i in Sun:
    if len(Sun[i]) == 1:
        a,b,PossibleSum = Sun[i][0][0], Sun[i][0][1], Sun[i][0][0]+Sun[i][0][1]
        if PossibleSum not in Pang:
            Pang.setdefault(PossibleSum, [(a,b)])
        else:
            Pang[PossibleSum].append((a,b))
print("数字和, 庞涓可选的数字组合")
for i in Pang:
    print(i, Pang[i])
附：程序输出完整结果，感兴趣的话可以任意选几个数字在心里验证一下。
数字积, 孙斌可选的乘子组合
18 [(2, 9)]
30 [(2, 15), (5, 6)]
42 [(2, 21), (3, 14)]
50 [(2, 25)]
54 [(2, 27)]
66 [(2, 33), (6, 11)]
70 [(2, 35), (7, 10)]
78 [(2, 39), (3, 26)]
90 [(2, 45), (5, 18)]
98 [(2, 49)]
102 [(2, 51), (3, 34), (6, 17)]
24 [(3, 8)]
60 [(3, 20), (5, 12)]
72 [(3, 24), (8, 9)]
96 [(3, 32)]
114 [(3, 38)]
132 [(3, 44), (4, 33), (11, 12)]
144 [(3, 48)]
150 [(3, 50), (5, 30)]
28 [(4, 7)]
52 [(4, 13)]
76 [(4, 19)]
92 [(4, 23)]
100 [(4, 25)]
124 [(4, 31)]
148 [(4, 37)]
172 [(4, 43)]
188 [(4, 47)]
196 [(4, 49), (7, 28)]
110 [(5, 22)]
120 [(5, 24), (8, 15)]
160 [(5, 32)]
180 [(5, 36), (9, 20), (12, 15)]
210 [(5, 42), (6, 35), (7, 30), (14, 15)]
230 [(5, 46)]
240 [(5, 48)]
126 [(6, 21), (9, 14)]
138 [(6, 23)]
174 [(6, 29)]
186 [(6, 31)]
246 [(6, 41)]
270 [(6, 45), (10, 27)]
282 [(6, 47)]
112 [(7, 16)]
140 [(7, 20)]
154 [(7, 22)]
238 [(7, 34)]
280 [(7, 40)]
308 [(7, 44)]
322 [(7, 46), (14, 23)]
152 [(8, 19)]
168 [(8, 21)]
216 [(8, 27)]
232 [(8, 29)]
264 [(8, 33), (11, 24)]
312 [(8, 39), (13, 24)]
344 [(8, 43)]
360 [(8, 45)]
162 [(9, 18)]
234 [(9, 26)]
252 [(9, 28)]
288 [(9, 32)]
342 [(9, 38), (18, 19)]
378 [(9, 42), (14, 27)]
396 [(9, 44), (11, 36)]
130 [(10, 13)]
170 [(10, 17)]
190 [(10, 19)]
250 [(10, 25)]
310 [(10, 31)]
370 [(10, 37)]
410 [(10, 41)]
430 [(10, 43)]
176 [(11, 16)]
198 [(11, 18)]
286 [(11, 26), (13, 22)]
330 [(11, 30), (15, 22)]
440 [(11, 40)]
462 [(11, 42), (14, 33)]
204 [(12, 17)]
276 [(12, 23)]
300 [(12, 25), (15, 20)]
348 [(12, 29)]
420 [(12, 35), (20, 21)]
468 [(12, 39)]
492 [(12, 41)]
182 [(13, 14)]
208 [(13, 16)]
364 [(13, 28)]
442 [(13, 34)]
494 [(13, 38)]
520 [(13, 40)]
294 [(14, 21)]
518 [(14, 37)]
546 [(14, 39), (21, 26)]
390 [(15, 26)]
480 [(15, 32)]
540 [(15, 36), (20, 27)]
570 [(15, 38)]
304 [(16, 19)]
336 [(16, 21)]
400 [(16, 25)]
496 [(16, 31)]
560 [(16, 35)]
592 [(16, 37)]
306 [(17, 18)]
340 [(17, 20)]
408 [(17, 24)]
510 [(17, 30)]
578 [(17, 34)]
612 [(17, 36)]
414 [(18, 23)]
522 [(18, 29)]
594 [(18, 33)]
630 [(18, 35), (21, 30)]
418 [(19, 22)]
532 [(19, 28)]
608 [(19, 32)]
646 [(19, 34)]
620 [(20, 31)]
660 [(20, 33)]
672 [(21, 32)]
550 [(22, 25)]
638 [(22, 29)]
682 [(22, 31)]
552 [(23, 24)]
644 [(23, 28)]
690 [(23, 30)]
648 [(24, 27)]
696 [(24, 29)]
650 [(25, 26)]
700 [(25, 28)]
702 [(26, 27)]
数字和, 庞涓可选的数字组合
11 [(2, 9), (3, 8), (4, 7)]
27 [(2, 25), (4, 23), (5, 22), (7, 20), (8, 19), (9, 18), (10, 17), (11, 16), (13, 14)]
29 [(2, 27), (4, 25), (6, 23), (7, 22), (8, 21), (10, 19), (11, 18), (12, 17), (13, 16)]
51 [(2, 49), (3, 48), (4, 47), (5, 46), (7, 44), (8, 43), (10, 41), (11, 40), (12, 39), (13, 38), (14, 37), (16, 35), (17, 34), (18, 33), (19, 32), (20, 31), (22, 29), (23, 28), (24, 27), (25, 26)]
35 [(3, 32), (4, 31), (6, 29), (8, 27), (9, 26), (10, 25), (12, 23), (14, 21), (16, 19), (17, 18)]
41 [(3, 38), (4, 37), (7, 34), (9, 32), (10, 31), (12, 29), (13, 28), (15, 26), (16, 25), (17, 24), (18, 23), (19, 22)]
17 [(4, 13)]
23 [(4, 19), (7, 16), (10, 13)]
47 [(4, 43), (6, 41), (7, 40), (10, 37), (13, 34), (15, 32), (16, 31), (17, 30), (18, 29), (19, 28), (22, 25), (23, 24)]
37 [(5, 32), (6, 31), (8, 29), (9, 28), (16, 21), (17, 20)]
53 [(5, 48), (6, 47), (8, 45), (10, 43), (12, 41), (13, 40), (15, 38), (16, 37), (17, 36), (19, 34), (20, 33), (21, 32), (22, 31), (23, 30), (24, 29), (25, 28), (26, 27)]
﻿
﻿
发布于: 4 小时前阅读数: 15
原文链接:【http://xie.infoq.cn/article/1af615d1c9845f39998b726e0】。
小七

 关注
还未添加个人签名 2020.08.09 加入
还未添加个人简介
发布
暂无评论