首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
确保“在任意的n个人中,必然有3个人相互都认识或有3个人相互都不认识”成立的最小的n的值为(69)。
确保“在任意的n个人中,必然有3个人相互都认识或有3个人相互都不认识”成立的最小的n的值为(69)。
admin
2010-01-29
19
问题
确保“在任意的n个人中,必然有3个人相互都认识或有3个人相互都不认识”成立的最小的n的值为(69)。
选项
A、5
B、6
C、7
D、8
答案
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/xGQZ777K
本试题收录于:
网络规划设计师上午综合知识考试题库软考高级分类
0
网络规划设计师上午综合知识考试
软考高级
相关试题推荐
描述一下C#中索引器的实现过程,是否只能根据数字进行索引?
如何理解委托?
什么是ASP.net中的用户控件
定义Fibonacci数列如下:输入n,用最快的方法求该数列的第n项。
如果WindowsXP能够识别网络适配器如何安装网络适配器。
如果在利用宽带连接,在Internet选项中设置宽带连接的用户名sy和密码2006。
在即时通讯工具MsN中,通过当前界面,把文件“c:\FuwA.jpg”发送给对方。
从当前界面开始,到“电话和调制解调器的选项”中,将系统中的标准56000bps调制解调器删除。
通过在附注中记录的“见过一面”这一信息来查找联系人。
下面是有关PPoint演示文稿播放控制方法的描述,其中()是错误的。A.可用键盘控制播放B.可用鼠标控制播放C.单击鼠标,幻灯片切换到"下一张",但用鼠标却不能切换到"上一张"D.按"↓"键切换到"下一张",按"↑"键切换到"上一张"
随机试题
荀子认为“君子居必择乡”的原因是()
颈椎病是否行手术治疗的主要依据是
A/环磷酰胺B/西咪替丁C/卡托普利D/马来酸氯苯那敏E/甲硝唑抗肿瘤药包括
女性,32岁,有心脏病4年,最近感到心悸,脉率84次/分,听诊发现心率100次/分,心律不齐,第一心音强弱不等,心尖部有舒张期隆隆样杂音。听诊的发现最可能是
下列关于投资者自动测定技术方案基准收益率的说法,错误的是()。
股票发行风险由证券机构承担的发行方式是()。
R1、R2是一个自治系统中采用RIP路由协议的两个相邻路由器,R1的路由表如下图(A)所示,当R1收到R2发送的如下图(B)的(V,D)报文后,Rl更新的五个路由表项中距离值从上到下依次为0、4、4、2、2那么,①②③④⑤可能的取值依次为
在关系模型中,每个关系模式中的关键字( )。
已知一个文件中存放若干工人档案记录,其数据结构如下:structa{charnumber[100];intage;floatp[6];};定义一个数组:structab[10];
There’safreeandimportanttool________canhelpalljobhunterstolookforajob:email.
最新回复
(
0
)