首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
确保“在任意的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
64
问题
确保“在任意的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
系统分析师上午综合知识考试
软考高级
相关试题推荐
www服务向用户提供信息的基本单位是()A.网页B.文件C.链接点D.超媒体文件
如果要在自选图形上添加文本,(),然后键入文本。A.必须在自选图形上单击鼠标右键,选择“添加文本”命令B.必须使用“绘图”工具栏中的“文本框”命令C.只要在该图形上单击一下鼠标左键D.必须使用“常用”工具栏中“文本框”命令
HTML代码imgsrc=nameborder=?表示______。A.添加一个图象B.排列对齐一个图象C.设置围绕一个图像的边框的大小D.加入一条水平线
使用“开始”菜单打开“资源管理器”,在C盘根目录下创建名为“打字.txt”的文本文档。
通过快捷菜单调出语言栏,然后利用“开始”菜单打开控制面板,设置在任务栏中显示快速启动区。
请利用菜单,为当前幻灯片的文字添加菱形项目符号,并将其大小改为75%字高,同时将颜色设为绿色。
请将数据透视表中“红”和“妹”这两个数据项组合在一起,然后筛选出“丽”的数据。
在当前工作表中,模拟运算表的单元格区域为A13:B17,创建的模拟运算表是以B10单元格为输入单元格,用B14:B17中则会显示输入单元格数据的变化对B14单元格公式产生的影响。
Whattypeofriskanalysisapproachdoesthefollowinggraphicprovide?
信息系统规划方法中,关键成功因素法是通过对关键成功因素的识别,找出实现目标所需要的关键信息集合,从而确定系统开发的(4)________。关键成功因素来源于组织的目标,通过组织的目标分解和关键成功因素识别、(5)________识别,一直到产生数据字典。
随机试题
能产生LTA的细菌是
管电压在摄影条件选择中的意义,错误的是
保管特殊类型药材必须具有
在公共场所附近开挖沟槽时,应设防护设施,夜间设置照明灯和警示红灯。()
在某些情况下,被保险人患病或遭受意外伤害,最终是否残疾在短期内难以判定,为此保险公司规定一个定残期限,过了该期限后仍无明显好转征兆的,认定为全残。这种情况称为( )。
立面图的绘制中整个建筑的外轮廓尺寸线用( )线绘制。
信用风险管理委员会或类似机构可以考虑重新设定/调整限额的情况有()。
饮水时,应注意遵循少次多量的原则。
把对集体与个人的管理结合起来的班级管理是()。
A、Thecablecarride.B、GoldenGatePark.C、Fisherman’sWharf.D、Busesandstreetcars.A男士问女士最喜欢旧金山的什么,女士回答:“我也不知道,这很难说。我喜欢金门大桥
最新回复
(
0
)