页面

2011年6月19日星期日

不要让蛋白疼了

话说偶昨天在松鼠会上看到了个周末数学题:

从2到99里取出两个数; 私下告诉和先生两书之和,再私下告诉积先生两数之积。和先生告诉积先生:“我不知两数是什么;但我肯定你不可能根据你手上的乘积知道它们是什么”。因这句话,积先生恍然大悟说:“我现在知道了。” 和先生也马上说:“我也知道了。”这两个数是什么?

当时正烦心一直没想通的论文里的破事,就当是换一下思路想想这个蛋疼的题吧。结果仔细想了好久,才算有点头绪,觉得这个题最后还是得逐个试验排错,于是找到了同样蛋疼的计算机大牛室友一起捣鼓,写了段小程序折腾出来了。
思路是这样的:

第一步。
把从2+3到98+99里所有的数列个表,估且叫候选和表,这个表是最有用的。
第一句话,和先生能断言积先生不可能知道,到底说明了什么呢?首先一点当然是,积先生拿着的不可能是两个质数的积,也就是说和先生拿着的不是两个质数的和。那候选和表里的偶数就全挂了,因为我们有哥德巴赫猜想撑腰(把他老人家搬出来了感觉特别牛逼),另外奇数也挂了不少。但剩下的数也还是不少。
另外一点是,留意比99的一半大的第一个质数,在这里是53。任何一个剩下的数,都可以写成53和一个合数的和,比如57=53+4。但是57这个数就不可能留在候选和表里,因为积是53×2×2的情况下,只可能拆成53×4,才能让两个数都比99小。也就是说,在这个表里所有比53大的数,也就全挂了。
现在剩下的这个候选和表,是后面两步里的关键武器。在足够聪明的假设下,和先生和积先生现在都知道候选和表了。

第二步。
什么情况下积先生马上就知道了呢?
举个例子。11在刚才的候选和表里,那万一和是11,那两个数就可能是2+9,3+8,4+7,5+6。考虑2+9,积先生如果拿着18,他能不能说他知道了呢?18的话,就可能是2×9或者3×6。3×6的话意味着和是9,而9不在候选和表里。所以积先生的18就只可能是2×9,于是他就知道了。也就是说,对于候选和表里的每一个数,我们把它拆成两个数,然后就可以看看那两个数符不符合积先生的条件。但是这样结果还挺多的。

第三步。
什么情况下和先生接着就知道了呢?
再考虑刚刚的例子。2+9是符合第二步条件的解。而3×8=24=2×12=4×6,可以验证也只有3与8的和在候选和表里,于是3+8也是符合第二步条件的解。这就有问题了,因为拿着11的和先生不知道到底是2+9还是3+8。于是11就挂掉了。
于是把候选和表里的数挨个拆一遍,验证可得唯一解,4和13,和是17,积是52。

更有甚者,室友试着把99那个最大值改了一下,发现最多到866时4和13都是唯一解。而到867时下一组解就出现了,是4和61。至于为什么是866,程序也不在偶手上,不仔细调试一下恐怕不容易发现卡在哪里……

p.s.
发现自己还是没学会计算机的思考方式,比如偶还想了一下怎么做合数的分解,结果室友说直接就把所有组合都试一遍好了,晃然大悟。
另外,这个问题恐怕是纯蛋疼的,要问理论价值实际应用什么的怕是没有了。但偶听说数论好多结论就是这样,古代数学家们蛋疼多年都没找到可以实际应用的地方,结果到了现代密码学才发现“原来可以这么使!”什么的。偶觉得做学问的人还是要多有点蛋疼的精神的,政策扶持什么的也是,马上有实用价值的东西自然会有市场投入去做,就扶持一把那些蛋疼的人吧,说不定研究什么时候就有用呢……想太多了,反正偶也不是能做学问的人,交给你们疼好了……

不关事的p.s.
不知道电视台父亲节那个事搞成怎样了,各种囧啊……(◞‸ლ)