首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
确保“在任意的n个人中,必然有3个人相互都认识或有3个人相互都不认识”成立的最小的n的值为(69)。
确保“在任意的n个人中,必然有3个人相互都认识或有3个人相互都不认识”成立的最小的n的值为(69)。
admin
2010-01-29
18
问题
确保“在任意的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
网络规划设计师上午综合知识考试
软考高级
相关试题推荐
大概描述一下ASP。NET服务器控件的生命周期
组合问题(从M个不同字符中任取N个字符的所有组合)
自定义工具栏上的按钮添加“自动索引”按钮,删除“查找”按钮。
设置拨号连接属性卸载Qos数据包计划程序。
从当前界面开始,到“电话和调制解调器的选项”中,将系统中的标准56000bps调制解调器删除。
允许Microsoft收集有关我如何使用MSNMessenger匿名信息。
利用复选框进行设置,使新安装的程序在“开始”菜单中突出显示。
下面哪些属于中国域名()A.MicrosoftB.eeec.comC.ibm……ilD.bta.cn
将文档中的某段落的字体、字号、缩进、对齐等格式设置好后,希望在其他段落刚相同格式寸应选用“格式”菜单中的()命令。
美国国防部高级研究计划局于1968年主持研制,次年建成了()网。
随机试题
Thesewerevitaldecisionsthatboreuponthehappinessofeverybody.
阿胶的功效是()(1994年第141题)
患者主诉午餐食入海鱼后,即发生头痛、头晕、胸闷、心跳呼吸加快伴有眼结膜充血、颜面部及全身潮红,测体温正常,无呕吐腹泻等症状,该病可能是
(2004)在建筑工程建设程序中,以下哪项叙述是正确的?
与市场风险和信用风险相比,商业银行的操作风险具有()。
根据企业国有资产法律制度的规定,下列各项中符合规定的有()。
消除码间串扰的基本思想是当前码元的判决时刻,其他码元的值为1。()
学生证:学生
假定学生关系是S(S#,SNAME,SEX,AGE),课程关系是C(C#,CNAME,TEACHER),学生选课关系是SC(S#,C#,GRADE),要查找选修“COMPUTER”课程的女学生的姓名,将涉及到关系()。
完全无弹性是指需求对价格的变化不敏感,无论商品的价格如何变化,都会有特定的需求量存在而不会发生变化。根据上述定义,以下属于完全无弹性现象的是()。
最新回复
(
0
)