鬼谷考徒

花了一天,想明白一道题。

孙膑,庞涓都是鬼谷子的徒弟;一天鬼出了这道题目:他从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

Comments