2. 计算机
  3. 确保“在任意的n个人中，必然有3个人相互都认识或有3个人相互都不认识”成立的最小的n的值为______。 A．5 B．6 C．7 D．8

确保“在任意的n个人中，必然有3个人相互都认识或有3个人相互都不认识”成立的最小的n的值为______。 A．5 B．6 C．7 D．8

admin2012-04-19  66
问题 确保“在任意的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://www.kaotiyun.com/show/mHLZ777K
本试题收录于： 系统分析师上午综合知识考试题库软考高级分类
0

系统分析师上午综合知识考试

软考高级

相关试题推荐
随机试题
最新回复(0)