猜数谜题

有A,B两个理性的学生,一天他们的老师从2-99中随机选取两个数,他把这两数之和M告诉A,把这两数之积S告诉B。然后
A说:虽然我不知道这两个数是什么,但我知道你一定不知道
B说:我开始不知道,但是现在知道了
A说:我也知道了
问这两个数是什么?

解答:
首先得到M的区间为[4,198],由A说的第一句话可知,当M满足以下条件之一时应被过滤掉

(1)M能唯一的分解成两个2-99范围内的数之和。

(2)存在两个2-99范围内的数其和等于M,且这两个数之积只能唯一的分解成两个2-99范围内的数之积。

对于条件2,它的充分条件由如下之一得到

(3)M能分解成两个2-97范围内的素数之和。

(4)M能分解成1个53-97范围内的素数与1个2-99范围内的数之和。

首先考察[4,198]的偶数,根据哥德巴赫猜想任一大于2的偶数都可写成两个素数之和,部分偶数满足条件3,故过滤相应的偶数后。
对于174 182 184 188 190 192 196 198不能写成两个2-99范围内的素数之和,需依次验证

198=99+99 满足条件1过滤
196=97+99 满足条件4过滤
192=97+95 满足条件4过滤
190=97+93 满足条件4过滤
188=97+91 满足条件4过滤
184=97+87 满足条件4过滤
182=97+85 满足条件4过滤
174=97+77 满足条件4过滤

所以[4,198]的偶数全部过滤掉,然后考察[4,198]的奇数。若M能分解成2与2-99范围内的奇质数之和,那么满足条件3应过滤掉
即5 7 9 13 15 19 21 25 31 33 39 43 45 49 55 61 63 69 73 75 81 85 91 99

197=99+98 满足条件1过滤

对于[100,196]的任意奇数总能分解为97+K,其中K在2-99范围内,满足条件4过滤。

还剩下的候选数依次为11 17 23 27 29 35 37 41 47 51 53 57 59 65 67 71 77 79 83 87 89 93 95 97依次验证
97=89+8 满足条件4过滤
95=89+6 满足条件4过滤
93=89+4 满足条件4过滤
89=83+6 满足条件4过滤
87=83+4 满足条件4过滤
83=79+4 满足条件4过滤
79=73+6 满足条件4过滤
77=73+4 满足条件4过滤
71=67+4 满足条件4过滤
67=61+6 满足条件4过滤
65=61+4 满足条件4过滤
59=53+6 满足条件4过滤
57=53+4 满足条件4过滤
最后剩下的候选数依次为11 17 23 27 29 35 37 41 47 51 53 记为T

由B说的话可知,S应满足如下条件
(5)分解成的全部积组合中——两个2-99范围内的数之积,只能有1个积组合其和在T中。
对于T中的特定候选数的某个和组合——分解成两个2-99范围内的数之和,其积不满足条件5的和组合过滤,满足的留下。
故T中的某个候选数没有一个满足条件5的和组合,应把该候选数过滤。
另一方面若候选数的某个和组合是1个2次幂与1个素数,那么该和组合的积是满足条件5的。
候选数的某个和组合是1个大于等于53一半的素数与1个偶数,那么该和组合的积也是满足条件5的。

由A说的第二句话可知,如果某个候选数存在2个及以上的满足条件5的和组合,也应把该候选数过滤。不然对于A来说并不确认
哪一个和组合的积是S。只有某个候选数存在唯一一个满足条件5的和组合,A才能在最后确认。
11存在2个满足条件5的和组合(4,7) (8,3) 过滤
23存在2个满足条件5的和组合(4,19) (16,7) 过滤
27存在2个满足条件5的和组合(4,23) (8,19) 过滤
35存在2个满足条件5的和组合(4,31) (16,19) 过滤
37存在2个满足条件5的和组合(8,29) (32,5) 过滤
47存在2个满足条件5的和组合(4,43) (16,31) 过滤
51存在2个满足条件5的和组合(4,47) (8,43) 过滤
41存在2个满足条件5的和组合(4,37) (29,12) 过滤
53存在2个满足条件5的和组合(16,37) (29,24) 过滤
29存在2个满足条件5的和组合(16,13) (2,27) ——这种组合是单独分析的 过滤

对于最后一个候选数分析如下
17=(2,15)(3,14)(4,13)(5,12)(6,11)(7,10)(8,9)
2*15=30=3*10=5*6,M=11,17无法过滤
3*14=42=2*21=6*7,M=23,17无法过滤
4*13=52=2*26,过滤
5*12=60=2*30=3*20=4*15=6*10,M=17,23无法过滤
6*11=66=2*33=3*22,M=35,17无法过滤
7*10=70=2*35=5*14,M=37,17无法过滤
8*9=72=2*36=3*24=4*18=6*12,M=27,17无法过滤
所以这两个数分别是4与13

原文地址:https://www.cnblogs.com/nearWind/p/15544912.html