目录: 标题| 题干| 答案| 搜索| 相关
问题

确保“在任意的n个人中,必然有3个人相互都认识或有3个人相互都不认识”成立的


确保“在任意的n个人中,必然有3个人相互都认识或有3个人相互都不认识”成立的最小的n的值为(54)。

  • A5
  • B6
  • C7
  • D8
参考答案
参考解析:

解析:本题是拉姆齐(Ramsey)数问题。一般地,一对正整数a和b对应一个正整数r,使得在r个人中或者有a个人相互认识,或者有b个人相互不认识,满足这个条件的r的最小值用r(a,b)表示,称,(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=l、2、3、4时,类似可举出反例。  当n=6时,设有6个人A、B、C、D、E、F。选定A时,其余人按照与A的认识关系可分为两类,即A认识类和A不认识类,不难得出这两类中一定有一类至少有3个人。假设A认识类至少有3个人,如果其中有3个人相互不认识,则得证;否则,A认识类中必有2个人相互认识,由于他们都与A相互认识,则得证。假设A不认识类至少有3个人,如果其中有3个人相互认识,则得证,否则,A不认识类中必有2个人相互不认识,由于他们都与A相互不认识,则得证。  所以,n=6是确保命题为真的最小正整数。

分类:其他
相关推荐

1、印刷滚筒离合压可以在任意的对应位置进行。

印刷滚筒离合压可以在任意的对应位置进行。A正确B错误

2、职业生涯规划必然和个人相联系,没有脱离个人而存在的职业生涯规划。这说明个人职

职业生涯规划必然和个人相联系,没有脱离个人而存在的职业生涯规划。这说明个人职业生涯规划具有()A动态性特征B组织性特征C个人性特征D时间性特征

3、个人理财业务建立严格的内部控制制度是风险管理的必然要求,其中包括( )。&n

个人理财业务建立严格的内部控制制度是风险管理的必然要求,其中包括( )。A个人理财业务的分析、审核、报告制度B内部监督和独立审核制度C资产分开管理制度D审批和报告制度E充...

4、A1考核标准要求控制区域的ACE在任意的多少分钟内必须至少过零一次?()

A1考核标准要求控制区域的ACE在任意的多少分钟内必须至少过零一次?()A1分钟B5分钟C10分钟D15分钟

5、个人客户可以在任意电话上进行查询及电话银行转账服务。

个人客户可以在任意电话上进行查询及电话银行转账服务。A正确B错误

6、对方差未知的正态总体进行样本容量相同的n次抽样,则这n个置信区间的宽度必然相

对方差未知的正态总体进行样本容量相同的n次抽样,则这n个置信区间的宽度必然相等。A正确B错误