首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
确保“在任意的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
32
问题
确保“在任意的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
系统分析师上午综合知识考试
软考高级
相关试题推荐
通过“声音和音频设备属性”对话框,将声音方案设置为“Windows默认”。
计算八进制数324减123的值,再将结果转换为十进制。
请将当前演示文稿的放映方式设置为:演讲者放映(全屏幕),绘图笔颜色为自动,幻灯片放映分辨率为800*600。
请将艺术字“幻灯片学习”改为“Powerpoint2003幻灯片学习”,并修改艺术字的填充颜色。
请为上海的销售情况建立趋势线。
步骤1单击[公式]选项卡→[插入函数]按钮,在[选择函数]列表框中单击[SUMIF]→[确定]按钮,如图3—11所示。[*]步骤2单击[Range]处的图标按钮,选中单元格区域B3:B7。步骤3在[criteria]文本框
将E-R图转换到关系模式时,实体与联系都可以表示成______。
个人计算机的简称是()。
论IT服务团队建设与管理IT服务团队人员的岗位包括管理岗、技术岗和操作岗,都需要较高的服务意识,一个运维项目的成功离不开一个好的团队,团队管理在项目实施过程中起着非常重要的作用。在工作中,项目管理师要跟踪个人和团队的执行情况,提供反馈和协调变更,以此来提
论政务流程的优化与再造政务流程是一组相关的、结构化的活动集合,这些活动集合为公众提供特定的服务或产品。一般而言,政务流程有三类:面向公众的流程,为公众提供产品或服务;支持流程,为政府内部提供产品、服务和信息;管理流程,促使面向公众的流程和支持流
随机试题
如果压裂层平面上距离水淹带较近,裂缝过长会引起平面窜流,造成油井压裂含水上升,起不到增产的目的。()
主要用于抑制异体器官移植排斥反应的药物是哪一种
关于蔬菜、水果类的卫生问题叙述正确的是
乳母长期营养不良,乳汁中成分含量改变较显著的是()
我国现行投资估算中建设单位管理费应包括()等。
建设单位应当自建设竣工验收合格之日起()日内,将竣工验收报告和规划、公安消防、环保等部门出具的认可文件或者准许使用文件报建设行政主管部门或者其他有关部门备案。
小辛平时易受暗示,屈从于权威,按照他人的意见办事,不善于适应紧急情况。小辛的认知方式属于()。
下列属于纯四度音程的是()
Youprobablyknowyoushouldsay"please"and"thankyou"atrestaurants.Youprobablyknowtherulesofalibrary.Youknowyou
开发大型软件时,产生困难的根本原因是
最新回复
(
0
)