首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
确保“在任意的n个人中,必然有3个人相互都认识或有3个人相互都不认识”成立的最小的n的值为______。 A.5 B.6 C.7 D.8
确保“在任意的n个人中,必然有3个人相互都认识或有3个人相互都不认识”成立的最小的n的值为______。 A.5 B.6 C.7 D.8
admin
2012-04-19
60
问题
确保“在任意的n个人中,必然有3个人相互都认识或有3个人相互都不认识”成立的最小的n的值为______。
A.5
B.6
C.7
D.8
选项
A、
B、
C、
D、
答案
B
解析
这是一道鸽笼原理(拉姆齐(Ramsey)数)的应用题。通常,一对正整数a和b对应一个正整数r,使得在r个人中或者有a个人相互认识,或者有b个人相互不认识,满足这个条件的r的最小值用,r(a,b)表示,称r(a,b)为拉姆齐数。求拉姆齐数r(a,b)是较困难的,但对于a和b较小时,是可以求解的。
当n=5时,有5个人A、B、C、D、E,假设A与B相互认识,B与C相互认识,C与D相互认识,D与E相互认识,E与A相互认识,除此之外,再没有其他相互认识关系。这样,就既没有3个人相互认识,也没有3个人相互不认识。
当n=1、2、3、4时,类似可举出反例。
当n=6时,设有6个人A、B、C、D、E、F。选定A时,其余人按照与A的认识关系可分为两类,即与A认识的记为X类,与A不认识的记为Y类,不难得出这两类中一定有一类至少有3个人。假设X类至少有3个人,如果其中有3个人相互不认识,则得证;否则,X类中必有2个人相互认识,由于他们都与A相互认识,则得证。假设Y类至少有3个人,如果其中有3个人相互认识,则得证;否则,Y类中必有2个人相互不认识,由于他们都与A相互不认识,则得证。可见,n=6是确保命题为真的最小正整数。
转载请注明原文地址:https://kaotiyun.com/show/mHLZ777K
本试题收录于:
系统分析师上午综合知识考试题库软考高级分类
0
系统分析师上午综合知识考试
软考高级
相关试题推荐
windows95是真正的( )位操作系统。A.8B.16C.32D.64
在PPoint97中,若要更改系统自动保存时间,可在()菜单中实现。A.文件B.视图C.格式D.工具
在Word97的编辑状态,进行字体设置操作后,按新设置的字体显示的文字是()。A.文档中被选择的文字B.插入点所在段落中的文字C.插入点所在行中的文字D.文档的全部文字
Powerpoint2000中,在演示文稿中插入公式,需要利用“公式编辑器”中的工具和菜单,使用()菜单中的命令打开公式编辑器A.编辑B.工具C.窗口D.插入
设有变量string=“四川省职称计算机应用能力考试”,能够显示“四川省计算机应用能力考试”的命令是()。A.string-“职称”1B.?SUBSTR(string,1,6)+SUBSTR(string,11,28)C.?SUBSTR(stri
背景快捷按钮在()工具栏A.常用B.格式C.绘图D.表格和边框
请为椭圆形图形对象添加文本,内容“椭圆形示例”。
请利用编辑栏插入函数。
关系操作的特点是()操作。
在下列关系数据库二维表操作中,________操作的结果二维表模式与原二维表模式相同。
随机试题
有“拉丁美洲的《纽约时报》”之称的巴西报纸是()
A.眩晕头重如蒙B.眩晕动则加剧C.眩晕耳鸣,头痛且胀D.眩晕而见精神萎靡E.眩晕头痛
任脉的终点是()
痰常规标本应何时采集
编制个人现金流量表时,需要注意的问题有( )。
根据我国《宪法》的规定,县级以上各级地方人民政府设立审计机关,地方各级审计机关依照法律规定独立行使审计监督权,对()负责。
下列命题属于客观唯心主义命题的是( )。
高适诗歌的体裁多为古诗,尤以_______为佳,代表作有《燕歌行》。
甲于2003年6月与乙合谋共同诈骗李某30000元,甲、乙平分各得15000元。在审理本案期间,甲主动交代曾在1997年3月间诈骗张某4000元的犯罪事实。在处罚甲诈骗罪时其犯罪金额应为()。
A、B、C、D、E五个选项为判断结果,请选择一项符合试题要求的判断。A.条件(1)充分,但条件(2)不充分。B.条件(2)充分,但条件(1)不充分。C.条件(1)和(2)单独都不充分,但条件(1)和(2)联合起来充分。D.条件(1)充分,条件(2)
最新回复
(
0
)