首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
确保“在任意的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
31
问题
确保“在任意的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://jikaoti.com/ti/gSJ7FFFM
本试题收录于:
系统分析师上午综合知识考试题库软考高级分类
0
系统分析师上午综合知识考试
软考高级
相关试题推荐
一般情况下,在Excel97工作表的单元格内输入的文本超过了列宽,而此单元格右边的单元格内无数据,此时()。A.超长的文字被截去,数据发生错误B.超长的文字被截去,但完整的数据还在单元格中C.输入的文本会扩展到右边的单元格D.显示“#####
以下属于文字处理软件的有()。A.WordB.WPSC.ExcelD.PowerPoint
若按下Shift键同时用鼠标分别单击幻灯片中的标题、文本和图片对象,则()。A.仅最后单击的对象被选中B.三个对象被同时选中C.仅标题对象被选中D.仅图形对象被选中
将“画图”窗口中的图形进行水平翻转。
使用“开始”菜单打开“资源管理器”,在C盘根目录下创建名为“打字.txt”的文本文档。
请利用“用户账户”窗口创建一个用户账户,账户名为“学生01”,账户类型为“受限”。
请给学生成绩表的某列“普通物理”设置一个链接其课程简介的超链接。
请将数据透视表中“红”和“妹”这两个数据项组合在一起,然后筛选出“丽”的数据。
表是关系型数据库系统的基本结构,是关于特定主题数据的集合。与其他数据库管理系统一样,Access中的表也是由()和()两部分组成的。
信息系统规划方法中,关键成功因素法通过对关键成功因素的识别,找出实现目标所需要的关键信息集合,从而确定系统开发的(18)________。关键成功因素来源于组织的目标,通过组织的目标分解和关键成功因素识别、(19)________识别,一直到产生数据字典。
随机试题
A.呆小症B.臣人症C.侏儒症D.肢端肥大症成年人生长激素分泌过多可引起
28岁初产妇,足月临产,产程进展顺利,LOA,先露S-0,胎心监护突然出现较频发的中、重度变异减速,此多为何种原因
患者肢体痿软,麻木微肿,足胫热气上腾,身体困重,胸脘痞闷,溲短涩痛,舌苔黄腻,脉滑数。其证候是
在土地分等定级工作中,不同层次的因素和因子之间不能进行累加和比较。()
收益性房地产的价值就是其未来净收益的现值之和,该价值高低主要取决于()这几个因素。
审议表决应当遵循“集体审查审议、明确发表意见、绝对多数通过”的原则。()
计算机病毒具有________、________、________寄生性、隐蔽性、针对性和衍生性。
温度的数值表示法叫做温标,下列不属于温标三要素的是:
Sincewearesocialbeings,thequalityofourlivesdependsinlargemeasureonourinterpersonalrelationships.Onestrengtho
最新回复
(
0
)