花了一天,想明白一道题。
孙膑,庞涓都是鬼谷子的徒弟;一天鬼出了这道题目:他从2到99中选出两个不同的整数,把积告诉孙,把和告诉庞。
庞说:我虽然不能确定这两个数是什么,但是我肯定你也不知道这两个数是什么。
孙说:我本来的确不知道,但是听你这么一说,我现在能够确定这两个数字了。
庞说:既然你这么说,我现在也知道这两个数字是什么了。
问这两个数字是什么?为什么?
水木的IQDoor有这个题的解法,但我觉得他的分析有问题。"我肯定你也不知道这两个数是什么"这句话能说明"x+y一定不能表示成2个质数之和"?我觉得不对,严谨的说应该是x+y一定不能表示成2个2~99之间的质数之和。
因为庞知道的数字x+y也许可以分解成两个质数之和(这就不能用Goldbach Conjecture了),但这两个质数有一个不在2~99的范围,而符合范围的分解中没有质数组合,庞就可以确定孙不知道答案。
想了很久还是不知道怎么手算,最后写了个程序。
用isSumOfPrime(x)==true表示x可以表示成2个2~99之间的质数之和
所以分析第一句话
"我不能确定这两个数是什么",排除2+3,2+4,97+99,98+99
"但是我肯定你也不知道这两个数是什么",isSumOfPrime(x+y)==false。
站在孙的角度考虑,他的数字x×y有很多因式分解的方式,他通过庞的话排除掉了不可能的情况,得到最终的结果。那什么情况不可能?
如果分解为a×b,那么庞手中的数字是a+b,则需要有isSumOfPrime(a+b)==false,如果isSumOfPrime(a+b)==true,则可以排除a×b的情况
孙通过庞的第一句话知道了结果,说明在所有a×b的分解中,只有一组isSumOfPrime(a+b)==false
把满足这种条件的num=a×b,表示为onlyOneFactorization(num)==true
分析第三句话,站在庞的角度考虑,他得到的数字x+y表示成2个数字的和有很多种方式。在所有的x+y=a+b的分解中,那种分解方式是对的呢?
如果分解为a+b,那么孙的数字应该是a×b,那么应该有onlyOneFactorization(a×b)==true,如果onlyOneFactorization(a×b)==false,则可以排除分解为a+b的情况
然后既然庞说他知道结果了,那么说明根据上面的猜测,他排除了足够多的分解情况,最终只剩下一组分解的方式。
把满足这种条件的num=a+b,表示为onlyOneDivision(num)==true
用庞可能拿到的数字着手进行逐个测试,
RANGE=100
isSumOfPrime=[]
prime=[]
failSet=set([])
succeedSet=set([])
def primes(n):
if n==2: return [2]
elif n<2: return []
s=range(3,n+1,2)
mroot = n ** 0.5
half=(n+1)/2-1
i=0
m=3
while m <= mroot:
if s[i]:
j=(m*m-3)/2
s[j]=0
while j<half:
s[j]=0
j+=m
i=i+1
m=2*i+3
return [2]+[x for x in s if x]
def onlyOneFactorization(num):
#对于测试过的num,放入成功集或失败集,避免多次测试
if num in failSet:
return False
if num in succeedSet:
return True
findOne=False
finda=0
findb=0
for i in range(2,int(num**0.5+1)):
if num%i==0:
a=i
b=num/i
if b < RANGE and a<b and not isSumOfPrime[a+b]:
if findOne==False:
findOne=True
finda=a
findb=b
else:
failSet.add(num)
return False #找到不止一种a×b分解方法
if findOne :
succeedSet.add(num)
return findOne
def onlyOneDivision(num):
findOne=False
finda=0
findb=0
for i in range(2,int(num/2+1)):
a=i
b=num-i
if b < RANGE and a<b and onlyOneFactorization(a*b):
if findOne==False:
findOne=True
finda=a
findb=b
else:
return False #找到不止一种a+b分解方法
if findOne:
print "x+y= ",num," x*y= ",finda*findb," x= ",finda," y= ",findb
return findOne
if __name__ == '__main__':
#用数组来保存isSumOfPrime,查找快捷
prime=primes(RANGE)
isSumOfPrime=[False for i in range(RANGE*2)]
for i in range(0,len(prime)):
for j in range(i+1,len(prime)):
isSumOfPrime[prime[i]+prime[j]]=True
#排除5,6,197,198四种情况
for i in range(7,2×RANGE-4):
if isSumOfPrime[i]: #是2个质数之和,跳过
continue
onlyOneDivision(i)
最终结果只有一组,x+y= 17 x*y= 52 x= 4 y= 13
Last modified on 2007-10-16