S先生和P先生谜题

这道题目来自美国斯坦福大学的麦卡锡教授—-S先生与P先生谜题。

题目:S先生与P先生谜题
设有两个自然数X、Y,2<=X<=Y<=99,S先生知道这两个数的和S,P先生知道这两个数的积P,他们二人进行了如下对话: S:我确信你不知道这两个数是什么,但我也不知道。
P: 一听你说这句话,我就知道这两个数是什么了。
S: 我也是,现在我也知道了。

现在你能通过他们的会话推断出这两个数是什么吗? (当然,S和P先生都是非常聪明的)

解答:
首先,S说: 我确信你不知道这两个数是什么,但我也不知道。
F1:
我们从S先生的这句话可以知道,S不可能拆分为两个素数的和
若不然,P只有唯一的分解,这样,P先生就有可能立即推测出这两个数,因此S先生没理由断定P先生不知道这两个数

F2:
这两个数的和必然是奇数(两数是一奇一偶), 因为歌德巴赫猜想对充分小偶数是成立的,每个小偶数可以分解为两个奇素数的和,这样,如果这两个数的和是偶数,它就有可能分解为两个奇素数,这与上面的结论矛盾了

F3:
S的任意分拆中美有大于50的素数
否则,设s=u+v,其中v为大于50的素数,那(u,v)导致的p'=uv除了有分解(u,v)没有其他分解,因为若有其他分解则比呈现(k1,k2v)形式, k1k2=u k2>=2 因而k2v>100不合题意
所以S也没理由断定P先生不知道这两个数

F4:
s<54
这是F2,F3的逻辑结果. 因为54为偶数,与F2不合,而大于54的数可以有分拆(53,v) 但53是大于50的素数,与F3不合

综合F1~F4得,S必须满足: S是大于3小于54的奇数,并且没有2个素数的拆分
满足条件D1(S) 的集合 A={11,17,23,27,29,35,37,41,47,51,53}
这也是P先生得到的结论

接着P先生说: 一听你说这句话,我就知道这两个数是什么了
P先生之所以立刻得到答案,说明
D2(P): p能导致满足D1(S)的s'的分拆(u,v)是唯一的

最后S先生说: 我也是,现在我也知道了
S从D2(P)中获取了信息,S知道这两个数因为
D3(P): s能导致满足D2(P)的p'的分拆(u,v)是唯一的

下面用D3(P)来一一考察集合A中的数:
首先考察11: 11的分拆有(3,8)(4,7) 分别导致p1'=28=2^2*7,p2'=24=2^3*3
但p1',p2'都满足D2(P),因为他们都只有唯一的分拆(2^2,7)(2^3,3)能导致满足D1(S)的s'
说明11有2个分拆能导致满足D2(P)的p' 不满足D3(P)

从上面分析还可以看出,一切形如2^K乘以素数的数按上面的分析,是不合题意的
因此S只可能是17,29,41,53之一

其实S<>29,因为29有2个分拆(13,16)(12,17)
而由前陈述,(13,16)导致的P'=2^4*13必满足D2(P).
(12,17)导致的P'=12*17=204 204的所有分解(3,68),(6,34),(12,17),(4,51),(2,102)
其中(6,34)(2,102)将导致偶数的s' (3,68),(4,51)导致的s'都不满足D1(S)
则204的分解中就(12,17)能导致满足D1(S)的s' 所以他满足D2(P)
于是29有2个分拆能导致满足D2(P)的p' 不满足D3(P)

类似可证明S<>41 S<>53
剩下17,而且容易验证,17满足D3(P),因此S=17
最后用D2(P)确定P=52
则M=4 N=13就是本谜题的解

发表评论

电子邮件地址不会被公开。 必填项已用*标注