一道数论题（已用计算机语言求解成功） - 辕门射虎


	jidongshou (莴笋)

组别	士兵
级别	仁勇校尉
功绩	5
帖子	183
编号	45297
注册	2005-8-10
家族	瓦岗寨

#1

发表于 2006-8-27 16:04 资料个人空间短消息看全部作者

一道数论题（已用计算机语言求解成功）

已知两自然数大于等于2小于等于200，甲知两数之积，乙知两数之和
甲说：我不知道这两个数到底是多少……
乙说：我就知道你不知道！
甲说：那我就知道了！
乙说：那我也知道了！
求这两个数分别是多少？
不同于以前的,范围和对话都有不同!

[ 本帖最后由 jidongshou 于 2006-8-30 19:27 编辑 ]

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	jidongshou (莴笋)

组别	士兵
级别	仁勇校尉
功绩	5
帖子	183
编号	45297
注册	2005-8-10
家族	瓦岗寨

#2

发表于 2006-8-27 16:05 资料个人空间短消息看全部作者

占一楼发表解题日志（这道题不容易）
设a*b=p,a+b=q,则甲只知道p，乙只知道q
1.甲说：不知道
则p至少有3个因子，因此a与b中至少有一个合数，否则甲就知道答案了，换言之a和b不可能同时为素数
2.乙说：我就知道你不知道
也就是说乙将q进行和式分解，结果发现q不可能是两素数之和
这样的q有哪些呢？
（1）首先q不可能是偶数，因为歌德巴赫猜想告诉我们任何大于6的偶数都可以分解为两奇素数之和
（2） q-2也不能素数，否则可令a=q-2，b=2
（3） q的取值范围是[4，400]之间的自然数，参照（1）（2），我们可以把[4，400]之间的自然数分成两个集合一个是M={可分解为两素数之积的q，也即q或者为偶数或者q-2是素数}，N={q是奇数且q-2是合数}
那么乙所知道的q刚好属于N集，所以乙有此一言
3.甲说：那我知道了
也就是说甲将他所知道的p分解为所有可能的a*b形式，发现只有一种形式a+b属于N集，所以他就知道答案了。
这样的p有哪些呢？（我们是否也可以仿照第二步对p作一个区划）
（1）q是奇数，故p也必定是偶数（就不证明了）
4.乙说：那我也知道了
也就是说乙明白甲所知的p的特性之后，进一步针对自己所知道的q的所有和式分解a+b，算出所有可能的p，发现其中只有一个p——它的所有积式分解只有一个a+b属于N集
这个题目的关键在于对p是否可以像q那样作一个明确简单的分类
［８．２７］

[ 本帖最后由 jidongshou 于 2006-8-27 16:32 编辑 ]

[广告] 《精忠报国岳飞传完整版》火热发布


	jidongshou (莴笋)

组别	士兵
级别	仁勇校尉
功绩	5
帖子	183
编号	45297
注册	2005-8-10
家族	瓦岗寨

#3

发表于 2006-8-27 22:36 资料个人空间短消息看全部作者

没人会做吗?各位帮帮忙吧!!

[广告] 真诚支持说岳，携手共创辉煌


	jidongshou (莴笋)

组别	士兵
级别	仁勇校尉
功绩	5
帖子	183
编号	45297
注册	2005-8-10
家族	瓦岗寨

#4

发表于 2006-8-27 23:33 资料个人空间短消息看全部作者

没找到

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	jidongshou (莴笋)

组别	士兵
级别	仁勇校尉
功绩	5
帖子	183
编号	45297
注册	2005-8-10
家族	瓦岗寨

#5

发表于 2006-8-27 23:55 资料个人空间短消息看全部作者

原题使用穷举法,但是对于该题,范围扩大,穷举法失效

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	jidongshou (莴笋)

组别	士兵
级别	仁勇校尉
功绩	5
帖子	183
编号	45297
注册	2005-8-10
家族	瓦岗寨

#6

发表于 2006-8-28 00:00 资料个人空间短消息看全部作者

我拿到的题目就是200,所以说只能用数论的推理,不能用穷举法,其实我前几天已经疯到用穷举法一个一个排除过,最后宣告失败

[ 本帖最后由 jidongshou 于 2006-8-28 00:07 编辑 ]

[广告] 《精忠报国岳飞传完整版》火热发布


	jidongshou (莴笋)

组别	士兵
级别	仁勇校尉
功绩	5
帖子	183
编号	45297
注册	2005-8-10
家族	瓦岗寨

#7

发表于 2006-8-28 00:08 资料个人空间短消息看全部作者

而且题目也不完全一样

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	jidongshou (莴笋)

组别	士兵
级别	仁勇校尉
功绩	5
帖子	183
编号	45297
注册	2005-8-10
家族	瓦岗寨

#8

发表于 2006-8-28 08:58 资料个人空间短消息看全部作者

注意:
乙说的是我就知道你不知道！
这是该题的信息最多的地方！
和大家以前见得题目不同
范围使穷举法失效，而甲乙的第一次对话就是突破口。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	jidongshou (莴笋)

组别	士兵
级别	仁勇校尉
功绩	5
帖子	183
编号	45297
注册	2005-8-10
家族	瓦岗寨

#9

发表于 2006-8-28 19:41 资料个人空间短消息看全部作者

QUOTE:

原帖由 @rz 于 2006-8-28 18:38 发表
答案是多少?
2和2 行不行?
符合条件的哦

依照我的分析,这两个数一个为偶数,一个为奇数,2和2肯定不对

[广告] 《精忠报国岳飞传完整版》火热发布


	jidongshou (莴笋)

组别	士兵
级别	仁勇校尉
功绩	5
帖子	183
编号	45297
注册	2005-8-10
家族	瓦岗寨

#10

发表于 2006-8-28 19:46 资料个人空间短消息看全部作者

我们可以看一下2和2,a=2,b=2,p=4,q=4
甲知p=4，就已经可以确定2、2了

[广告] 真诚支持说岳，携手共创辉煌


	jidongshou (莴笋)

组别	士兵
级别	仁勇校尉
功绩	5
帖子	183
编号	45297
注册	2005-8-10
家族	瓦岗寨

#11

发表于 2006-8-30 19:26 资料个人空间短消息看全部作者

用计算机语言已得出正解:4、13
：甲知道的数为4*13=52，52=4*13=2*26，甲不知道具体是哪个。所以甲说：不知道
2：乙知道的数为4+13=17，而17=2+15或大于2的偶数加上一个奇数，而无论哪一种，其积至少3个质因数，故乙说：我就知道你不知道。
3：甲听了这句话，知道乙手中的数一定是奇数，并且减2是一个合数，否则乙不会那样断定，而4+13-2=15，满足，2+26-2=26，偶数，不满足。所以两数必为413。所以甲说他就知道了。
4：17= 2+15 = 3+14 = 4+13 = 5+12 = 6+11 = 7+10 = 8+9。验算的话能使前三条结论都确定成立的应该只有4，13，所以乙也得出了结果。
但是用数论推算尚无成功

[广告] 《精忠报国岳飞传完整版》火热发布