首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
确保“在任意的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
79
问题
确保“在任意的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
系统分析师上午综合知识考试
软考高级
相关试题推荐
保存Word文档文件的快捷键是()。
若按下Shift键同时用鼠标分别单击幻灯片中的标题、文本和图片对象,则()。A.仅最后单击的对象被选中B.三个对象被同时选中C.仅标题对象被选中D.仅图形对象被选中
请利用“开始”菜单打开“录音机”并录制一段音乐,要求格式为“MPEGLayer-3”属性为“256kBit/s,23.000Hz,Sterero,并将该格式以‘mp3”为名进行保存,然后将声音文件保存到E盘根目录下,文件名为“001.wav”。
在桌面上已经打开了写字板窗口中利用动态键盘输入数学符号“±∑”。
已知道该电脑处于局域网中,请利用“网络和Intemet连接”将本地连接的IP地址设置改为自动获取IP。
请设置回收站属性为“所有驱动器均使用同一设置”,并且回收站所占最大空间为驱动器的20%。
请利用我的电脑窗口,对可移动磁盘“kingston(I)”进行检查,要求自动修复文件系统错误,扫描并恢复坏扇区。
在32×32点阵的字库中,存储一个汉字的字模信息需要()个字节。
Access2003是一个大型关系数据库管理系统,适合于开发大型管理信息系统。
随机试题
下列面谈的各自的基本目的是什么?①选择/聘用面试;②市场调查面谈;③与事故目击者的面谈;④绩效评估面谈;⑤销售面谈。
一男青年17岁,夜间突发右侧睾丸剧烈疼痛,有轻度咳嗽,无尿频,尿疼和尿急,来医院急诊检查,心肺(-),腹部检查未见异常,右侧睾丸较左侧略大,有明显触疼,阴囊无明显红肿,右附睾可及
成熟红细胞的主要供能代谢途径是
PM2.5是指直径
对化疗敏感的细胞
在给水管管材中,生产和消火栓消防给水管一般采用非镀锌钢管或()。
胡锦涛总书记在中共第十七次全国代表大会上作了重要报告。在报告中,他提及了关于社会主义文化建设的几个方面,主要有()。
设A为n阶矩阵,a0≠0,满足Aα0=0,向量组α1,α2满足Aα1=α0,A2α2=α0.证明α0,α1,α2线性无关.
Tothemajorityofus,musicisanindispensablepartofourdailylife.Itcanbedefinedinthisway,musicissoundarranged
ThenovelGulliver’sTravelsiswrittenby
最新回复
(
0
)