在2到99之间选两个整数,告诉A两数之和,告诉B两数之积.
在2到99之间选两个整数,告诉A两数之和,告诉B两数之积.
A对B说:"虽然我不知道那两个数字,可是我能肯定你也不知道." B说:" 我原来确实不知道,可是你这么一说,现在我知道了." A于是说:" 既然你这么说,那我也知道了," 问是哪两个数字?
方便描述,改写如下:有2到99间两数a、b,A知道和s,B知道积m,然后是后面的对话,略
由A的第一句话就可以推得,两数和必然小于55
原因:如果s=a+b>=55,则s一定可以写为s=c+d,其中53这样,假如恰好a取c、b取d,那么m=c*d=a*b是一个可唯一乘积分解的数,也就是说B有可能只知道积就可以猜出来.
那么A说你一定猜不出就不准确了,所以s由A的第一句话还可以推得,这两个数不能写为两个素数的积.因此,根据哥德巴赫猜想“每一个大于或等于6的偶数都可表示成两个奇素数之和”,推得至少在2~200范围内,s不能是偶数
所以s的取值范围目前可以确定为[5,54]间的奇数,还可以进一步缩小范围.对奇素数p,3s是奇数,说明a,b必然一个为奇一个为偶(不妨a奇b偶).因此m=a*b为偶数
再分析B的第一句话.因为仅仅上面的条件就可以在知道m的条件下,而推出a,b.所以m=a*b的奇偶分解必然是唯一的.这说明奇数a必然是素数,b=2^n
再看A的的二句话.同样,仅仅上面的条件,就能确定s,说明s形如奇素数加一个2^n的偶数的分解也是唯一的.
根据上面的几条判据,对{11,17,23,27,29,35,37,41,47,51,53}进行筛选,同时注意s的a+b分解唯一性,可以很快得到结果
例如:11=4+7=8+3,不唯一
23=16+7=4+19,不唯一
.
最终得到s=17,a=13,b=4,m=52