S先生与P先生谜题_在线百科全书查询
S先生与P先生谜题
S先生与P先生的谜题，是由美国斯坦福大学的麦卡锡提出的，事实上这是一个推理问题。在对题目定义的清楚明确下，为了得到结果进行了一系列的举例证明与排除，从而在思辨中得出问题的答案。这个谜题从另一侧面教会了我们思考问题的方法。
解题方法一(1.ｓ先生自己不知道ｘ，ｙ 2.ｓ先生知道ｐ先生不知道ｘ，ｙ 3.p先生听了s先生的话后，知道了ｘ，ｙ 4.ｓ先生也知道了ｘ，ｙ)
解题方法二(1、S：我确信你不知道，但我也不知道。 2、P: 听你说这句话，我就知道这两个数了。 3、S: 我也是，现在我也知道了。)
介绍
简介
S先生与P先生的谜题，是由美国斯坦福大学的麦卡锡提出的，事实上这是一个推理问题。在对题目定义的清楚明确下，为了得到结果进行了一系列的举例证明与排除，从而在思辨中得出问题的答案。
题面
美国斯坦福大学的麦卡锡提出的
设有两个自然数X、Y，2<=X<=Y<=99,S先生知道这两个数的和S，P先生知道这两个数的积P，他们二人进行了如下对话：
S：我确信你不知道这两个数是什么，但我也不知道。
P: 一听你说这句话，我就知道这两个数是什么了。
S: 我也是，现在我也知道了。
现在你能通过他们的会话推断出这两个数是什么吗？（当然，S和P先生都是非常聪明的）
题后结语
每一道题的解法都有它的独特处。若具有良好的解题思想，思辨意识，有始有终，持之以恒，定会得到自己的满意答案。
解题方法一
我把思路说一下吧
1.ｓ先生自己不知道ｘ，ｙ
说明和数ｓ不是4，5，197，198
否则x,y分别只能为2,2；2,3；98,99；99,99。均只有一种情况。即可确定x,y了。
2.ｓ先生知道ｐ先生不知道ｘ，ｙ
首先，什么样的数p先生可以知道呢？
如s=8
8=2*4 8=1*8 后者是不可能的( x,y>=2 )
又如 s=25
25=5*5 只有一种
这样p先生就能知道x,y
这说明ｓ分解后 ｓ＝M1+N1=M2+N2=.....
M1*N1 分解成 乘积 的形式有 两种或两种以上，
若 s=11
11＝2+9 2*9=18 18=2*9=3*6
11=3+8 3*8=24 24=2*12=3*8=4*6
11=4+7 4*7=28 28=2*14=4*7
这样s先生可以确定p先生不能知道ｘ，ｙ
所以s先生知道的 和数s 是如下的数
SA={ 11,17,23,27,29,35,37，41，47，51，53...}
SA也不可以是29，因为29=7+11+11，则x，y=88，11，
同样得到SA={11，17，23，27}
3.p先生听了s先生的话后，知道了ｘ，ｙ
我们可以想像p先生根据s先生的话，已经知道s先生知道的和数是集合SA中的数
若自己所知道的乘积p分解成m*n后 其中有一个（m+n）是集合SA中的数
则 m,n就是所求的数ｘ，ｙ
如 p=18
18=2*9 2+9=11
18=3*6 3+6=9
11属于SA
ｘ，ｙ就是 2 和 9
若p=72
72=2*36 2+36=38
72=3*24 3+24=27
......
72=8*9 8+9=17
其中27,17都属于SA
于是72被排除了
所以ｐ先生所知道的乘积是如下
pb={18,24,28,30，50,52,....}
所知道的ｘ，ｙ是乘积在pb中，且 乘积分解后的两数的和只有一个 在SA中的数对，记为
XY={(x1,y1),(x2,y2),.....}
4.ｓ先生也知道了ｘ，ｙ
可以知道，这时ｓ先生也知道ｐ先生知道的数的范围XY
如果ｓ分解后的两数s=m+n,(m,n)只与XY中的一个数对相同
这样，ｓ先生也就找到了ｘ，ｙ ，但是没有这样的数。
解题方法二
我看到过答案，这是根据我的理解写下的
1、S：我确信你不知道，但我也不知道。
为什么s先生这么确定？换句话说P先生得到怎样的组合就能立刻知道mn的值呢？
先看看哪些情况下ｐ先生能立刻得到答案
（１）mn不能同时为质数。
mn为质数，那么他们的乘积分解成两个因子乘积的可能性就唯一了，那么P先生就会立刻得知mn的值。
譬如34=1*34=2*17，因为nm是大于等于2的，那么1*34这样的组合是不可能的，那么mn就是2和17。
Mn不为质数，那么他们可能之中有1个质数，或者２个同为合数。
（２） 如果mn中有一个质数，那么那个质数不会大于50
如果mn有一个大于50，那么他们分解成两个因子乘积的可能性中，其他的分解方式都会有一个因子会超过100，然么分解方式必然会被P排除，那就只剩下一种方式，P也就立刻知道答案。
譬如318 = 6*53 = 3*106 = 2*159，因为mn小于等于99，那么后两种可能性肯定被排除。mn就肯定是6，53。
（３） 如果mn都是合数，那么都不会大于５０
理由同上。可就是Ｐ分解因子，只有一种情况下ｍｎ是小于１００的，其他情况ｍｎ必有一数大于等于１００。
其实mn的积也不会是8或者27，因为8 = 2*4 27=3*9，分解因子也就一种情况
Mn的值在以上情况下Ｐ先生可以立刻知道答案，那么也就是说Ｓ先生看到ｍｎ的和可以立刻推理出ｍｎ不可能存在上述的情况
（4）S不能分解成三个这样的质数之和：
如果S=29=7+11+11.那么X,y=11，88，或7，121 后面一种不符合。
又如果S=35=7+11+17，那么x，y=7，187或11，119或17，88 前面两种不符合。
（１）Ｓ肯定是奇数
Ｓ肯定是奇数，如果ｓ是偶数，那么mn有可能是质数。（原作者引用了哥德巴赫猜想：每一个大于2的偶数都是两个素数的和。虽然这个猜想没有证明，但是在１００范围以后可以实验证明这个猜想是正确的。如果有例外的话，这个猜想也就不会这么有名了。也就是说４－１００范围以内的偶数都可以用两个质数的和表示。）
（２）ｍｎ的和不能大于５4
这个推测的依据是建立在上面２、３之中的。因为Ｓ先生确信Ｐ先生不知道ｍｎ的值，所以２、３的情况是不会从ｍｎ的和中反应的。
（3）S-减去2的值不是质数
在质数中，2是一个特例，他是质数中唯一的偶数。既然mn不能同时为质数，那么s减去2的值也就不是质数了。
（4)S不等于29，35，37，41，47，51，53.
有上得S只能取11，17，23，27。
2、P: 听你说这句话，我就知道这两个数了。
P先生和我们一样，现在知道mn的和就只有上面的可能了。他只要把mn的积分解两个因子乘积，所有可能性中，有且只有一组的可能性中两个因子的和刚好是上面11个数中的一个，那么P先生就知道mn的值了。
假设P = 30 = 5*6 = 2*15，而5+6=11，2+15 =17，11和17都在上面11个数之中，那么P先生就无法判断mn到底是哪组数。所以P就不会等于30。
既然知道P先生的判断方法，现在就从11个数出发，一个个的推导。
3、S: 我也是，现在我也知道了。
S先生根据P先生的话知道了mn的积分解因子，只有一组的因子之和为11个数中间的一个。而S先生同时也立刻知道mn的值。我们可以推断，如果把mn之和拆成数个由一个奇数和一个偶数的组合，只有一个组合符合下面的条件：这个奇数和偶数的乘积符合第2条P先生的判断，也就是把这个积分解成两个因子乘积，所有分解情况中，有且只有一组的情况中两个因子的和刚好是上面11个数中的一个。这样S先生也就能知道mn的值了
我们只要把11个数拆成若干种奇偶组合，如果有2个或者2个以上的组合满足P先生判断条件，那么这个数就不是mn的和。：
（１）11 = 2+9=4+7=6+5=8+3
2*9 = 18 = 3*6，3+6=9不在10个数中，那么2*9符合。
4*7=28=2*14，前面说过mn是一奇一偶，2*14不考虑，4*7符合。
6*5=30=2*15，而6+5=11，2+15=17，两个数都在11个数中，那么P先生是无法判断，所以这个组合可以略过。
8*3 = 24 = 2*12=4*6，，那么2*12，4*6不用考虑，8*3符合
现在有3组数字符合，那么11就不是mnd的和了
从上面看，如果把11拆成2的次方和一个质数的组合，那么只有一种分解是一奇一偶，其他的情况都是2个偶数。(4,7) = (2^2,7),(3,8) = (3,2^3)，这样的组合分解就具有唯一性，就能满足我们的要求。11可以拆成2个这样的组合，11就可以排除了。
（2）23 = 2^2+19 = 2^4+7
27 = 2^2+23 = 2^3+19
上面是数可以拆成2组2的次方和一个质数，也就是有2组符合P先生的判断，故这些数可以排除，那就只剩下17，29了
（3）29 =16+13=2+27
2*27 = 54 =3*18=6*9，符合
16*13 是2^4和13，13是质数，肯定符合
29有2组符合，所以29排除。
（4）现在就只剩下17了。
17=4+13=6+11=7+10=8+9
4*13=52，6*11=66，7*10=70，8*9=72都只有一组符合。排除故无解。
