首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
确保“在任意的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
62
问题
确保“在任意的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
一般情况下,在Excel97工作表的单元格内输入的文本超过了列宽,而此单元格右边的单元格内无数据,此时()。A.超长的文字被截去,数据发生错误B.超长的文字被截去,但完整的数据还在单元格中C.输入的文本会扩展到右边的单元格D.显示“###
请将E盘根目录下的“backup”文件夹设为网络共享,共享名为“备份文件”。
在“我的电脑”窗口中快速格式化可移动磁盘,并将“KS”作为磁盘卷标。
打开“显示属性”对话框,在“桌面”选项卡中查看“位置”下拉列表框的帮助信息。
利用“我的电脑”打开资源管理器,利用左侧的浏览栏打开“C:\windows”,然后将其折叠,再打开“G:\公司常用文件”。
请将当前演示文稿的第8张幻灯片设置成“自定义”放映,名称为“CPU”。
请删除当前演示文稿中的自定义放映CPU。
某工作簿存放了学生成绩,将存储在Sheet1中的课程分数,计算李林的总分,结果保存在Sheet2中的单元格A2中。
将E-R图转换到关系模式时,实体与联系都可以表示成______。
随机试题
一般来说,背景吸收是使吸光度增加而产生正误差。()
下列病变不是T1及T2加权像均呈高信号的是
A、刺痛拒按,固定不移,舌暗,脉涩B、气短疲乏,脘腹坠胀,舌淡,脉弱C、胸胁胀闷窜痛,时轻时童,脉弦D、面色淡白,口唇爪甲色淡,舌淡,脉细E、少气懒言,疲乏无力,自汗,舌淡,脉虚血瘀证可见的症状是
《公司法》对公司的出资形式的限额做出限制的是( )。
消火栓的间距应小于或等于()。
常用的确定设备最佳更新期的方法有低劣化数值法和()。
为了预防病毒,在计算机中安装了操作系统补丁(windowsupdate)的防病毒软件,也按时升级了病毒定义文件,仍旧被种了木马程序(即被感染病毒),最不可能的原因是()。
以可见光波的长短为序,人类感觉到的颜色依次为()。
汉代选拔和任用官吏的方法有()
在计算机指令中,规定其所执行操作功能的部分称为()。
最新回复
(
0
)