首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
确保“在任意的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
61
问题
确保“在任意的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
系统分析师上午综合知识考试
软考高级
相关试题推荐
创建新演示文稿有多种方式,其中()会一步步地引导用户创建新演示文稿,生成演示文稿的基本框架。A.利用“内容提示向导”创建新演示文稿B.利用“模板”创建新演示文稿C.利用“空演示文稿”创建新演示文稿D.上述三种方式都可以
HTML代码imgsrc=nameborder=?表示______。A.添加一个图象B.排列对齐一个图象C.设置围绕一个图像的边框的大小D.加入一条水平线
将桌面上的Word应用程序通过“打开所有用户”窗口在“开始”菜单中创建快捷方式,然后查看创建快捷方式后的菜单。
请利用“我的电脑”窗口,格式化可移动磁盘(J:),卷标为“数字用盘”。
请将当前演示文稿的放映方式设置为:演讲者放映(全屏幕),绘图笔颜色为自动,幻灯片放映分辨率为800*600。
某工作簿存放了学生成绩,将存储在Sheet1中的课程分数,计算李林的总分,结果保存在Sheet2中的单元格A2中。
利用单元格的相对引用,计算学生成绩表中每个学生的总成绩。
将成绩表中单元格E13的总分平均分利用INT函数取整,结果保存在单元格F13中。
下列关系运算的叙述中,正确的是
最大的10位无符号二进制整数转换成十进制数是()。
随机试题
患者女性,62岁,高血压病4年。4小时前突然感到头痛,呕吐,家人发现两侧肢体轻微抽搐。查体:血压230/130mmHg,意识尚清,无肢体运动障碍。最可能的诊断是
厥证急救时,首先应分辨
夜间施工,是指()期间的施工。
人们在房地产开发或投资活动中,为实现某种预定的开发、经营目标而预先垫支的资金称为()。
“达人”对于“()”相当于“弓虽”对于“()”
有专家指出,发展危险性非常高的载人航天飞行器根本没有必要。但事实上太空竞争不仅没有止步,反而更趋激烈。从中我们可以看出()。
根据①与②之间的关系,③与下列()图具有同样的逻辑关系。
Personalityistoalargeextentinherent—A-typeparentsusuallybringaboutA-typeoffspring.【F1】Buttheenvironmentmustalso
打开考生文件夹下的演示文稿yswg.pptx,按照下列要求完成对此文稿的修饰并保存。对第一张幻灯片,主标题文字输入“计算机基础知识”,其字体为“楷体”,字号为63磅,加粗,红色(请用自定义标签的红色250、绿色0、蓝色0)。副标题输入“第一章”,其字体
A、School.B、Family.C、Community.D、Publicplaces.D根据短文第二段第一句Careereducation…occursinthefamily,inthecommunity,andinscho
最新回复
(
0
)