首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
确保“在任意的n个人中,必然有3个人相互都认识或有3个人相互都不认识”成立的最小的n的值为(69)。
确保“在任意的n个人中,必然有3个人相互都认识或有3个人相互都不认识”成立的最小的n的值为(69)。
admin
2010-01-29
21
问题
确保“在任意的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
网络规划设计师上午综合知识考试
软考高级
相关试题推荐
实现strstr功能(寻找子串在父串中首次出现的位置)
两个单向链表,找出它们的第一个公共结点。链表的结点定义为:structListNode{intm_nKey;ListNode*m_pNext;};
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
如果WindowsXP能够识别网络适配器如何安装网络适配器。
利用MSN给bob@sina.com发送电子邮件内容“8号晚上到我家一起吃饭”。
设置用户在拨号前不需要等待扬声器发出拨号声音。
在桌面上打开帮助和支持中心,利用“索引”的方法取得关于WindowsXP的“磁盘清理程序”方面的帮助信息。
在“打印机和传真”窗口,添加新硬件“Diconix公司的Diconix150Plus”,不自动检测端口,新硬件已接入计算机,要求检测,在列表中选择厂商和型号,手动安装,不打印测试页。
在单元格A1中,利用四则运算求出2007年1月1日到2007年12月15日期间的天数。
算法是使用计算机求解问题的步骤,算法由于问题的不同而千变万化,但它们必须满足若干共同的特性,但________一特性不必满足。
随机试题
在windows中,为了便于在文档中查找信息,可以使用_______符号来代表任何一个字符进行匹配。
Ihavetwobrothers.______inthearmy.
患儿女性,13岁10个月,主诉“间断头痛12天,精神行为异常3天”。病程中患儿无发热、抽搐。近3天偶有胡言乱语、乱跑、肢体舞动、舔唇、咀嚼、吞咽动作,同时出现睡眠不安及减少,患儿渐不能对答,不认识父母。既往体健,发育正常。该患儿病程中进一步出现的临床表
FcγR的功能不包括
一健康男性,输血前肝功能正常,所有肝炎病毒血清学检查指标均为阴性,输血后发生病毒性肝炎,可能因输血而感染的肝炎病毒是()
A.丹毒 B.痛经 C.晕厥 D.呃逆 E.便秘委中穴的主治病证是
骶管麻醉进针的部位是
(2007年)某理想气体在进行卡诺循环时,低温热源的温度为T,高温热源的温度为nT。则该理想气体在一个循环中从高温热源吸收的热量向低温热源放出的热量之比为()。
《规划环境影响评价条例》规定:有()情形之一的,审查小组应当提出不予通过环境影响报告书的意见。
上海证券交易所规定融资融券业务最长时限为()个月。
最新回复
(
0
)