首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
确保“在任意的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
85
问题
确保“在任意的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
系统分析师上午综合知识考试
软考高级
相关试题推荐
在Word中编辑文档,若光标不在结尾处,以下()操作可完成将光标移到文档结尾处。A.PageDownB.Ctrl+PageDownC.EndD.Ctrl+End
在HTML语言中FRAMENORESIZE的具体含义是下列哪一项______。A.个别框架名称B.定义个别框架C.不可改变大小D.背景资讯
关于计算机硬件系统,下列()说法是正确的。A.软驱属于主机,软磁盘本身属于外部设备B.硬盘和显示器都是计算机的外部设备C.键盘和鼠标器均为输入设备D.“裸机”是指不含任何软件系统的计算机
在PPoint中,要添加或改变幻灯片中的对象链接,可选择“幻灯片放映”菜单中的()命令。A.动作设置B.预设动画C.幻灯片切换D.自定义放映
请设置回收站属性为“所有驱动器均使用同一设置”,并且回收站所占最大空间为驱动器的20%。
请将显示器的屏幕分辨率设置为“800*600”,颜色质量设置为“最高(32位)”,将显示器的“DPI”设置为“正常尺寸”(96DPI),且设置为“在应用新的显示设置之前重新启动计算机”(请按题目操作顺序操作)。
请快速选取较大单元格区域E6:G19。
Access2003是一个大型关系数据库管理系统,适合于开发大型管理信息系统。
【程序说明】程序功能是计算一个整数的各位数字之和。【程序】SETTALKOFFINPUT“x=”TOxs=0DOWHILEx!=0s=s+MOD(x,10)(1)(2)?SSETTALKON
Thefollowingscenariowillbeusedforquestions26,27,and28.Trentisthenewmanagerofhiscompany’sinternalsoftwarede
随机试题
恢复盂肱关节活动范围的康复治疗中最重要的是
设某人群的身高X服从N(155.4,5.32)分布,现从该总体中随机抽出一个n=10的样本,得均值为X=158.36,S=3.83,求得μ的95%可信区间为(155.62,161.10),发现该区间竟然没有包括真正的总体均数155.4。若随机从该总体抽取含
静脉输液是利用()和()形成的输液系统内压高于人体静脉压的原理将液体输入静脉内。
下列水泥品种中,其水化热最大的是()。
根据《旅游安全管理办法》规定,旅游突发事件,是指突然发生,造成或者可能造成旅游者人身伤亡、财产损失,需要采取应急处置措施予以应对的自然灾害、事故灾难、公共卫生事件、社会安全事件。()
下列属于文房四宝中湖笔的四大特点的是()。
关于警察的本质,下列说法正确的是()。
平面上有4个点A、B、C、D,已知AB、AC、AD、BC、BD的长度分别为25厘米、24厘米、12.5厘米、7厘米、12.5厘米。则CD的长度为多少厘米?
"Helicopterparenting"describesastyleofraisingchildrenwhereparentsareover-protectiveanddotoomuch.Thetermwasuse
TheMuseumofNaturalHistoryisoneofthemostinterestingmuseumsattheUniversityofKansas.Themuseumopenedin1903,and
最新回复
(
0
)