主题:【原创推理】对于Ready-go的推理题第一题我的推理分析 -- 不爱吱声
Ready-go给出了一道很好的推理题,实际上是一道很好的数论题,不知道为什么给发到了龙门客栈,以后可以直接发到科技版,让大家都合计合计。现在我将我对第一道题的推理分析贴到这里,欢迎大家讨论,看还有没有更好地解决办法。第二道题,还没找到好方法,等想到后再说吧。
下面是Ready-go的原题:
1
假设A先生和B先生都有足够的推理能力。现在有两个数,这两个数不相同并且取与1到50之间 (不包括1和50)。A先生只知道这两个数的和,B先生只知道这两个数的积。
A先生开始说话了:我不知道这两个数是什么,但是我可以肯定,B先生你也不知道。
B先生接着说:我还是不知道这两个数是什么。
A又说:那我现在知道这两个数是什么了。
B再说:呵呵,我现在也知道了。
请详细列出A和B先生的推理过程,并找到这两个数是什么。
这个问题是个很好的数论问题。我的推理分析如下,
条件1。先分析A拿到的数是什么。
A拿到两个数的和,进而推出B一定不知道两个数是什么。首先我们可以确定,任何大于或等于31的数,是不可能成为A所拥有的数的。因为任何大于或等于31的数记为n,总能写成大于或等于29的质数(记为q)与另一个数(n-q)的和,这样的话,不管n-q是合数,还是质数,B都能推出两个数是什么。因为即便n-q是合数,n-q的任何非1因子与q的积都将大与50,所以在这种情况下,[q,n-q]是唯一可能的数对!
其次,A拿到的数一定不包括任何两个质数的和,歌德巴赫猜想告诉我们,任何大偶数(大于6)都可以写成两个不同质数的和(这两个质数毫无疑问小于或等于23),因此A拿到的数一定不是偶数。此外,A拿到数一定可以写成2与另一奇数的和,显然这个奇数必定是合数。在31以内的奇合数有以下几个9,15,21,25,27,因此A拿到的数一定是2与上面几个数中任意一个数的和,只有五种情况,包括11,17,23,27,29。
下面我用列表的方式,列出了所有可能数的组合及其乘积:
11 17 23 27 29
2*9=18 2*15=30 2*21=42 2*25=50 2*27=54
3*8=24 3*14=42 3*20=60 3*24=72 3*26=78
4*7=28 4*13=52 4*19=76 4*23=92 4*25=100
5*6=30 5*12=60 5*18=90 5*22=110 5*24=120
6*11=66 6*17=102 6*21=126 6*23=138
7*10=70 7*16=112 7*20=140 7*22=154
8*9=72 8*15=120 8*19=152 8*21=168
9*14=126 9*18=162 9*20=180
10*13=130 10*17=170 10*19=190
11*12=132 11*16=176 ……
12*15=180
13*14=182
条件2。在A的第一句话以后,A和B已经知道了A的数的五种可能性,但B仍然说他不知道答案,说明B所拥有的数,一定是有两对以上因子的和满足条件1,所以我们可以从表中找到那些数的乘积是同时出现在至少两列上的,我已经用颜色标出来了。
条件3。然后A说,他知道了答案,说明A现在所有的数,一定只存在一种满足条件2的情况,也就是说在表中,那一列只含有一种带颜色的数,就一定是答案了。表中只有红色的满足此条件。
表中很清楚表明,A拿到的数是11,B拿到的数是30,这两个数是5和6。
这个问题出的好,出题人一定是个数论大牛!
本帖一共被 1 帖 引用 (帖内工具实现)
Ready-go给出的题目是要求50以内的数,我考虑即便是大于50的数此题目也只有唯一解。下面是我对于此题目的扩展与证明。
扩展的题目应为:
1假设A先生和B先生都有足够的推理能力。现在有两个大于1的不相同的数。A先生只知道这两个数的和,B先生只知道这两个数的积。
A先生开始说话了:我不知道这两个数是什么,但是我可以肯定,B先生你也不知道。
B先生接着说:我还是不知道这两个数是什么。
A又说:那我现在知道这两个数是什么了。
B再说:呵呵,我现在也知道了。
请详细列出A和B先生的推理过程,并找到这两个数是什么。
扩展问题的推理证明如下:
条件1。先分析A拿到的数是什么。
A拿到两个数的和,进而推出B一定不知道两个数是什么。那么A拿到的数一定不包括任何两个质数的和,歌德巴赫猜想告诉我们,任何大偶数(大于6)都可以写成两个不同质数的和,因此A拿到的数一定不是偶数。此外,A拿到数一定可以写成2与另一奇数的和,显然这个奇数必定是合数。进而,A拿到数可以写成2与另一个奇合数的和。而且任何可以写成2与另一个奇合数的和的数都可能是A拿到数!这是第一句话的充分必要条件!这里记这个奇合数为q-2,满足条件1的数为q.
条件2。在A的第一句话以后,A和B已经知道了A的数可能性,但B仍然说他不知道答案。这说明B所拥有的数,一定是有两对以上因子的和满足条件1。
条件3。然后A说,他知道了答案。这说明满足条件1的所有数中,一定只存在一种满足条件2的情况。
下面需要说明,满足条件3的情况只有一种,就是两个数为5和6。
这反过来需要证明所有的q,除了最小的11外,一定存在至少两个以上满足条件2。
我们知道,任何q(>=11),一定能写成大偶数(大于2)加奇数(q1)的形式,记他们的乘积为m。如果这个偶数除以2以后另一个因子为奇数(q2),我们有m=2*q2*q1。于是我们知道另一对数2和q1*q2的乘积也是m,因为q1*q2是奇合数,于是这两个数的和就一定满足条件1。
或者换句话说,至少满足条件1的任何数q,被可以写成6+奇数(q-6),10+奇数(q-10),14+奇数(q-10)......以后,所得到的数对一定被发现另外相应的一对能同时满足条件1和条件2。
数对[6, q-6], [10, q-10], [14, q-14]...
与
数对[2, 3*(q-6)],[ 2, 5*(q-10)],[2, 7*(q-14)]...
总是同时满足条件1和条件2。
于是我们会发现,当q=11时,只有5和6这么一对,因为其中的偶数6可以写成2*3,m=2*3*5,这样他的另一组和2+3*5一定也满足条件1。
大于或等于17的满足条件1的数,永远至少拥有6+奇数,10+奇数,和14+奇数的情况,于是都不符合条件3。
结论是:任何情况下,3条件都满足就是只有两个数为5和6。
第一题的限定条件,很可能是为了形式美,和第二题对称。
您看到我给的数据了吧,希望能有帮助。锁,总是绕道门后更容易打开。
虽说是妙手偶得, 这两题完全对称, 题面极具美感. 两题都有唯一解这个结论, 虽然还需要别人验证, 可我现在已经很有自信了. 因为我的程序解第一题被不爱证明完全正确, 第二题只要把+和*互换, 没道理出错.
还是有点不敢相信. 这50是哪里来的呢? 正如不爱所说, 第一题应不给上限更完美. 这50倒像是给第二题设计的. 我试了其他数字, 对第一题, 都是唯一解(废话); 对第二题, 有的无解, 有的解不唯一, 一般说来, 解是相近的两个大数(仔细想想是讲得通的).
Ready-go给的推理题真得挺难的.虫子想了一个晚上也没做出来, 干脆就放到一边,给“今古聊斋”写故事去了.昨天一看不爱同学交作业了. 先是一喜, 觉得河里果然高人辈出. 可在仔细读一读, 就觉得不对味. 忍了一天等大伙发言, 可最后还是自己跳出来给不爱挑错了. 唉, 在这版里当恶人的总是我 .
先说我做到哪儿了吧. 以第一题为例. 从A和B的第一次对话, 我们可以得出两个结论.
结论一 :
如果B先生所知道的两数之积可以分解为两个质数的话, 那么B先生可以推断出这两个数是什么, 因为这分解是唯一的. 而知道两个数的和的A先生“可以肯定,B先生你也不知道这两个数是什么”。 所以,我们可以肯定A先生所知道的两数之和是不可能分解为两个质数的. 换句话说, 两数之和不可能是 (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47) 中任意两个数的和的. 所以, 在5 (唯一分解为2+3)到97 (唯一分解为49+48)之间, 有可能的两数之和是(11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 82, 83, 85, 86, 87, 89, 91, 92, 93, 94, 95).
【注意】这儿我与不爱的的结果不同. 不爱根据歌德巴赫猜想把所有偶数给去掉了. 而我上面的计算却保留了82,86,92, 94等偶数. 这其中的不同是, 歌德巴赫猜想运用在这里是有附加条件的, 就是大数必须分解为两个不同, 而且小于50的质数之和. 就说82吧, 质数和的分解(3+79), (11+71), (23+59), (29+53), 和 (31+51)都不满足<50的条件 (41+41就不说了). 所以82是不能分解为两质数之和的, 是不能用歌德巴赫猜想排除的.
结论二 :
B先生从结论一已经所知道了两数的可能之和, 但“仍然还是不知道这两个数是什么”. 原因很简单, B先生从所知道的两数之积中能够分解出多种组合, 他们的积相同, 而和又在以上范围内. 根据这, 我们可以进一步缩小包围圈. 比如 x+y=95的分解有 (48+47) 和 (49+46), 而 (48*47) 和(49*46) 不可能分解为其他两个<50的数之积 (比如48*47=2*2*2*2*3*47, 任何其他因子与47乘结果都大于50), 所以x+y=95可以排除.
虫子编了个小程序, 得出的可能组合如下:
x*y x,y的组合
30 --> (15+2=17) 或 (6+5=11)
42 --> (21+2=23) 或 (14+3=17)
60 --> (20+3=23) 或 (12+5=17)
66 --> (33+2=35) 或 (11+6=17)
70 --> (35+2=37) 或 (10+7=17)
72 --> (24+3=27) 或 (9+8=17)
78 --> (39+2=41) 或 (26+3=29)
90 --> (45+2=47) 或 (18+5=23)
102 --> (34+3=37) 或 (17+6=23)
120 --> (24+5=29) 或 (15+8=23)
126 --> (21+6=27) 或 (14+9=23)
132 --> (33+4=37) 或 (12+11=23) 或 (44+3=47)
180 --> (20+9=29) 或 (15+12=27) 或 (36+5=41)
196 --> (49+4=53) 或 (28+7=35)
210 --> (30+7=37) 或 (15+14=29) 或 (42+5=47) 或 (35+6=41)
264 --> (33+8=41) 或 (24+11=35)
270 --> (45+6=51) 或 (27+10=37)
286 --> (26+11=37) 或 (22+13=35)
294 --> (49+6=55) 或 (21+14=35)
300 --> (25+12=37) 或 (20+15=35)
312 --> (39+8=47) 或 (24+13=37)
322 --> (46+7=53) 或 (23+14=37)
330 --> (30+11=41) 或 (22+15=37)
336 --> (48+7=55) 或 (21+16=37)
342 --> (38+9=47) 或 (19+18=37)
378 --> (42+9=51) 或 (27+14=41)
396 --> (44+9=53) 或 (36+11=47)
414 --> (46+9=55) 或 (23+18=41)
420 --> (35+12=47) 或 (21+20=41)
462 --> (42+11=53) 或 (33+14=47)
540 --> (36+15=51) 或 (27+20=47) 或 (45+12=57)
546 --> (39+14=53) 或 (26+21=47) 或 (42+13=55)
624 --> (48+13=61) 或 (39+16=55)
630 --> (35+18=53) 或 (30+21=51) 或 (45+14=59) 或 (42+15=57)
646 --> (38+17=55) 或 (34+19=53)
660 --> (44+15=59) 或 (33+20=53)
690 --> (46+15=61) 或 (30+23=53)
700 --> (35+20=55) 或 (28+25=53)
702 --> (39+18=57) 或 (27+26=53)
714 --> (42+17=59) 或 (34+21=55)
720 --> (48+15=63) 或 (45+16=61)
756 --> (36+21=57) 或 (28+27=55)
782 --> (46+17=63) 或 (34+23=57)
798 --> (42+19=61) 或 (38+21=59)
810 --> (45+18=63) 或 (30+27=57)
840 --> (40+21=61) 或 (35+24=59)
858 --> (39+22=61) 或 (33+26=59)
874 --> (46+19=65) 或 (38+23=61)
882 --> (49+18=67) 或 (42+21=63)
900 --> (45+20=65) 或 (36+25=61)
924 --> (44+21=65) 或 (33+28=61)
966 --> (46+21=67) 或 (42+23=65)
980 --> (49+20=69) 或 (35+28=63)
990 --> (45+22=67) 或 (33+30=63)
1050 --> (42+25=67) 或 (35+30=65)
1080 --> (45+24=69) 或 (40+27=67)
1170 --> (45+26=71) 或 (39+30=69)
1188 --> (44+27=71) 或 (36+33=69)
1260 --> (45+28=73) 或 (36+35=71)
1470 --> (49+30=79) 或 (42+35=77)
1680 --> (48+35=83) 或 (42+40=82)
看的头大了吧. 提醒大家注意, 我得到的组合要比不爱多得多. 不爱的推论中提到, “A拿到数一定可以写成2与另一奇数的和,显然这个奇数必定是合数。在50以内的奇合数有以下几个9,15,21,25,27,33,35,39,45,49,因此A拿到的数一定是2与上面几个数中任意一个数的和(包括11,17,23,27,29,35,37,41,47,51) (这儿不爱好像错误地认为A拿到的两数之和小于50. 要知道即使两数之和分解为(2+奇合数), 奇合数的范围应该是(9~93))。同时我们应该注意到,上面数字中后五个也是不可能的情况,因为我们考虑一个数是4或6的时候,则另一个数只能是大与25的质数,于是A拿到的数只有五种情况:11,17,23,27,29(这个为什么我是不明白, 不爱最好解释解释)。” 黑体红字是我不明白的地方. 我不理解不爱是如何将两数之和一下子缩小到只有五种情况的. 我穷举出来的结果表明, 两数之和可能是 (11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 77, 79, 82, 83) (见下面的列表).
进一步推论
其实我的作业就到此为止了.无法继续是因为我猜测不出从“A又说:那我现在知道这两个数是什么了。 B再说:呵呵,我现在也知道了。”可以得出什么样的信息来进一步明确两个数. 不爱说的条件3挺有启发性. A知道答案说明A手头的和数是 (11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 77, 79, 82, 83) 中的一个, 而且分解后的乘积只有一种可能. 问题是即使如此, 还是不能确定唯一答案的. 下面列的很清楚了: 结果可以是11 -> (6*5=30), 73 -> (45*28=1260), 77 -> (42*35=1470), 79 -> (49*30=1470), 82 -> (42*40=1680), 83 -> (48*35=1680). (请不爱说明一下如何排除73, 77, 79, 82, 83等和数的可能性.)
【注意】下面这个列表的本质和不爱的是一样的, 不同是: 1. 按列排出了所有可能的组合及乘积,而不爱是按行列出; 2. 不合结论2 (两数之积能分解出多种组合, 而和又在确定范围内) 的分解 如 2*9=18, 3*8=24, 4*7=28等除去了. 换句话说, 只有一个分解的和数就是满足不爱文中最后红色条件的数。
11 --> (6*5=30)
17 --> (9*8=72) 或 (10*7=70) 或 (11*6=66) 或 (12*5=60) 或 (14*3=42) 或 (15*2=30)
23 --> (12*11=132) 或 (14*9=126) 或 (15*8=120) 或 (17*6=102) 或 (18*5=90) 或 (20*3=60) 或 (21*2=42)
27 --> (15*12=180) 或 (21*6=126) 或 (24*3=72)
29 --> (15*14=210) 或 (20*9=180) 或 (24*5=120) 或 (26*3=78)
35 --> (20*15=300) 或 (21*14=294) 或 (22*13=286) 或 (24*11=264) 或 (28*7=196) 或 (33*2=66)
37 --> (19*18=342) 或 (21*16=336) 或 (22*15=330) 或 (23*14=322) 或 (24*13=312) 或 (25*12=300) 或 (26*11=286) 或 (27*10=270) 或 (30*7=210) 或 (33*4=132) 或 (34*3=102) 或 (35*2=70)
41 --> (21*20=420) 或 (23*18=414) 或 (27*14=378) 或 (30*11=330) 或 (33*8=264) 或 (35*6=210) 或 (39*2=78)
47 --> (26*21=546) 或 (27*20=540) 或 (33*14=462) 或 (35*12=420) 或 (36*11=396) 或 (38*9=342) 或 (39*8=312) 或 (42*5=210) 或 (45*2=90)
51 --> (30*21=630) 或 (36*15=540) 或 (42*9=378) 或 (45*6=270)
53 --> (27*26=702) 或 (28*25=700) 或 (30*23=690) 或 (33*20=660) 或 (34*19=646) 或 (35*18=630) 或 (39*14=546) 或 (42*11=462) 或 (44*9=396) 或 (46*7=322) 或 (49*4=196)
55 --> (28*27=756) 或 (34*21=714) 或 (35*20=700) 或 (38*17=646) 或 (39*16=624) 或 (46*9=414) 或 (48*7=336) 或 (49*6=294)
57 --> (30*27=810) 或 (34*23=782) 或 (36*21=756) 或 (39*18=702) 或 (42*15=630)
59 --> (33*26=858) 或 (35*24=840) 或 (38*21=798) 或 (42*17=714) 或 (44*15=660) 或 (45*14=630)
61 --> (33*28=924) 或 (36*25=900) 或 (38*23=874) 或 (39*22=858) 或 (40*21=840) 或 (42*19=798) 或 (45*16=720) 或 (46*15=690) 或 (48*13=624)
63 --> (33*30=990) 或 (35*28=980) 或 (42*21=882) 或 (45*18=810) 或 (46*17=782) 或 (48*15=720)
65 --> (35*30=1050) 或 (42*23=966) 或 (44*21=924) 或 (45*20=900) 或 (46*19=874)
67 --> (40*27=1080) 或 (42*25=1050) 或 (45*22=990) 或 (46*21=966) 或 (49*18=882)
69 --> (36*33=1188) 或 (39*30=1170) 或 (45*24=1080) 或 (49*20=980)
71 --> (36*35=1260) 或 (44*27=1188) 或 (45*26=1170)
73 --> (45*28=1260)
77 --> (42*35=1470)
79 --> (49*30=1470)
82 --> (42*40=1680)
83 --> (48*35=1680)
写了这么多,就是为了挑不爱一个错 . 不过答案是啥, 我是没招了. 等高人出手吧 .
A发言后,确实只有11,17,23,27,29这几个可能,您说的大于这些的都可以排除。举例,35=4+31,124虽然不是素数积,但除了4*31以外并无其他拆法(不爱的话的意思是,既然31大于25,就没法再从4那边挪一个因子过来了)。后面的还有哪个不信,我拆给您看。(我有电脑作后盾。)不爱的推理,确实漏了一些情况,但很巧,对结果没影响。
不明白您的是,既然用上程序了,何不从头到尾都用程序搜索,不要夹进人脑的推理。编完了,也好和我的结果对一下,回头再找巧办法。
http://www.cchere.com/article/177112
我想你要说的是这个意思:因为我们考虑一个数比如x是4的时候,xy的积可以分解为2*2*y的形式。因为2*y必须小于50, 所以另一个数只能是小于25的质数。于是x+y只有五种情况:11,17,23,27,29。
如果你真的这么想,就有两个错。一个错是因为x+y不一定是奇数。我的帖子中已经说明了,有偶数的可能(x+y=82)。更大的错是为什么只考虑xy=n1*n2*n3(n1~n3均为质素)的可能性。的确,在这种情况下,因为n1>2,所以n2和n3必须小于25。 问题是,为什么不考虑xy=n1*n2*n3*n4*n5...(即xy均为和数)的可能。这种情况xy互换因子产生的差别是可以小于2的。比如xy=1470=2*3*5*7*7, 有两种分解 (42*35)和 (49*30) (两组换的是2*3和7)。小筑不妨拆一下210和630。我的分解结果如下。
210 --> (30+7=37) 或 (15+14=29) 或 (42+5=47) 或 (35+6=41)
630 --> (35+18=53)或 (30+21=51) 或 (45+14=59)或 (42+15=57)
对小筑的结果,因为没有过程,我不知道你是怎么得出的。小筑有程序为后盾,不过我更看重的是背后的逻辑和推理。先开始我只想用笔和纸来完成任务,不得已才用计算机的。我的算法如下,好向小筑解释:
1。确定可能的x+y的值:(就是结论一中列出的 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 82, 83, 85, 86, 87, 89, 91, 92, 93, 94, 95).
2。寻找x*y组合中,x+y的值正好在上述范围内的组合。
for(i=0;i<2500;i++) x[i]=y[i]=xADDy[i]=xBYy[i]=-1;
for(i=2;i<50;i++){
for(j=2;j<i;j++){ //因为对称,只用搜一半就行
k=i*50+j;
if((i+j)== 结论一中的可能值之一)){ //在可能值数组中找一遍
x[k]=i, y[k]=j, xADDy[k]=i+j, xBYy[i]=i*j; //保存分解
}
}
}
3。寻找有多种分解的x*y值, 列出其分解(注意,分解出的x和y的合是结论一中的可能值之一)。
这个搜索就简单了。从数组的0~2499,取大于0的xBYy[i]值看后面还出现不,有重复就输出分解(x,y,x+y,x*y)到结果文件中。
首先应该明确说明,任何大于或等于31的数,是不可能成为A所拥有的数的。因为任何大于或等于31的数记为n,总能写成大于或等于29的质数(记为q)与另一个数(n-q)的和,这样的话,不管n-q是合数,还是质数,B都能推出两个数是什么。因为即便n-q是合数,n-q的任何因子与q的积都将大与50,所以在这种情况下,[q,n-q]是唯一可能的数对!
这个条件应该放在歌德巴赫猜想前面。
原来的帖子已经修改,请去看看是否还有疑问。
第一次论证的时候有一个条件没说明白,这次修改了一下论证次序应该没问题了。
谢谢啊!
cchere.com ◆不爱吱声 发于:5/22/2004 5:37:05 PM
我应该首先明确说明,任何大于或等于31的数,是不可能成为A所拥有的数的。因为任何大于31的数记为n,总能写成大于后等于29的质数(记为q)与另一个数(n-q)的和,这样的话,不管n-q是合数,还是质数,B都能推出两个数是什么。因为即便n-q是合数,n-q的最小因子是2,2*q〉50,所以在这种情况下,[q,n-q]是唯一可能的数对!
虫子半天才转过弯来。不爱的意思是, 如果x+y的值大于31,就可能被分解为 (29+(n-29))的形式。 而如果B所拥有的数正好符合这个条件(x*y=29*n1*n2*...),那么B就能推出[29,x*y/29=n-29]这个唯一可能的数对。反过来,A明确地指出不存在这种可能,就是说从(x+y)不可能分解出比25大的质数的。所以,x+y<31。
把这点说明了,就可以确定唯一解了。咱咋没想到呢?!
比如你让我解释清楚为何73, 77, 79, 82, 83不行。
我们可以应用第一个推论,任何大于31得数都能找到反例使得A的话不成立。
73 = 29+44, 如果B拿到的是29*44,那么B就能推出来了。尽管44=2*2*11,但是最小的2*29也是大于50的,于是B是可以猜出两个数是29和44的。当然和等于73的还有其他的数对同样可以作为反例,比如,[31,42],[37,36],[41,32],[43,30],[47,26],但是我们只要找到一组反例就行了。至于我说任何大于31的数都不行,实际上我考虑的是29是最小的大于50/2的质数,当A拿到的数能分解出来这种质数作为其中一个数的时候,这种质数的任何倍数都大于50,于是这种质数与另外的数成为唯一的可能了。B也就可以确定两个数了。
同理可以发现,
77 = 29+48
79 = 31+48
82 = 37+45
83 = 37+46
84 = 37+47
85 = 37+48
86 = 37+49
87 = 41+46
32 = 29+3
33 = 29+4
34 = 29+5
...